Overview

In a directed graph where each edge has a weight (magic value), we want to compute the sum of products of edge weights over all paths from vertex 1 to vertex \(N\) that use exactly \(K\) edges. This can be computed as the \((1,N)\) entry of the \(K\)-th power of the weighted adjacency matrix.

Analysis

The total magic of a path \(v_0=1, v_1, \dots, v_K=N\) is $\(\prod_{j=1}^{K} W(v_{j-1}, v_j)\)$ and we want the sum of this over all such paths.

The key observation here is that “the sum of products over paths of exactly length (number of edges) \(K\) can be naturally expressed using matrix exponentiation.”

• Since \(N \le 100\), we can work with \(N \times N\) matrices.
• However, \(K \le 10^9\) is very large, so:
  • A naive DP approach with \(dp[t][v]\) (the sum when at vertex \(v\) after \(t\) steps): $\(dp[t+1][v] = \sum_u dp[t][u]\cdot W(u,v)\)\( iterated from \)t=0\( to \)K\( would be \)O(KM)\( (on the order of \)10^9$ in the worst case), resulting in TLE.

Instead, we express the transition as a matrix and use repeated squaring (binary exponentiation) to compute the \(K\)-th power in \(O(\log K)\) matrix multiplications.

Algorithm

1. Construct the weighted adjacency matrix

Define an \(N \times N\) matrix \(A\) as: - If there is an edge \(u \to v\) with magic value \(W(u,v)\), then \(A[u][v]=W(u,v)\) - If there is no edge, then \(A[u][v]=0\)

(All operations are performed \(\bmod\ 998244353\))

2. Why matrix multiplication corresponds to path concatenation

The entries of the matrix product \(C=AB\) are: $\(C[i][j]=\sum_{k=1}^{N} A[i][k]\cdot B[k][j]\)$

Interpreting this in terms of paths: - \(A[i][k]\): the sum of weights over “all methods” of going from \(i \to k\) - \(B[k][j]\): the sum of weights over “all methods” of going from \(k \to j\) - Concatenating these (for a fixed intermediate vertex \(k\)), the weights become a product, - and summing over all possible intermediate vertices \(k\) gives a sum.

In particular, if \(A\) represents “weights of paths of length 1,” then: - \(A^2[i][j]\) represents the “sum of products” over paths of length 2 - In general, \(A^K[i][j]\) represents the “sum of products” over paths of length \(K\)

Therefore, the answer is $\( (A^K)[1][N] \)\( (In implementation with 0-indexing, this is \)(A^K)[0][N-1]$).

3. Compute \(A^K\) using repeated squaring (fast exponentiation)

• Initial value: \(res = I\) (identity matrix)
• Examine each bit of \(K\):
  • If the bit is 1, then \(res = res \cdot A\)
  • \(A = A \cdot A\)
  • Right-shift \(K\)

This yields \(A^K\) in \(O(\log K)\) matrix multiplications.

Complexity

• Time complexity: \(O(N^3 \log K)\)
  (Each matrix multiplication is \(O(N^3)\), performed \(O(\log K)\) times)
• Space complexity: \(O(N^2)\)
  (Storing a few matrices)

Implementation Notes

• Always take the remainder modulo \(998244353\): because weights, products, and sums can become extremely large.

• Vertex indices in the input are 1-indexed, so in the implementation, convert to 0-indexed (\(u-1, v-1\)).

• For matrix multiplication: $\(res[i][j] \mathrel{+}= A[i][k]\cdot B[k][j]\)\( In the code, `if aik:` is used to **skip the inner loop when \)A[i][k]=0$**, providing a slight speedup.

• When no edge exists, \(A[u][v]=0\) naturally represents “there is no choice for that step.” If no path exists at all, the final answer will be 0.

  Source Code

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()

---

This editorial was generated by gpt-5.2-high.