概要

各辺に重み（魔力値）がある有向グラフで、「ちょうど \(K\) 本の道を通って 1 から \(N\) へ行く経路」すべてについて、辺重みの積を合計した値を求めます。これは重み付き隣接行列の \(K\) 乗の \((1,N)\) 成分として計算できます。

考察

経路 \(v_0=1, v_1, \dots, v_K=N\) の総魔力は $\(\prod_{j=1}^{K} W(v_{j-1}, v_j)\)$ で、求めたいのはその総和です。

ここで重要な観察は、「長さ（辺数）がちょうど \(K\) の経路に対する “積の和” は、行列累乗で自然に表現できる」という点です。

• \(N \le 100\) なので \(N\) 次の行列を扱えます。
• しかし \(K \le 10^9\) と非常に大きいので、
  • 素朴に DP を \(dp[t][v]\)（長さ \(t\) で頂点 \(v\) にいるときの総和）として $\(dp[t+1][v] = \sum_u dp[t][u]\cdot W(u,v)\)\( を \)t=0\( から \)K\( まで回すと、\)O(KM)\(（最悪 \)10^9$ オーダー）になり TLE です。

そこで、遷移を行列としてまとめ、繰り返し二乗法で \(K\) 乗を \(O(\log K)\) 回の行列積で求めます。

アルゴリズム

1. 重み付き隣接行列を作る

\(N \times N\) 行列 \(A\) を - 道 \(u \to v\) の魔力値が \(W(u,v)\) なら \(A[u][v]=W(u,v)\) - 道がなければ \(A[u][v]=0\) （すべて \(\bmod\ 998244353\) で扱う）

2. 「行列の積」が「経路の結合」になる理由

行列積 \(C=AB\) の成分は $\(C[i][j]=\sum_{k=1}^{N} A[i][k]\cdot B[k][j]\)$ です。

これを経路として見ると、 - \(A[i][k]\)：\(i \to k\) へ行く “何らかの方法” の重みの総和 - \(B[k][j]\)：\(k \to j\) へ行く “何らかの方法” の重みの総和 - それらをつなげると（経由点 \(k\) を固定したとき）重みは 積 になり、 - 経由点 \(k\) を全探索して足し合わせるので 和 になります。

特に \(A\) を「長さ 1 の経路の重み」とすると、 - \(A^2[i][j]\) は「長さ 2 の経路」についての “積の和” - 一般に \(A^K[i][j]\) は「長さ \(K\) の経路」についての “積の和” を表します。

よって答えは $\( (A^K)[1][N] \)\( （実装では 0-index にして \)(A^K)[0][N-1]$）です。

3. 繰り返し二乗法（高速累乗）で \(A^K\) を計算

• 初期値：\(res = I\)（単位行列）
• \(K\) の各ビットを見ながら
  • ビットが 1 なら \(res = res \cdot A\)
  • \(A = A \cdot A\)
  • \(K\) を右シフト として \(O(\log K)\) 回の行列積で \(A^K\) を得ます。

計算量

• 時間計算量: \(O(N^3 \log K)\)
  （行列積が \(O(N^3)\)、それを \(O(\log K)\) 回）
• 空間計算量: \(O(N^2)\)
  （行列を数枚保持）

実装のポイント

• 法 \(998244353\) で常に剰余を取る：重みや積・和が巨大になるため。

• 頂点番号は入力が 1-index なので、実装では 0-index に直す（\(u-1, v-1\)）。

• 行列積は $\(res[i][j] \mathrel{+}= A[i][k]\cdot B[k][j]\)\( を回しますが、コードでは `if aik:` で **\)A[i][k]=0$ のとき内側をスキップ**し、少しだけ高速化しています。

• 道が存在しない場合の \(A[u][v]=0\) は、「その 1 手の選択肢がない」ことを自然に表せます。経路が 1 つもなければ最終的に答えは 0 になります。

  ソースコード

import sys

MOD = 998244353

def mat_mul(A, B, n):
    rn = range(n)
    res = [[0] * n for _ in rn]
    for i in rn:
        Ai = A[i]
        resi = res[i]
        for k in rn:
            aik = Ai[k]
            if aik:
                Bk = B[k]
                for j in rn:
                    resi[j] += aik * Bk[j]
        for j in rn:
            resi[j] %= MOD
    return res

def mat_pow(A, e, n):
    rn = range(n)
    res = [[0] * n for _ in rn]
    for i in rn:
        res[i][i] = 1
    while e > 0:
        if e & 1:
            res = mat_mul(res, A, n)
        e >>= 1
        if e:
            A = mat_mul(A, A, n)
    return res

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = iter(data)
    N = next(it)
    M = next(it)
    K = next(it)

    A = [[0] * N for _ in range(N)]
    for _ in range(M):
        u = next(it) - 1
        v = next(it) - 1
        w = next(it) % MOD
        A[u][v] = w

    AK = mat_pow(A, K, N)
    print(AK[0][N - 1] % MOD)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。