Day 095-Q4 | Matrix-Forest定理（全域森数え上げ）

問題

$N$ 頂点 $M$ 辺の無向グラフ（辺重みはすべて1）が与えられる。全域根付き森（spanning rooted forest）の個数を素数 $998244353$ で割った余りを求めよ。

全域根付き森とは、辺の部分集合であって閉路を含まず、全頂点を含み、各連結成分（木）にちょうど1つの「根」が指定されている構造。Matrix-Forest定理（Chebotarev–Shamis, 1997）により、この個数はラプラシアン行列 $L$ を用いて

$\text{全域根付き森の個数} = \det(I + L)$

で与えられる。

入力形式

N M
u_1 v_1
:
u_M v_M

制約

$1 \le N \le 500$

$0 \le M \le \frac{N(N-1)}{2}$

単純グラフ（連結とは限らない）

入出力例

入力例1

2 1
1 2

出力例1

2頂点1辺: 辺を使わず両方自己根(1通り) + 辺を使い根を頂点1または2にする(2通り) = 3。三角形(N=3,M=3)の場合は16。

概念図

ヒント（段階的開示）

ヒント1: 方向性

通常の行列木定理はラプラシアン行列の余因子（1行1列を除いた小行列式）で「連結な全域木の個数」を求める。今回は「複数の木からなる森」かつ「各木に根が1つ」という設定であり、余因子ではなく行列全体に単位行列を足した $\det(I+L)$ を使う点が異なる。

ヒント2: アプローチ

$I+L$ を実際に構成し、$\bmod\ p$ 上でガウスの消去法により行列式を計算すればよい（$p=998244353$は素数なのでピボットの逆元はFermatの小定理 pow(x, p-2, p) で求まる）。行の入れ替え回数の偶奇で符号が決まることに注意。

ヒント3: 誘導（コード骨格）

def det_mod(mat, n, mod):
    det = 1
    for i in range(n):
        piv = next((r for r in range(i, n) if mat[r][i] % mod), -1)
        if piv == -1:
            return 0
        if piv != i:
            mat[i], mat[piv] = mat[piv], mat[i]
            det = -det % mod
        inv = pow(mat[i][i], mod - 2, mod)
        det = det * mat[i][i] % mod
        for r in range(i + 1, n):
            factor = mat[r][i] * inv % mod
            if factor:
                for c in range(i, n):
                    mat[r][c] = (mat[r][c] - factor * mat[i][c]) % mod
    return det % mod

matには$I+L$（mod p済みの値）を渡す。

模範解答 (Python)

import sys

MOD = 998244353


def det_mod(mat, n, mod):
    det = 1
    for i in range(n):
        piv = -1
        for r in range(i, n):
            if mat[r][i] % mod != 0:
                piv = r
                break
        if piv == -1:
            return 0
        if piv != i:
            mat[i], mat[piv] = mat[piv], mat[i]
            det = (-det) % mod
        inv = pow(mat[i][i], mod - 2, mod)
        det = det * mat[i][i] % mod
        for r in range(i + 1, n):
            factor = mat[r][i] * inv % mod
            if factor:
                row_r = mat[r]
                row_i = mat[i]
                for c in range(i, n):
                    row_r[c] = (row_r[c] - factor * row_i[c]) % mod
    return det % mod


def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1

    lap = [[0] * n for _ in range(n)]
    for _ in range(m):
        a = int(data[idx]) - 1; idx += 1
        b = int(data[idx]) - 1; idx += 1
        lap[a][a] += 1
        lap[b][b] += 1
        lap[a][b] -= 1
        lap[b][a] -= 1

    mat = [[(1 if i == j else 0) + lap[i][j] for j in range(n)] for i in range(n)]
    for i in range(n):
        for j in range(n):
            mat[i][j] %= MOD

    print(det_mod(mat, n, MOD))


main()

計算量: ガウスの消去法は $O(N^3)$。$N \le 500$ なので約 $1.25\times10^8$ 回の演算。

Step-by-Step 解説

1ラプラシアン行列の構築
各辺$(a,b)$について対角成分を+1、非対角成分を-1する（通常の行列木定理と同じ）。

2I+L の構成
対角成分に1を足すだけで$I+L$が得られる。

3mod上のガウス消去法
ピボットの割り算はモジュラ逆元をかけることで実現。行の入れ替えごとに符号を反転させる。

4結果の解釈
$\det(I+L)\bmod p$がそのまま全域根付き森の個数となる。非連結グラフでも定理はそのまま成立する。

よくあるミス

ミス	原因	正しい書き方
行列木定理と同様に1行1列を除いた余因子を計算してしまう	Matrix-Forest定理との違いの混同	余因子を取らず$\det(I+L)$をそのまま使う
対角成分に1を足し忘れる	$L$の行列式（常に0）を計算してしまう	`mat[i][i] = 1 + lap[i][i]`を忘れずに構成
行の入れ替え時に符号反転を忘れる	行列式の基本性質の見落とし	`piv != i`の場合は`det = -det % mod`
ピボットが0の判定を非mod値で行ってしまう	mod演算の性質の誤解	必ず`% mod`した上で0判定する

次のステップ

発展: 重み付きグラフへの一般化（ラプラシアンに重みを反映するだけで同じ定理が成立）
発展: 特定の頂点集合を根候補から除外した場合の数え上げ
次回予告: Dilworthの定理（最小鎖分割・DAG最小パス被覆）

自己評価

完全理解おおむね理解要復習

Day 095-Q4 — Matrix-Forest定理（全域森数え上げ）

問題