ABC 411 G — Count Cycles

考察

同じ二頂点間の異なる二辺は長さ2の cycle を作り、その数は各 pair について C_{u,v} choose 2 で、頂点数3以上の simple cycle とは分けて数える必要がある。長さ3以上の cycle は最大頂点 s を一意に持つ。s から頂点を重複せず辿る subset path DP を頂点1..sだけで行えば、cycleを最大頂点ごとに重複なく分類できる。一つの長さ≥3の無向 cycle は s から時計回り/反時計回りに辿る二方向だけ dp に現れるため、closing sum へ inv2 を掛ける。遷移 dp[S∪{j}][j]+=dp[S][i]C_{i,j}、閉じるときさらに C_{i,s} を掛けることで、同じ頂点列でも各隣接 pair の平行辺選択を独立に数えられる。

採用する候補: 辺多重度 C_{u,v} を遷移重みとする subset DP を最大頂点 s ごとに実行し、閉路を閉じる寄与を2で割る

dp[S][i] は s から S を一度ずつ通り i に至る path 数。未訪問 j への遷移と i→s の閉辺選択で multiedge の選び方も数えられ、N≤20で O(2^N N^2)。

棄却する候補: M 本の辺 subset を列挙して各集合が cycle か判定する

multi-edge により M は2×10^5あり 2^M は不可能で、cycleの頂点順序と各pairの辺選択を分離していない。

全 edge を C[u][v] に集計し、長さ2の寄与 Σ_{u<v}C_{u,v}(C_{u,v}-1)/2 を先に答えへ加える。s=3..Nごとに dp[{s}][s]=1 から、S⊆{1..s}、未訪問 j<s へ多重度付き遷移する。|S|≥3 の各末端 i から C_{i,s} で閉じる総和だけを inv2 倍し、長さ3以上の寄与として答えへ加える。

典型の発動条件

Hamilton path 型 subset DP

発動条件: 小さい頂点集合上で頂点重複のない path/cycle を数えるとき。

訪問maskと末端頂点を状態にし、未訪問頂点だけへ伸ばす。

canonical maximum による重複排除

発動条件: 同じ部分構造を複数の頂点集合範囲で数えそうなとき。

cycleの最大番号sを固定し、使用頂点を1..sに制限する。

multi-edge の multiplicity 重み

発動条件: 頂点遷移は同じでも選べる辺自体を区別して数えるとき。

遷移ごとに端点間辺数 C_{i,j} を掛ける。

問題固有の要素

長さ2 cycleだけは二頂点間の平行辺二本という別構文で数え、長さ3以上は最大頂点を根にした二方向 path として数える。

別の問題へ持ち帰る視点: multi-graphのcycle数え上げでは、頂点列のDPと各stepの辺多重度を分け、通常graphにない最短cycleを先に切り出す。

正当性

二頂点 cycle は平行辺から異なる二本を選ぶ組なので別計数する。三頂点以上では最大頂点sが一意。s始点の訪問集合と終点のDPは、未訪問頂点への辺多重度を掛けて全単純pathを数える。sへの閉辺でcycleにし、同じ無向cycleは二方向のちょうど二回現れるため2で割る。最大頂点を制限することで始点回転の重複は生じない。

実装上の注意

  • 長さ2をsubset DPへ混ぜず、|S|≥3だけ閉じる。C_{u,v} とDP積は毎回modを取り、各sでdpを初期化・再利用してmemoryを抑える。

復習の核

  • 平行辺だけの二頂点graph、triangle各辺の多重度積、一つの4-cycle、chord付き小graphをedge subset全列挙と比較する。

計算量と制約

時間

N 頂点 M 辺。多重度化 O(M+N²)、最大頂点s別DPの合計 O(N²2^N)、全体 O(M+N²2^N)。

空間

pair多重度O(N²)、各sのpathDPを再利用して O(N2^N)。

制約との対応

公式制約の確認範囲: Time limit: 6 sec; Memory limit: 1024 MiB; Constraints: 2\leq N \leq 20; 2\leq M \leq 2\times 10^5; 1\leq U_i < V_i \leq N; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Count Cycles の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 部分集合・bitmask状態DP

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 部分集合・bitmask状態DP

    補助タグ: 法上の四則演算・高速累乗・逆元 状態・配置の正規化

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: 部分集合・bitmask状態DP

    • bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題