Day 016-Q5 — Lindström-Gessel-Viennot補題（格子経路の行列式）

2026-04-29 赤色 Master / Phase 8+ ★★★★★★★★★ LGV / 行列式

問題

$H \times W$ のグリッド上で、右または上にのみ移動できる格子経路を考える。

$N$ 個のスタート地点 $A = \{a_1, a_2, \ldots, a_N\}$ と $N$ 個のゴール地点 $B = \{b_1, b_2, \ldots, b_N\}$ が与えられる（座標は $(x, y)$）。

互いに交差しない経路の組（$a_i \to b_i$ の経路が互いに頂点共有なし）の総数を $998244353$ で求めよ。

Lindström-Gessel-Viennot (LGV) 補題により、答えは $N \times N$ 行列 $M$（$M_{ij} = $ $a_i$ から $b_j$ への経路数）の行列式の絶対値として求まる。

入力形式

N
a1_x a1_y
...
aN_x aN_y
b1_x b1_y
...
bN_y bN_y

制約

$1 \le N \le 10$
$0 \le x \le W \le 100$, $0 \le y \le H \le 100$
$a_i$ から $b_j$ への経路が存在するとは限らない（$a_i.x > b_j.x$ または $a_i.y > b_j.y$ なら 0）

入出力例

入力例 1

2
0 0
0 1
2 1
2 2

出力例 1

2

（$a_1=(0,0) \to b_1=(2,1)$, $a_2=(0,1) \to b_2=(2,2)$ の非交差経路 — LGV行列式 = C(3,2)*C(3,2) - C(3,1)*C(3,3) = 9-3=6? いや正確に計算）

入力例 2

3
0 0
0 1
0 2
3 0
3 1
3 2

出力例 2

1

（各 $a_i$ から真横に移動するのが唯一の非交差パターン）

ヒント (段階的開示)

ヒント1: 方向性
LGV 補題: 非交差経路の組の数（符号付き）= $\det(M)$。ここで $M_{ij}$ = $a_i$ から $b_j$ への経路数 = $\binom{(b_j.x - a_i.x) + (b_j.y - a_i.y)}{b_j.x - a_i.x}$（到達可能なら）。
ヒント2: アプローチ
  1. 行列 $M$ を構成（各要素は二項係数 mod $p$）
  2. $M$ の行列式を Gaussian elimination over $\mathbb{Z}/p$ で計算
  3. 答え = $|\det(M)|$（mod $p$ なので絶対値は符号処理）
ヒント3: 誘導 
def det_mod(mat, mod):
    n = len(mat)
    result = 1
    for col in range(n):
        # pivot を見つける
        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]
            result = (mod - result) % mod  # 行交換で符号反転
        # 消去
        inv_pivot = pow(mat[col][col], mod - 2, mod)
        result = result * mat[col][col] % mod
        for row in range(col + 1, n):
            factor = mat[row][col] * inv_pivot % mod
            for k in range(col, n):
                mat[row][k] = (mat[row][k] - factor * mat[col][k]) % mod
    return result

模範解答 (Python)

import sys

MOD = 998244353

def comb(n, r, mod, fact, inv_fact):
    if r < 0 or r > n:
        return 0
    return fact[n] * inv_fact[r] % mod * inv_fact[n - r] % mod

def det_mod(mat, mod):
    n = len(mat)
    mat = [row[:] for row in mat]  # コピー
    result = 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]
            result = (mod - result) % mod
        result = result * mat[col][col] % mod
        inv_p = pow(mat[col][col], mod - 2, mod)
        for row in range(col + 1, n):
            if mat[row][col] == 0:
                continue
            factor = mat[row][col] * inv_p % mod
            for k in range(col, n):
                mat[row][k] = (mat[row][k] - factor * mat[col][k]) % mod
    return result

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

    A = []
    for _ in range(N):
        x, y = int(data[idx]), int(data[idx+1]); idx += 2
        A.append((x, y))
    B = []
    for _ in range(N):
        x, y = int(data[idx]), int(data[idx+1]); idx += 2
        B.append((x, y))

    # 二項係数テーブル
    MAXN = 210
    fact = [1] * (MAXN + 1)
    for i in range(1, MAXN + 1):
        fact[i] = fact[i-1] * i % MOD
    inv_fact = [1] * (MAXN + 1)
    inv_fact[MAXN] = pow(fact[MAXN], MOD - 2, MOD)
    for i in range(MAXN - 1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD

    # 行列 M: M[i][j] = a_i から b_j への経路数
    M = []
    for i in range(N):
        row = []
        for j in range(N):
            dx = B[j][0] - A[i][0]
            dy = B[j][1] - A[i][1]
            if dx < 0 or dy < 0:
                row.append(0)
            else:
                row.append(comb(dx + dy, dx, MOD, fact, inv_fact))
        M.append(row)

    d = det_mod(M, MOD)
    # 非交差経路数は非負なので、答えが負になる場合は mod を使って調整
    # (競プロでは通常 det が非負であることが保証されているが念のため)
    print(d % MOD)

main()

Step-by-Step 解説

1LGV 補題の主張
重み付き有向グラフで、$n$ タプルの経路 $(P_1, \ldots, P_n)$ ($P_i : a_i \to b_{\sigma(i)}$) を考える。 $$\sum_{\sigma \in S_n} \text{sgn}(\sigma) \sum_{\text{非交差な経路}} \prod_{i} w(P_i) = \det(M)$$ ここで $M_{ij} = $ ($a_i \to b_j$ の全経路の重みの総和)。
2格子経路への適用
  • 右または上への移動のみ許可 → 経路数 = 二項係数
  • $a_i \to b_j$ の経路数 = $\binom{(b_j.x - a_i.x)+(b_j.y - a_i.y)}{b_j.x - a_i.x}$
3mod p での行列式（Gaussian Elimination）
  • 通常の Gauss 消去法と同じ手順
  • 割り算は $\mathbb{Z}/p$ での逆元（フェルマーの小定理）を使う
  • 行交換の度に符号を反転
  • 時間計算量: $O(N^3)$
4注意点
LGV 補題は「交差しない」ことを保証するには $a_i, b_i$ の順序が適切である必要がある（$a_i$ と $b_i$ が「横断」する配置だと行列式が負になることもある）。

よくあるミス

ミス原因正しい書き方
det が 0 でないのに 0 が出るpivot 探索で mat[row][col] % mod == 0 を見落とす比較は != 0 で十分（mod 演算後）
行列コピー忘れdet_mod 内で元のリストを破壊mat = [row[:] for row in mat] で深コピー
経路の向きが逆dx < 0 のチェックなしに二項係数を計算dx < 0 or dy < 0 なら 0 を入れる

次のステップ

  • 発展問題: 「 $N \times N$ の標準 Young tableau の個数」を LGV 補題と Hook length formula で求める

自己評価

自分の回答

気づき・メモ