Day 072-Q1 — 行列木定理拡張（重み付き全域木数え上げ・固有多項式）

問題

$N$ 頂点 $M$ 辺の無向重み付きグラフ $G$ が与えられる。辺 $e_i$ は頂点 $u_i$, $v_i$ を結び、重み $w_i \ge 1$ を持つ。

重み付き全域木の重みを辺重みの積と定義する。すなわち全域木 $T$ の重みは $\prod_{e \in T} w_e$ である。

全域木の重みの総和 $\displaystyle W = \sum_{T: \text{spanning tree}} \prod_{e \in T} w_e$ を $10^9+7$ で割った余りを求めよ。

これは Kirchhoff の行列木定理の重み付き版により、重み付きラプラシアン行列 $L$ の任意の $(i,i)$ 余因子として計算できる。

入出力例

4 5
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

252

3 3
1 2 1
2 3 1
1 3 1

3

概念図: 重み付き行列木定理

ヒント（段階的開示）

def mat_det_mod(mat, mod):
    n = len(mat)
    mat = [row[:] for row in mat]
    det = 1
    for col in range(n):
        pivot = -1
        for row in range(col, n):
            if mat[row][col] != 0:
                pivot = row; break
        if pivot == -1: return 0
        if pivot != col:
            mat[col], mat[pivot] = mat[pivot], mat[col]
            det = (-det) % mod
        det = det * mat[col][col] % mod
        inv = pow(mat[col][col], mod-2, mod)
        for row in range(col+1, n):
            ratio = mat[row][col] * inv % mod
            for c in range(col, n):
                mat[row][c] = (mat[row][c] - ratio * mat[col][c]) % mod
    return det

模範解答 (Python)

コピーimport sys
input = sys.stdin.readline

def solve():
    MOD = 10**9 + 7
    N, M = map(int, input().split())

    L = [[0] * N for _ in range(N)]
    for _ in range(M):
        u, v, w = map(int, input().split())
        u -= 1; v -= 1
        w %= MOD
        L[u][u] = (L[u][u] + w) % MOD
        L[v][v] = (L[v][v] + w) % MOD
        L[u][v] = (L[u][v] - w) % MOD
        L[v][u] = (L[v][u] - w) % MOD

    sub = [[L[i][j] for j in range(1, N)] for i in range(1, N)]
    n = N - 1
    mat = [row[:] for row in sub]
    det = 1
    for col in range(n):
        pivot = -1
        for row in range(col, n):
            if mat[row][col] % MOD != 0:
                pivot = row; break
        if pivot == -1:
            print(0); return
        if pivot != col:
            mat[col], mat[pivot] = mat[pivot], mat[col]
            det = (-det) % MOD
        det = det * mat[col][col] % MOD
        inv = pow(mat[col][col], MOD - 2, MOD)
        for row in range(col + 1, n):
            if mat[row][col] == 0: continue
            ratio = mat[row][col] * inv % MOD
            for c in range(col, n):
                mat[row][c] = (mat[row][c] - ratio * mat[col][c]) % MOD

    print(det % MOD)

solve()

Step-by-Step 解説

Step 1: 行列木定理の重み付き版

通常の行列木定理では全域木の個数を数えるが、重み付き版では辺に重み $w_e$ を割り当てることで全域木の重み積の総和を計算できる。

重み付きラプラシアン:

Step 2: 余因子行列式の計算

行列木定理により $W = \det(\tilde{L})$、ここで $\tilde{L}$ は $L$ から任意の1行1列を除いた行列。どの行列を選んでも値は同じ（行列木定理の基本性質）。

Step 3: mod p でのガウス消去

1. 行スワップごとに符号を反転（$\det \to -\det$）
2. ピボット元で他行を消去（逆元を使用）
3. 対角成分の積が行列式

時間計算量: $O(N^3)$

Step 4: 実装上の注意

• Pythonの % はmodulo演算子で負数も正規化される
• pow(x, MOD-2, MOD) でフェルマーの小定理による逆元計算
• $N = 500$ のとき $O(N^3) = 1.25 \times 10^8$ 操作、Pythonではやや重いので必要なら PyPy 推奨

よくあるミス

次のステップ

• 発展問題: 有向グラフの全域木数え上げ（BEST定理、オイラー路との関係）
• 固有値との関係（ラプラシアン固有値の積 = $N^{N-2}$ for 完全グラフ）
• 電気ネットワーク理論との接続（有効抵抗 = 行列木定理の比）

自己評価