結果

問題 No.3226 2×2行列累乗
ユーザー Mogobon
提出日時 2025-08-08 22:18:23
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,260 bytes
コンパイル時間 522 ms
コンパイル使用メモリ 11,904 KB
実行使用メモリ 31,824 KB
最終ジャッジ日時 2025-08-08 22:18:33
合計ジャッジ時間 8,910 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 4 TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

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)}")
        return matrix_pow(X2, n//2, cnt)
    else:
        cnt += 1
        # print(f"cnt={cnt}")
        # print(f"in: id(cnt)={id(cnt)}")
        return matrix_mult(X, matrix_pow(X, n-1, cnt))

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