verify-check/AtCoder/Algo-math-054.py

• View this file on GitHub
• Last update: 2023-09-22 16:37:30+09:00

Code

# IGNORE

import numpy as np

def dot(A1, A2, N, mod):
    # N: 行列のサイズ
    A = np.zeros((N, N), dtype=int)
    for i in range(N):
        for j in range(N):
            for k in range(N):
                A[i][j] = (A[i][j] + (A1[i][k] * A2[k][j]) % mod) % mod
    return A

def pow_mat(A, K, N, mod):
    # A: 累乗する行列, k: 累乗数, n: 行列Aのサイズ
    P = np.eye(N, dtype=int)
    while K:
        if K & 1:
            P = dot(P, A, N, mod)
        A = dot(A, A, N, mod)
        K >>= 1
    return P

N = int(input())
mat = np.array([[1, 1], [1, 0]], dtype=int)
mod = 10**9
ans_matrix = pow_mat(mat, N-1, 2, mod)
ans = (ans_matrix[1][0] + ans_matrix[1][1]) % mod
print(ans)

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.1/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.1/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page