250525 模拟赛 T2 题解
题意
给定一张无向图,包含 \(n\) 个点和 \(m\) 条边(可能包含重边自环),边有边权。有 \(q\) 次询问,每次询问给定 \(x,y,d\),询问 \(x\) 和 \(y\) 之间是否存在一条路径(可以经过同一个点或边多次),其长度为 \(d\) 的整数倍。输出 Yes
或 No
。
\(n,m\le 10^6,\ w\le 2^{60}-1\)
部分分:保证所有边权等于 \(1\),所有询问 \(d=2\)。
题解
当 \(x\) 和 \(y\) 不在同一个连通块时,答案显然为 No
。现在我们考虑同一个连通块中的情况。
考虑部分分。注意到如果连通块内存在奇环,则我们可以随意改变路径的奇偶性,因此这种情况答案一定是 Yes
。否则,图是一个二分图,我们只需要判断 \(x,y\) 是否在图的同一侧即可。
考虑普通情况。继续观察,容易发现当 \(d\) 是奇数时,我们只需要找到 \(x\to y\) 的一条路径,然后在路径上走 \(d\) 次即可。
考虑推广这个结论:容易发现,这本质上是把一段长度为 \(l\) 的路径乘上了任意的奇数 \(p\)(上面 \(p=d\)),并且过程是充要的。因此我们可以把 \(d\) 拆分成 \(l\times p\),取 \(l=2^k\),\(k\) 即 \(d\) 中质因子 \(2\) 的次数。这样,问题就转化为找到一条被 \(d=2^k\) 整除的路径。
仍然先考虑有奇环的情况。由于边权边权不一定 \(=1\),此处的奇环定义为权值和为奇数的环。由于一个奇数一定和 \(2^k\) 互质,因此我们可以通过这个环构造出 \(1\pmod {2^k}\),由此可以直接构造出答案。
否则,图是一个二分图:奇数边跨过两个集合,偶数边两个端点都在同一个集合内。若 \(x,y\) 分布在两个集合中,那么所有 \(x\to y\) 的路径权值和都是奇数,一定不行。若 \(x,y\) 位于同一个集合内,我们先随便找出一条 \(x\to y\) 的路径,路径包含至少一条奇数边,权值和为 \(s\)(有 \(2\mid s\))。任选路径中一条奇数边,记其权值为 \(w\),我们希望找到一个满足 \(s+2qw\equiv 0\pmod {2^k}\) 的正整数 \(q\)。注意到这个式子等价于 \(\frac{s}{2}+qw\equiv 0\pmod {2^{k-1}}\),显然有解(\(w\) 与 \(2^{k-1}\) 互质)。
然而,我们假设了图中存在一条奇数边,这不一定成立。这时,我们可以取连通块中所有边权的 \(\operatorname{gcd}\),记其中 \(2\) 的次数为 \(p_2\)。如果 \(k\le p_2\),显然有解;否则我们将所有边权都除以 \(2^{p_2}\),这样至少会产生一条奇数边,就转换为上面的情况。
AC 代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
|