結果
問題 |
No.3226 2×2行列累乗
|
ユーザー |
|
提出日時 | 2025-08-08 22:03:46 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 49 ms / 2,000 ms |
コード長 | 840 bytes |
コンパイル時間 | 181 ms |
コンパイル使用メモリ | 82,908 KB |
実行使用メモリ | 54,492 KB |
最終ジャッジ日時 | 2025-08-08 22:03:49 |
合計ジャッジ時間 | 2,396 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
def dot(A, B): C = [[None for col in range(2)] for row in range(2)] for row in range(2): for col in range(2): # C[row][col]:= Aのrow行目とBのcol列目の内積 tmp = 0 for i in range(2): tmp += ((A[row][i]%K) * (B[i][col]%K))%K tmp %= K C[row][col] = tmp return C M = [list(map(int, input().split())) for row in range(2)] S, T = map(int, input().split()) N, K = map(int, input().split()) bin_N = bin(N) bin_N = bin_N[2:] bin_N = bin_N[::-1] if bin_N[0] == "1": A = M else: A = [[1, 0], [0, 1]] for i in range(1, len(bin_N)): M = dot(M, M) if bin_N[i] == "1": A = dot(A, M) R = A[0][0]*S + A[0][1]*T U = A[1][0]*S + A[1][1]*T print(R%K, U%K)