裴蜀定理

题意简述

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

题意转化

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

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

任意找一点 uu,只需考虑经过 uu 的所有环。

考虑有一不经过 uu 的环,其长为 aa;另有一经过所有点的环(本图强连通),其长为 bb。则有 gcd(a,b,a+b)=gcd(a,a+b)\gcd(a,b,a+b)=\gcd(a,a+b)

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

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

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

More
  • 2023年11月22日