Day 057-Q4 — 包除原理 + 格子路DP（禁止点制約）

問題

$W \times H$ のグリッドの左下 $(0,0)$ から右上 $(W, H)$ へ、右方向 $(+1,0)$ または上方向 $(0,+1)$ の移動のみで進む格子路を考える。

$K$ 個の「禁止点」$\{(x_1,y_1), \ldots, (x_K,y_K)\}$ が与えられ、これらの点を一切通らない格子路の総数を $\bmod{998244353}$ で求めよ。

入出力例

4 4 2
2 2
3 1

48

通常の格子路数 $\binom{8}{4}=70$。禁止点 $(2,2)$ と $(3,1)$ を通る路を包除原理で除いた結果 = 48。

概念図: 禁止点DP の帰納構造

ヒント（段階的開示）

forbidden.sort(key=lambda p: (p[0]+p[1], p[0]))
K = len(forbidden)
f = [0] * K

for i in range(K):
    xi, yi = forbidden[i]
    f[i] = comb(xi+yi, xi)
    for j in range(i):
        xj, yj = forbidden[j]
        if xj <= xi and yj <= yi:  # j が i に先行
            f[i] = (f[i] - f[j] * comb((xi-xj)+(yi-yj), xi-xj)) % MOD

ans = comb(W+H, W)
for i in range(K):
    xi, yi = forbidden[i]
    ans = (ans - f[i] * comb((W-xi)+(H-yi), W-xi)) % MOD

模範解答 (Python)

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

def solve():
    W, H, K = map(int, input().split())
    MAXN = W + H + 10

    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

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

    def ways(ax, ay, bx, by):
        dx, dy = bx - ax, by - ay
        if dx < 0 or dy < 0:
            return 0
        return comb(dx + dy, dx)

    forbidden = []
    for _ in range(K):
        x, y = map(int, input().split())
        forbidden.append((x, y))

    forbidden.sort(key=lambda p: (p[0] + p[1], p[0]))

    f = [0] * K
    for i in range(K):
        xi, yi = forbidden[i]
        f[i] = ways(0, 0, xi, yi)
        for j in range(i):
            xj, yj = forbidden[j]
            if xj <= xi and yj <= yi:
                f[i] = (f[i] - f[j] * ways(xj, yj, xi, yi)) % MOD

    ans = ways(0, 0, W, H)
    for i in range(K):
        xi, yi = forbidden[i]
        ans = (ans - f[i] * ways(xi, yi, W, H)) % MOD

    print(ans % MOD)

solve()

Step-by-Step 解説

Step 1: 格子路の基本公式

$(0,0)$ から $(W,H)$ への格子路数は $\binom{W+H}{W}$。右に $W$ 回・上に $H$ 回の移動順序の選び方。

Step 2: 禁止点 DP の設計

「禁止点を一切通らない経路数 $f(p)$」を最初に通る禁止点で分類する帰納式を作る。点 $p$ に先行する禁止点（$x_q \le x_p$ かつ $y_q \le y_p$）を通る経路は $f(q)$ を使って計算。

Step 3: ソートの必要性

$i$ の計算に $j < i$ の $f(j)$ が必要なので、禁止点を「$p$ に先行する $q$ が常に小さいインデックスになる」順序でソートする。$(x+y)$ 順がこれを満たす。

Step 4: 最終答えの計算

$(0,0)$ から $(W,H)$ への全経路から、「少なくとも1つの禁止点を通る経路」を除く。

計算量

よくあるミス

次のステップ

• 発展: $K$ 本の格子路が互いに交差しない数え上げ（Lindström-Gessel-Viennot 補題）
• 類題: AtCoder ABC 155 F, Codeforces 559E
• 応用: ヤング図形の標準タブロー数（フック長公式との関係）

自己評価