Day 060-Q3 — DAG + 行列累乗加速（レイヤー構造DP）

問題

$N$ 頂点 $M$ 辺の DAG（有向非巡回グラフ）が与えられる。各辺 $(u, v)$ に重み $w_{uv}$ がある。

頂点 $1$ から頂点 $N$ までのパスに含まれる辺の重みの 積の和 を $\mathrm{mod}\ 998244353$ で求めよ。

DAG はレイヤー構造：各レイヤー $K$ 頂点、辺はレイヤー $\ell \to \ell+1$ のみ。辺の重みパターンは全レイヤーで同一の $K \times K$ 遷移行列 $A$。$L$ が最大 $10^{18}$ なので行列累乗を用いよ。

入出力例

2 3
0 1
1 1

3

$K=2, L=3$。行列 $A = \begin{pmatrix}0&1\\1&1\end{pmatrix}$（フィボナッチ行列）。$A^3[0][0] = 3$（$F_4 = 3$）。

概念図: レイヤー構造 DAG と行列累乗

ヒント（段階的開示）

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

def mat_pow(A, n, K):
    result = [[1 if i==j else 0 for j in range(K)] for i in range(K)]
    while n:
        if n & 1: result = mat_mul(result, A, K)
        A = mat_mul(A, A, K)
        n >>= 1
    return result

模範解答 (Python)

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

MOD = 998244353

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

def mat_pow(A, n, K):
    result = [[1 if i == j else 0 for j in range(K)] for i in range(K)]
    while n > 0:
        if n & 1:
            result = mat_mul(result, A, K)
        A = mat_mul(A, A, K)
        n >>= 1
    return result

def main():
    K, L = map(int, input().split())
    A = []
    for _ in range(K):
        row = list(map(int, input().split()))
        A.append([x % MOD for x in row])

    if L == 0:
        print(1)
        return

    AL = mat_pow(A, L, K)
    print(AL[0][0])

main()

Step-by-Step 解説

Step 1: 問題の行列化

$L$ ステップのDAGパスの「辺重み積の和」= $A^L[0][0]$。行列積の $(i,j)$ 成分は「$i$ から $j$ への全パスの辺重み積の和」を表す。

Step 2: 繰り返し二乗法

$n = L$、行列サイズ $K \times K$。$\log_2(10^{18}) \approx 60$ なので最大60回の行列積（各 $O(K^3)$）。全体 $O(K^3 \log L)$。

Step 3: 初期状態と答え

始点が頂点0なので初期ベクトル $v_0 = (1, 0, \dots, 0)$。$A^L \cdot v_0$ の第0成分 = $A^L[0][0]$。

Step 4: 計算量の確認

$K = 50, L = 10^{18}$：$50^3 \times 60 = 7.5 \times 10^6$ 演算。十分高速。

よくあるミス

次のステップ

発展問題: 同じ構造で辺の重みが「加算」ではなく「(min, +)」半環に変わった場合（最短経路行列累乗）を考えよ。Bellman-Ford の行列累乗版で $O(K^3 \log L)$ が得られる。

自己評価