Day 096-Q1 | BEST定理（有向オイラーグラフの閉路数え上げ）

問題

$N$ 頂点 $M$ 辺の有向多重グラフが与えられる。このグラフはオイラーグラフである（すべての頂点で入次数と出次数が等しく、次数が1以上の頂点全体は連結）ことが保証されている。

このグラフのオイラー閉路（すべての辺をちょうど1回ずつ使って開始点に戻る閉路）を、辺1本目を固定した上での辺の訪問順列として数える。すなわち、入力で1番目に与えられた辺から出発するオイラー閉路の異なる辺順序の総数を $998244353$ で割った余りを求めよ（この値は BEST定理により、どの辺を起点に固定しても同じ値になることが知られている）。

入力形式

N M
u_1 v_1
:
u_M v_M

$u_i \to v_i$ は $i$ 番目の有向辺（1-indexed）。自己ループは存在しない。

制約

$2 \le N \le 200$

$1 \le M \le 2000$

すべての頂点で入次数=出次数 $\ge 1$

次数1以上の頂点全体は連結

入出力例

入力例1

出力例1

頂点1↔2間に2本ずつの平行辺があり、2種類の異なるオイラー閉路（辺の使う順序の組み合わせ）が存在する。

概念図

ヒント（段階的開示）

ヒント1: 方向性

オイラー閉路を1本ずつ数え上げるのは辺の数が増えると指数的に困難になる。「グラフの全域木の本数」と「各頂点での辺の並べ方の自由度」の積として閉路数を表現できないかを考えよ。

ヒント2: アプローチ

BEST定理: オイラーグラフ $G$ において、固定した1本の辺から始まるオイラー閉路の数は $$ec(G) = tw(G) \times \prod_{v} (\deg(v) - 1)!$$ で与えられる。ここで $tw(G)$ は、任意の頂点 $r$ を根として「すべての辺が根に向かう」ように選んだ内向き全域木（in-arborescence）の本数であり、これは有向版の行列木定理（Tutte の定理）で $O(N^3)$ の行列式計算により求められる。$tw(G)$ の値はどの頂点を根に選んでも変わらない。

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

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

出次数ラプラシアン $L[i][i]=\text{outdeg}(i)$、$L[i][j]=-(\text{辺数})$ を作り、根の行・列を削除した部分行列にこの関数を適用する。

模範解答 (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

    outdeg = [0] * (n + 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
        outdeg[u + 1] += 1
        L[u][u] = (L[u][u] + 1) % MOD
        L[u][v] = (L[u][v] - 1) % MOD

    # 根 = 頂点0 の行・列を除いた (N-1)x(N-1) 行列
    size = n - 1
    mat = [[L[i][j] % MOD for j in range(1, n)] for i in range(1, n)]

    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:
            det = 0
            break
        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:
                for k in range(col, size):
                    mat[row][k] = (mat[row][k] - factor * mat[col][k]) % MOD

    tw = det % MOD

    max_deg = max(outdeg)
    fact = [1] * (max_deg + 1)
    for i in range(1, max_deg + 1):
        fact[i] = fact[i - 1] * i % MOD

    ans = tw
    for v in range(1, n + 1):
        ans = ans * fact[outdeg[v] - 1] % MOD

    print(ans % MOD)


solve()

計算量: ラプラシアン構築 $O(N^2+M)$、行列式計算（mod 上のガウス消去）$O(N^3)$。全体で $O(N^3+M)$。

Step-by-Step 解説

1出次数ラプラシアン行列の構築
各辺 $u\to v$ について対角成分 $L[u][u]$ に $+1$、非対角成分 $L[u][v]$ に $-1$ を加算（多重辺は自然に加算される）。

2根を1つ固定して行・列を削除
どの頂点を根に選んでも $tw(G)$ は変わらないため頂点0を根とし、その行・列を除いた $(N-1)\times(N-1)$ 部分行列を作る。

3mod 上のガウス消去で行列式を求める
ピボット行を探して行交換（符号反転）し、逆元で下三角を掃き出す。対角成分の積×符号が $tw(G)$。

4BEST定理の式に代入
$\prod_v (\deg(v)-1)!$ を階乗テーブルで求め $tw(G)$ と掛け合わせる。

よくあるミス

ミス	原因	正しい書き方
入次数ラプラシアンと出次数ラプラシアンを混同	BEST定理は出次数ラプラシアンの余因子を使う	対角成分は必ず出次数を使う
根の行・列削除でインデックスがずれる	1-indexed/0-indexed の混在	根を頂点0に固定し `range(1,n)` で一貫させる
次数0の頂点で `fact[-1]` エラー	孤立頂点が紛れ込む	制約で全頂点の次数1以上を保証する
行交換時の符号反転を忘れる	実数行列式のアルゴリズムをそのまま流用	行交換のたびに `det = (-det) % MOD`

次のステップ

発展: BEST定理は「固定辺から始まる閉路数」だが、無向オイラー閉路の数え上げには別の理論（Smith の定理）が必要
発展: $tw(G)$ が根に依存しないことを行列式の余因子展開の性質から証明する
次回予告: Bitset高速化二部マッチング（Kuhn法の整数ビット演算高速化）

自己評価

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

Day 096-Q1 — BEST定理（有向オイラーグラフの閉路数え上げ）

問題