ABC 253 Ex — We Love Forest

考察

選ばれた辺が森であることは、頂点集合を互いに素な木成分へ分解できることと同値であり、各頂点部分集合上の木の個数は行列木定理で求められる。

採用する候補: 行列木定理と部分集合DP

各部分集合の全域木数を前計算し、固定頂点を含む成分を切り出す漸化式で成分順の重複なくi辺の森を数えられる。

棄却する候補: M本の辺から操作列を直接列挙

操作列はM^i通りあり、N≤14でも辺数と回数に対して指数的すぎる。

多重辺はラプラシアンの非対角成分へ本数を加えることで、行列木定理の木数に選んだ平行辺の違いまで反映できる。

部分集合Sの最小頂点など一つを固定し、その頂点を含む成分Tだけを列挙すると、同じ成分分割を並べ替えて数える重複を防げる。

全頂点部分集合Tについて多重辺ラプラシアンの余因子行列式からtree[T]を求める。固定頂点を含むTを列挙してforest[S][i]へtree[T]×forest[S\T][i-(|T|-1)]を加え、得た森の辺集合数にi!を掛けて全M^iで割る。

典型の発動条件

行列木定理

発動条件: 多重グラフの指定頂点集合上にある全域木数が必要になる。

誘導多重グラフのラプラシアン余因子の行列式を法上で計算する。

成分分解の部分集合DP

発動条件: 森を木成分の集合として数えたい。

固定頂点を含む木成分を一つ選び、残り頂点の森DPと結合する。

問題固有の要素

森の確率を操作順から直接追わず、まず順序なし辺集合を木成分へ分解して数え、最後に異なる辺の選択順i!を戻す。

別の問題へ持ち帰る視点: 小頂点数のグラフで「各連結成分に既知の数え上げ公式がある」なら、成分を部分集合DPで組み立てる。

正当性

森は木成分の頂点分割を一意に持ち、各成分の木数は平行辺本数を含むラプラシアン余因子の行列木定理で得られる。固定頂点を含む成分だけ選ぶ再帰で成分順の重複を除く。i辺の森では辺を全て一度ずつ選ぶ順序がi!通りなので、森数·i!/M^iがi回抽選で森になる確率になる。

実装上の注意

  • 空集合の0辺森林を1とし、木Tの辺数は|T|-1としてDP添字を合わせる。平行辺の本数、i!、M^iの逆元を法998244353で正しく扱う。

復習の核

  • N≤5で全操作列を列挙し、平行辺がある例、孤立頂点、i=0の基底、木数と森数の合計、i!による順序復元を確認する。

計算量と制約

時間

O(2^NN³+N3^N)。各subsetの行列式と辺数付き成分分割DP。

空間

O(N2^N+N²)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 14; N-1 \leq M \leq 500; 1 \leq u_i,v_i \leq N; u_i\neq v_i; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

We Love Forest の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 行列式による数え上げ

主題
  • 行列式による数え上げ: 辺重みからLaplacianを構成し、根の行列余因子を全域木の重み付き個数へ対応させられる。有向木の向きと自己ループの扱いを説明できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 行列式による数え上げ

    補助タグ: label付き連結成分分解・exponential formula 法上の四則演算・高速累乗・逆元

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

    学習の位置

    体系上の位置: 行列式による数え上げ

    • 辺重みからLaplacianを構成し、根の行列余因子を全域木の重み付き個数へ対応させられる。有向木の向きと自己ループの扱いを説明できる。

    先に読む単元:

    • label付き連結成分分解・exponential formula — 生成関数による組合せ構造の符号化で得た考え方と実装を再利用し、label付き連結成分分解・exponential formulaの発動条件・正当化・境界を重複なく学ぶ。
    • 線形方程式・rank — 制約を体上の連立一次方程式へ写し、Gaussian eliminationでrank・可解性・解空間次元を求める。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
    • 法上の四則演算・高速累乗・逆元 — 剰余を正規化して加減乗算し、二分累乗と逆元の存在条件を使って法上の除算や確率を計算する。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題