行列累乗
(expansion/math/mat_exp.py)

• View this file on GitHub
• Last update: 2023-07-16 19:41:28+09:00

概要

$n * n$ 行列 $A$，$n * 1$ 行列 $B$ が与えられたときに $A^k B$ を求めます ただし，B は 2 次元リストではなく， 1 次元リストで与えてください，($B’i = B{i, 0}$)

使い方

C = mat_exp(A, B, MOD)

Code

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

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

Back to top page