cp_library/math/linalg/mat/mod/mat_pow_fn.py

• View this file on GitHub
• Last update: 2025-03-30 20:17:47+09:00

Depends on

• cp_library/math/linalg/mat/mat_id_fn.py
• cp_library/math/linalg/mat/mod/mat_mul_fn.py

Verified with

• test/library-checker/linear-algebra/pow_of_matrix_matpow.test.py

Code

import cp_library.math.mod.__header__

def mat_pow(A,K,mod):
    N = len(A)
    ret = A if K & 1 else mat_id(N)
    for i in range(1,K.bit_length()):
        A = mat_mul(A,A,mod) 
        if K >> i & 1:
            ret = mat_mul(ret,A,mod) 
    return ret 

from cp_library.math.linalg.mat.mod.mat_mul_fn import mat_mul
from cp_library.math.linalg.mat.mat_id_fn import mat_id

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''

def mat_pow(A,K,mod):
    N = len(A)
    ret = A if K & 1 else mat_id(N)
    for i in range(1,K.bit_length()):
        A = mat_mul(A,A,mod) 
        if K >> i & 1:
            ret = mat_mul(ret,A,mod) 
    return ret 


def mat_mul(A,B,mod):
    assert len(A[0]) == len(B)
    R = [[0]*len(B[0]) for _ in range(len(A))] 
    for i,Ri in enumerate(R):
        for k,Aik in enumerate(A[i]):
            for j,Bkj in enumerate(B[k]):
                Ri[j] = (Ri[j] + Aik*Bkj) % mod
    return R



def mat_id(N):
    return [[int(i==j) for j in range(N)] for i in range(N)]

Back to top page