Day 057-Q2 — FFT × 多項式行列累乗（Cayley-Hamilton定理）

問題

$N$ 頂点の有向グラフ $G$（隣接行列 $\mathbf{A}$、辺重み全て 1）が与えられる。頂点 $s$ から頂点 $t$ へ ちょうど $K$ 辺を使って到達するパス数を $\bmod{998244353}$ で求めよ。

$K \le 10^{18}$ のため通常の行列累乗は遅い。Cayley-Hamilton 定理を利用して $O(N^3 + N^2 \log K)$ で解け。

入出力例

3 4 5 1 3
1 2
2 3
3 1
1 3

5

頂点 1→3 への長さ 5 のパスを数える。グラフは三角形 + 辺 1→3。

概念図: Cayley-Hamilton 定理の活用

ヒント（段階的開示）

def poly_mul_mod_p(f, g, p, mod):
    """f*g mod p（多項式）"""
    h = [0] * (len(f) + len(g) - 1)
    for i, fi in enumerate(f):
        for j, gj in enumerate(g):
            h[i+j] = (h[i+j] + fi * gj) % mod
    return poly_mod_op(h, p, mod)

def poly_pow_mod_p(base, exp, p, mod):
    result = [1]  # 定数多項式 1
    while exp:
        if exp & 1:
            result = poly_mul_mod_p(result, base, p, mod)
        base = poly_mul_mod_p(base, base, p, mod)
        exp >>= 1
    return result

# lambda の多項式表現 = [0, 1]
lam = [0, 1]
r = poly_pow_mod_p(lam, K, char_poly, MOD)

模範解答 (Python)

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

def mat_mul(A, B, mod=MOD):
    n = len(A)
    C = [[0]*n for _ in range(n)]
    for i in range(n):
        for k in range(n):
            if A[i][k] == 0: continue
            for j in range(n):
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod
    return C

def char_poly(A, mod=MOD):
    """Leverrier-Fadeev法で特性多項式 det(xI-A) の係数を計算"""
    n = len(A)
    p = [0] * (n + 1); p[n] = 1
    M = [[1 if i==j else 0 for j in range(n)] for i in range(n)]
    for k in range(1, n + 1):
        AM = mat_mul(A, M, mod)
        tr = sum(AM[i][i] for i in range(n)) % mod
        ck = (-tr * pow(k, mod-2, mod)) % mod
        p[n - k] = ck
        for i in range(n):
            AM[i][i] = (AM[i][i] + ck) % mod
        M = AM
    return p

def poly_mod_op(f, g, mod=MOD):
    f = list(f)
    dg = len(g) - 1
    g_inv = pow(g[-1], mod-2, mod)
    while len(f) > dg:
        if f[-1] == 0:
            f.pop(); continue
        c = f[-1] * g_inv % mod
        dd = len(f) - 1 - dg
        for i in range(len(g)):
            f[dd + i] = (f[dd + i] - c * g[i]) % mod
        while f and f[-1] == 0:
            f.pop()
    return f

def poly_mul(f, g, mod=MOD):
    if not f or not g: return []
    h = [0] * (len(f) + len(g) - 1)
    for i, fi in enumerate(f):
        if fi == 0: continue
        for j, gj in enumerate(g):
            h[i+j] = (h[i+j] + fi * gj) % mod
    return h

def poly_mul_mod_p(f, g, p, mod=MOD):
    return poly_mod_op(poly_mul(f, g, mod), p, mod)

def poly_pow_mod_p(base, exp, p, mod=MOD):
    result = [1]
    base = poly_mod_op(base[:], p, mod)
    while exp:
        if exp & 1:
            result = poly_mul_mod_p(result, base, p, mod)
        base = poly_mul_mod_p(base, base, p, mod)
        exp >>= 1
    return result

def solve():
    line = input().split()
    N, M, K = int(line[0]), int(line[1]), int(line[2])
    s, t = int(line[3])-1, int(line[4])-1

    A = [[0]*N for _ in range(N)]
    for _ in range(M):
        u, v = map(int, input().split())
        A[u-1][v-1] = 1

    p = char_poly(A)
    lam = [0, 1]
    r = poly_pow_mod_p(lam, K, p)
    while len(r) < N:
        r.append(0)

    powers = []
    cur = [[1 if i==j else 0 for j in range(N)] for i in range(N)]
    for _ in range(N):
        powers.append(cur)
        cur = mat_mul(cur, A)

    ans = 0
    for i in range(N):
        ans = (ans + r[i] * powers[i][s][t]) % MOD
    print(ans)

solve()

Step-by-Step 解説

Step 1: Cayley-Hamilton 定理

$N \times N$ 行列 $\mathbf{A}$ は自身の特性多項式 $p(\lambda) = \det(\lambda I - \mathbf{A})$ を満たす（$p(\mathbf{A}) = \mathbf{0}$）。よって $\mathbf{A}^K$ は $\mathbf{I}, \mathbf{A}, \ldots, \mathbf{A}^{N-1}$ の線形結合で表せる。

Step 2: Leverrier-Fadeev 法

$O(N^3)$ で特性多項式の全係数を計算する。各ステップで $c_k = -\mathrm{tr}(AM_{k-1})/k$ を使う。

Step 3: 多項式繰り返し二乗法

$\lambda$ を「多項式 $[0, 1]$」として繰り返し二乗法。各ステップで $p(\lambda)$ で割った余りを取る。$O(N^2 \log K)$。

Step 4: 線形結合

$r = [r_0, \ldots, r_{N-1}]$ を用いて $\mathrm{ans} = \sum r_i [\mathbf{A}^i]_{s,t}$ を計算。

計算量

よくあるミス

次のステップ

• 発展: Berlekamp-Massey + Kitamasa 法との統一視点（線形漸化式の N 項目高速計算）
• 類題: AtCoder AGC005E, Codeforces 1528F
• 応用: 隣接行列の $K$ 乗を使った確率遷移（Markov chain）

自己評価