Day 126-Q3 | 有向グラフの全域木数え上げ（Directed Matrix-Tree定理）

問題

$N$ 頂点 $M$ 辺の重み付き有向グラフが与えられる。頂点は $1$ から $N$ で番号付けられ、辺 $i$ は $u_i \to v_i$ に重み $w_i$ を持つ（多重辺・自己ループなし）。

頂点 $r$ を根とする根付き全域有向木（arborescence）とは、全ての辺が根から離れる向き（外向き）で、根以外の各頂点はちょうど1本の入次数を持つ全域木のことである。すべての根付き全域有向木について、木を構成する辺の重みの積の総和を $\bmod\ 998244353$ で求めよ（該当する木が1つも存在しなければ $0$ を出力）。

入力形式

N M r
u_1 v_1 w_1
...
u_M v_M w_M

制約

$2 \le N \le 300$

$0 \le M \le N(N-1)$

$1 \le r \le N$

$u_i \ne v_i$（自己ループなし）

$1 \le w_i < 998244353$

入出力例

入力例1

出力例1

根1からの全域木は「1→2,1→3」と「1→2,2→3」の2通り

入力例2

2 1 2
1 2 5

出力例2

辺が1→2のみで、頂点2を根とする外向き全域木は作れない

概念図

ヒント（段階的開示）

ヒント1（方向性）

無向グラフの全域木数え上げには Kirchhoff の行列木定理があり、ラプラシアン行列から任意の行・列を1組除いた小行列式が答えになる。有向グラフでは「根から出る木」と「根に入る木」で定理の形が変わるため、有向版のラプラシアン行列をどう定義するかがポイントになる。

ヒント2（アプローチ）

外向き木を数える場合、対角成分は「頂点$i$に入る辺の重み和」、非対角成分$(i,j)$は「$j\to i$の辺の重みの$-1$倍」とする有向ラプラシアン $L$ を定義する。この行列から根$r$に対応する行・列を同時に除いた $(N-1)\times(N-1)$ 小行列の行列式が、根$r$を根とする外向き全域木の重み積総和に一致する（Tutteの有向版Matrix-Tree定理）。

ヒント3（誘導）

行列式は$\bmod\ p$（$p=998244353$は素数）でのガウス消去法で計算する。ピボットが0の場合は下の行と交換し、交換のたびに符号を反転させる。

def det_mod(mat, size, mod):
    det = 1
    for col in range(size):
        pivot = -1
        for row in range(col, size):
            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, size):
            factor = mat[row][col] * inv % mod
            for k in range(col, size):
                mat[row][k] = (mat[row][k] - factor * mat[col][k]) % mod
    return det % mod

模範解答 (Python)

import sys

MOD = 998244353


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

    L = [[0] * n for _ in range(n)]
    for _ in range(m):
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1
        w = int(data[idx]) % MOD; idx += 1
        L[v][v] = (L[v][v] + w) % MOD
        L[v][u] = (L[v][u] - w) % MOD

    idxs = [i for i in range(n) if i != r]
    size = n - 1
    mat = [[L[idxs[i]][idxs[j]] % MOD for j in range(size)] for i in range(size)]

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

    if size == 0:
        print(1)
        return

    print(det_mod(mat, size, MOD) % MOD)


solve()

Step-by-Step 解説

1無向版との対比
無向グラフのKirchhoff行列木定理では、ラプラシアン $L=D-A$ の任意の1行1列を除いた行列式が全域木の数になる。有向グラフでは根に対応する行・列を選んで除く必要がある。

2有向ラプラシアンの構成
外向き全域木を数える場合、対角成分は「入次数の重み和」、非対角成分$(i,j)$は「$j\to i$の辺重みの$-1$倍」とする。

3根の行・列を除去して行列式
$N\times N$の$L$から根$r$の行と列を同時に除いた $(N-1)\times(N-1)$ 部分行列 $L_r$ の行列式が答え（Cauchy-Binetの公式を用いる帰納法で証明される）。

4mod上のガウス消去法
$998244353$は素数なので、フェルマーの小定理 pow(x, mod-2, mod) で逆元を求め、通常のガウス消去法を適用する。行交換のたびに符号を反転させる。

5計算量
行列サイズは$O(N)$、ガウス消去は$O(N^3)$なので全体で$O(N^3)$。$N\le300$なら十分高速。

よくあるミス

ミス	原因	正しい書き方
無向版と同じラプラシアンを使う	有向グラフの向きを無視	外向き木なら対角=入次数の重み和、非対角$(i,j)=-w(j\to i)$
除く行・列を根と無関係な位置にする	定理の適用条件を誤解	必ず根$r$に対応する行と列を同時に除く
mod上の行列式でピボットの符号処理を忘れる	行交換時の符号反転を省略	行を交換するたびに `det = -det mod p`
逆元計算に一般modでフェルマーの小定理を使う	mod素数性の確認を怠る	$998244353$が素数であることを前提に実装する（本問題では保証）

次のステップ

発展: 内向き木（全頂点から根へ向かう全域木）を数える場合の有向ラプラシアンの定義の違いを導出する
次回予告: Vantage-Point Tree（距離空間の最近傍探索・計量距離のみを用いた分割構造）

自己評価

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

Day 126-Q3 — 有向グラフの全域木数え上げ（Directed Matrix-Tree定理）

問題