結果

問題 No.3226 2×2行列累乗
ユーザー Mogobon
提出日時 2025-08-08 22:26:46
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 1,520 bytes
コンパイル時間 207 ms
コンパイル使用メモリ 12,416 KB
実行使用メモリ 32,204 KB
最終ジャッジ日時 2025-08-08 22:27:09
合計ジャッジ時間 11,621 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24 RE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

def matrix_mult(A, B):
    H,W,K = len(A),len(B[0]),len(A[0])
    ans = [[0]*W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            for k in range(K):
                ans[i][j] += A[i][k]*B[k][j]
    return ans

def matrix_pow(X, n, cnt):
    # print(f"in: id(cnt)={id(cnt)}")
    if n == 1:
        return X
    elif n%2 == 0:
        X2 = matrix_mult(X,X)
        cnt += 1
        # print(f"cnt={cnt}")
        # print(f"in: id(cnt)={id(cnt)}")
        for i in range(2):
            for j in range(2):
                if X2[i][j]!=0:
                    X2[i][j]%=k
        return matrix_pow(X2, n//2, cnt)
    else:
        cnt += 1
        # print(f"cnt={cnt}")
        # print(f"in: id(cnt)={id(cnt)}")
        X2 = matrix_mult(X, matrix_pow(X, n-1, cnt))
        for i in range(2):
            for j in range(2):
                if X2[i][j]!=0:
                    X2[i][j]%=k
        return X2

M = [list(map(int,input().split()))for _ in range(2)]

s,t = map(int,input().split())

n,k=map(int,input().split())

M = matrix_pow(M, n, 0)

# explist = []
# u = n
# from math import log2
# while u > 1:
#     if u%2 == 0:
#         u //= 2
#         explist.append(int(log2(u)))
#     else:
#         o = u // 2
#         u = u - o
#         explist.append(int(log2(u)))

# explist.reverse()

# print(*explist)

# i = 0
# for e in explist:
#     M = multiple_matrix(M)

import numpy as np
M = np.array(M)
x = np.array([s,t])

ans = M@x

for i in range(2):
    print(ans[i]%k,end=" ")
0