Phoenix and Odometers | Codeforces 1515G
给定一张 \(n\) 个点 \(m\) 条边的带权有向图。
有 \(q\) 次询问,每次给定 \(v,s,t\),问是否存在一条起点终点都为 \(v\) 的路径满足 \(t | (s+l)\),其中 \(l\) 是路径的总长。
\(n, m,q \le 2 \cdot 10^5,s<t\le 10^9\),边权均不超过 \(10^9\)。
首先这条路径只能在 \(v\) 所在强连通分量的内部。
以下所有的路径长度都是在模 \(t\) 意义下的。
引理:在同一个强连通分量,如果 \(u\rightarrow v\) 存在一条长度为 \(l\) 的路径,那么 \(v\rightarrow u\) 存在一条长度为 \(-l\) 的路径。
构造:假设 \(v\rightarrow u\) 存在一条长度为 \(w\) 的路径,先走 \(v\rightarrow u\),长度为 \(w\),再走 \(t-1\) 次 \(u\rightarrow v\rightarrow u\),长度为 \((t-1)(l+w)\),总长度 \(-w\)。
在强连通分量的内部,对于一个长度为 \(w\) 的环,从环上一个点 \(u\) 出发绕若干圈再回到 \(u\),所有可能的路径长度为 \(\gcd(w,t)\) 的倍数。根据引理,\(v\rightarrow u\) 有一条长度为 \(w\) 的路径,\(u\rightarrow v\) 有一条长度为 \(-w\) 的路径,先走 \(v\rightarrow u\),再绕若干圈,最后走 \(u\rightarrow v\),就可以凑出所有长度为 \(\gcd(w,t)\) 倍数的环。
以 \(r\) 为根建出 DFS
树,设 \(\phi(u)\) 表示从 \(r\) 沿着树边走到 \(u\) 的路径长度,对于每条非树边 \((u,v,w)\),意味着存在一个长度为 \(\phi(u)+w-\phi(v)\) 的环。设 \(x=\gcd_{(u,v,w)}\phi(u)+w-\phi(v)\),那么所有的可能环长分别为 \(0,x,2x,3x,\cdots\)。这些环长显然能取到,也可以归纳证明对于任何 \(r\rightarrow u\) 的路径,都有长度 \(\equiv \phi(u)\pmod x\)。结论:存在合法路径当且仅当 \(x|s\)。
复杂度 \(O(n+m)\)。
代码:
1 |
|