Day 062-Q2 — 行列木定理拡張（重み付き全域木数え上げ mod p）

2026-06-15 赤色 Master / Phase 8+ ★★★★★★★★★ Kirchhoff / Laplacian / 行列式 mod p / 全域木

問題

$N$ 頂点 $M$ 辺の重み付き連結無向グラフが与えられる。辺 $i$ は頂点 $u_i, v_i$ を結び重みは $w_i > 0$。

各全域木の重みを構成辺の重みの積として、全ての全域木の重みの総和 $T(G)$ を $p = 998244353$ で割った余りを求めよ：

$$T(G) = \sum_{\text{全域木 } t} \prod_{e \in t} w_e \pmod{p}$$

制約

パラメータ範囲
$N$$2 \le N \le 400$
$M$$N-1 \le M \le N(N-1)/2$
$w_i$$1 \le w_i \le 10^9$
グラフ連結

入出力例

入力例 1

3 3
1 2 2
2 3 3
1 3 5

出力例 1

31

全域木3種: $\{e_{12},e_{23}\}$ 重み積$=6$、$\{e_{12},e_{13}\}=10$、$\{e_{23},e_{13}\}=15$。総和 $= 31$。

概念図: 重み付きLaplacian行列と余因子

入力グラフ (N=3) 1 2 3 2 3 5 重み付きLaplacian $L$ $L = \begin{pmatrix} 7 & -2 & -5 \\ -2 & 5 & -3 \\ -5 & -3 & 8 \end{pmatrix}$ 対角: $L[i][i] = \sum_j w_{ij}$ 非対角: $L[i][j] = -w_{ij}$ 行列木定理（重み付き版）: $T(G) = \det(L') \pmod{p}$ $L'$: $L$ の任意の 1 行 1 列を除いた $(N-1) \times (N-1)$ 小行列 余因子計算 (例) $L' = \begin{pmatrix} 7 & -2 \\ -2 & 5 \end{pmatrix}$ $\det(L') = 35 - 4 = 31$ ✓ mod p ガウス消去: 1. ピボット選択 2. 行スワップ（符号反転） 3. 逆元で消去 4. 対角積 = det

ヒント（段階的開示）

ヒント1: 方向性
行列木定理（Kirchhoff's theorem）の重み付き版。重み付きLaplacian行列の余因子（$(N-1)\times(N-1)$ 小行列式）が $T(G)$ に等しい。
ヒント2: アプローチ
  • $L[i][i] = \sum_j w_{ij}$（頂点 $i$ に隣接する辺の重み総和）
  • $L[i][j] = -w_{ij}$（辺 $(i,j)$ の重み、符号を反転）
  • $T(G) = \det(L')$ で $L'$ は $L$ の最後の行・列を除いた $(N-1)\times(N-1)$ 行列
  • mod $p$ でガウス消去を行う（$p$ が素数なので逆元が存在）
ヒント3: コード骨格 
MOD = 998244353
def modinv(a): return pow(a, MOD-2, MOD)

def det_mod(mat):
    n = len(mat); res = 1
    for col in range(n):
        pivot = next((r for r in range(col,n) if mat[r][col]%MOD), -1)
        if pivot == -1: return 0
        mat[col], mat[pivot] = mat[pivot], mat[col]
        if col != pivot: res = (-res) % MOD
        res = res * mat[col][col] % MOD
        inv = modinv(mat[col][col])
        for row in range(col+1, n):
            f = mat[row][col] * inv % MOD
            for k in range(col, n):
                mat[row][k] = (mat[row][k] - f*mat[col][k]) % MOD
    return res

模範解答 (Python)

import sys
input = sys.stdin.readline

MOD = 998244353

def modinv(a, m=MOD):
    return pow(a, m - 2, m)

def det_mod(mat, mod):
    n = len(mat)
    res = 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:
            return 0
        mat[col], mat[pivot] = mat[pivot], mat[col]
        if col != pivot:
            res = (-res) % mod
        res = res * mat[col][col] % mod
        inv = modinv(mat[col][col])
        for row in range(col + 1, n):
            if mat[row][col] % mod == 0:
                continue
            factor = mat[row][col] * inv % mod
            for k in range(col, n):
                mat[row][k] = (mat[row][k] - factor * mat[col][k]) % mod
    return res % mod

def main():
    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 = [row[:-1] for row in L[:-1]]
    print(det_mod(sub, MOD))

main()

Step-by-Step 解説

Step 1: 重み付きLaplacian行列の構築

$L[i][i] = \sum_{j \sim i} w_{ij}$、$L[i][j] = -w_{ij}$。各行の和は0（全域木の重みを保存する性質）。行列は対称・半正定値・ランク $N-1$（連結グラフ）。

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

素数 $p$ の剰余体 $\mathbb{F}_p$ 上での行列式計算。各ピボット要素の逆元を $a^{p-2} \bmod p$（フェルマーの小定理）で求め、下三角部分を消去する。行スワップで符号を管理。計算量 $O(N^3)$。

Step 3: 余因子の選択

任意の1行1列を除いた $(N-1)\times(N-1)$ 部分行列の行列式が余因子となる（行列木定理の核心）。計算上は最後の行・列を除くことが多い（インデックス上便利）。

よくあるミス

ミス原因正しい書き方
$L$ の符号ミス非対角要素を正で設定$L[i][j] = -w_{ij}$（負）
mod で負値が残るPython の % は非負だが減算後に負(val % MOD + MOD) % MOD または明示的に $+$ MOD
全体の行列式を使うランク不足で det=0$(N-1)\times(N-1)$ 小行列を使う

次のステップ

  • 発展問題: 有向グラフの全域木数え上げ（BEST定理: $t_G = t_w \cdot \prod \text{Euler circuits}$）
  • 関連: FKT アルゴリズム（平面グラフの完全マッチング数え上げ）
  • 応用: Laplacian 固有値と連結性・ランダムウォーク・電気抵抗の関係

自己評価