MOCK PTS- 20231122 B – 迷失 – 强连通图所有环长度之最大公约数

题意简述

给定不含重边的有向图 $G$，设其邻接矩阵为 $A$，定义其元素的“加”为逻辑或，“乘”为逻辑与。问 $A^c,c=1,2,\cdots$ 在何时出现循环节（$c=k$），以及最小循环节长度 $d$（即，$A^k=A^{k+d}$，$k,d$ 均最小）。

题意转化

在原图上，从 $u$ 出发，可用恰 $b$ 步走到 $v$，则在 $b$ 次迭代后的图上有有向边 $(u,v)$。问最少迭代多少次后图的形态出现循环节。

强连通图的所有环环长的最大公约数

任意找一点 $u$，只需考虑经过 $u$ 的所有环。

考虑有一不经过 $u$ 的环，其长为 $a$；另有一经过所有点的环（本图强连通），其长为 $b$。则有 $\gcd(a,b,a+b)=\gcd(a,a+b)$。

我们任意找一棵本图的搜索树。设其根为 $u$。设节点 $v$ 的深度为 $\newcommand\dep{\operatorname{dep}}\dep(v)$。设某经过 $u$ 的有限长度的环依次经过了非树边（横叉边、返祖边） $(v_1,w_1),(v_2,w_2),\cdots,(v_t,w_t)$。那么其环长在答案中可以被 $\gcd(|\dep(v_i)+1-\dep(w_i)|,i\in\{1,2,\cdots,t\})$ 取代。

可得 $w_i$ 一定是 $v_{i+1}$ 的祖先。我们删去 $(v_1,w_1)$，得到另一个环；这环与原来环的长度差为 $\dep(w_1)-\dep(v_1)-1$。这两环均在答案中作出贡献；又由于 $\gcd(a,b)=\gcd(a,b-a)$，则我们将原来的环长等价替换为两个数：其一即 $|\dep(w_1)-\dep(v_1)-1|$，其二为现在的环长。再继续删除 $(v_2,w_2),\cdots$，便等价地换为 $t+1$ 个数。

因此我们遍历一遍搜索树，就可以在 $\operatorname{O}(n\log n)$ 的时间内求出所有环环长之 $\gcd$。

若图强连通

假设 $u$ 可以用恰好 $c$ 步以内到达 $v$（此处并未对 $c$ 的大小作任何要求！）。由裴蜀定理可得，整数不定方程 $\sum a_ix_i=b$ 有解当且仅当 $\gcd(a)\mid b$。只要我们求出所有环长的 $\gcd$——设其为 $g$，设有自然数 $t$，则在 $t$“大到一定程度”后，总能用恰 $c+t\cdot g$ 步从 $u$ 走到 $v$。需要“大到一定程度”是因为 $x_i$——也即每个环的途径次数——应当非负，同时为了保证构造出可达的方案，甚至可能要求 $x_i>0$。则此种情况下，本题的第二问答案为 $d=g$。由于 $g$ 已经是最大公因数，故若 $d<g$，则由裴蜀定理（的逆定理——原来并不是“当且仅当”）知与所求相悖。

若不强连通

设各个强连通分量的环长之 $\gcd$ 为 $g_1,\cdots$，第二问答案变成 $\operatorname{lcm}(g)$。

现在考虑第一问。对于一条路径 $x$ 到 $y$，设其经过的连通块环长之 $\gcd$ 依序排开为 $g_1,\cdots,g_t$，那么路径长度总能写成 $p_1+q_1g_1+p_2+q_2g_2+\cdots+p_t+q_tg_t$，其中 $q_i,p_i$ 均为自然数。再次应用裴蜀定理可以得到其循环节长度应为 $\gcd(g)$。那么最早在何时才能进入循环节呢？我们给出一个粗略的上界：$n^3$。

有整数不定方程 $\sum_{i=1}^n a_ix_i=b$ 满足 $1\leq a_i\leq m\land \gcd(a)\mid b$。则当 $b\geq nm^2$ 时，一定可以找到一组自然数解。

我们只需说明，对于任意 $b\geq 0$，都能构造出一组解，满足 $\forall i,x_i\geq -m$ 即可。

这对于 $n=2$ 很好证明。不妨考虑将它写作 ${a_1}’x_1+{a_2}’x_2=b’$，其中 $g$ 是 $\gcd(a_1,a_2)$，${a_1}’,{a_2}’,b’$ 分别是 $a_1/g,a_2/g,b/g$。则 $x_2=(b’-{a_1}’x_1)/{a_2}’$，$x_1$ 在 $\pmod {{a_2}’}$ 意义下有唯一解：它是 ${a_1}’^{-1}\cdot b’\pmod{{a_2}’}$（二者互质，故有逆元）；$x_2$ 之于 ${a_1}’$ 同理。在整数域上，我们去掉 $\bmod{{a_2}’,{a_1}’}$ 的限制，就可得到解 $x_1,x_2\geq -m$，且必有 $x_1\geq 0\lor x_2\geq 0$。

对于 $n>2$，我们逐个分裂前 $n’-1$ 项和第 $n’$ 项构成的方程即可，并始终让前 $n’-1$ 项合并得到的系数 $\geq 0$。

于是答案就容易求得了：我们直接在 $[1,n^3]$ 上二分 $k$，检查 $A^k\stackrel{?}{=}A^{k+d}$ 即可（$d$ 已在上文中求出）。利用 std::bitset <N> 优化矩阵乘法，时间复杂度 $\operatorname{O}(n^3\log n/\omega+n\log n)$。