考察
walkがstart/endともvertex 1なら途中で使えるのは1から到達でき、かつ1へ戻れるverticesだけなので、1を含むSCC以外を削除できる。このSCC内のclosed-walk lengthsのgcd Gが巨大step数を割ることが必要十分であり、10^(10^100)のprime factorsは2と5だけである。全edgesでd_v≡d_u+1 mod aなら任意closed walk長はaの倍数で、違反edgeがあればtree pathsと組み合わせてa非倍数のclosed walkを作れる。十分大きいlengthではcycle lengthsの非負結合がgcdの倍数をすべて表すため、exact huge lengthの存在はperiodのdivisibilityだけで決まる。
棄却する候補: 巨大回数までreachable length setsをDPまたはmatrix exponentiationで追う。
指数自体を保持できず、N×N matrixも総N=20万に不適切である。
採用する候補: 1-rooted spanning treeのdepth dを作り、全SCC edges u→vについて|d_u+1−d_v|のgcdを取る。
このgcdは全closed-walk lengthsのperiodと一致し、graph一走査で計算できる。
典型の発動条件
有向graphの周期gcd
発動条件: 同じvertexへ戻るwalkの可能lengthを巨大なexact値について判定したいとき。
root distance potentialと各edgeのdepth差+1のgcdからSCC periodを得る。
往復可能領域の抽出
発動条件: startから出て同じstartへ戻るwalkだけが対象のとき。
forward reachableとreverse reachableのintersection、すなわちstart SCCだけを残す。
問題固有の要素
G>0からfactor 2と5を繰り返し除き、残りが1ならGはtargetのdivisorになる。
別の問題へ持ち帰る視点: target整数が巨大でもprime factorizationが既知なら、divisibilityはcandidate gcdの余分なprime factorsだけ調べればよい。
正当性
1から戻れる walk は1のSCC内だけ。DFS potential d に対する全辺の差 d_u+1−d_v のgcd Gは閉walk長のperiodに一致する。SCCの十分大きい閉walk長はこのperiodの倍数すべてを含むので巨大指定長がGの倍数かで判定できる。指定長の素因数は2,5だけのため G から2,5を全て取り除いた残りが1なら成立。正閉walkがないG=0は除外する。
実装上の注意
- 1のSCC内にpositive closed walkがなくG=0ならNoとし、gcd更新ではabsolute valueを取る。
- Tが多いため各caseのadjacency/reverse adjacencyとvisited arraysをcase sizeに応じて初期化する。
復習の核
- exact-length closed walk問題は、個々のcyclesではなくSCCのperiod gcdへ圧縮する。
- cycle length gcdは全cycles列挙を避け、spanning-tree potentialに対するnon-tree edge discrepancyから得る。
計算量と制約
時間
各 case の N 頂点、M 有向辺に O(N+M)。SCC抽出と discrepancy gcd(整数幅固定)を一巡ずつ。
空間
正逆隣接とSCC・potentialで O(N+M)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: All input values are integers.; 1\leq T \leq 2\times 10^5; 2\leq N \leq 2\times 10^5; 1\leq M \leq 2\times 10^5; The sum of N over all test cases is at most 2 \times 10^5.; The sum of M over all test cases is at most 2 \times 10^5.; 1 \leq U_i, V_i \leq N; U_i \neq V_i; If i\neq j, then (U_i,V_i) \neq (U_j,V_j).
出典