expansion/$tests/math/mat_pow.test.py

View this file on GitHub
Last update: 2023-07-23 08:45:17+09:00
Problem: https://yukicoder.me/problems/no/1750
Link: View error logs on GitHub Actions

Code

# verification-helper: PROBLEM https://yukicoder.me/problems/no/1750
from pathlib import Path
import sys

sys.path.append(str(Path(__file__).resolve().parent.parent.parent.parent))


def mat_exp(A, B, n, MOD=-1):
    le = len(A)
    while n > 0:
        if n & 1:
            C = [0] * le
            for i in range(le):
                for j in range(le):
                    C[i] += A[i][j] * B[j]
                    if MOD != -1:
                        C[i] %= MOD
            B = C
        C = [[0] * le for _ in range(le)]
        for i in range(le):
            for k in range(le):
                for j in range(le):
                    C[i][j] += A[i][k] * A[k][j]
                    if MOD != -1:
                        C[i][j] %= MOD
        A = C
        n >>= 1

    return B


n, m, T = map(int, input().split())
A = [[0] * n for _ in range(n)]
B = [0] * n
B[0] = 1
for _ in range(m):
    s, t = map(int, input().split())
    A[s][t] = 1
    A[t][s] = 1

B = mat_exp(A, B, T, 998244353)
print(B[0])

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 81, in _render_source_code_stat
    bundled_code = language.bundle(
                   ^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/python.py", line 108, in bundle
    raise NotImplementedError
NotImplementedError