結果
問題 |
No.3226 2×2行列累乗
|
ユーザー |
|
提出日時 | 2025-08-08 21:36:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 41 ms / 2,000 ms |
コード長 | 1,008 bytes |
コンパイル時間 | 201 ms |
コンパイル使用メモリ | 82,840 KB |
実行使用メモリ | 54,296 KB |
最終ジャッジ日時 | 2025-08-08 21:36:47 |
合計ジャッジ時間 | 2,246 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
import sys input = lambda :sys.stdin.readline()[:-1] ni = lambda :int(input()) na = lambda :list(map(int,input().split())) yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES") no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO") ####################################################################### def mat_mul(A,B): return [[(A[0][0] * B[0][0] + A[0][1] * B[1][0]) % mod, (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % mod], [(A[1][0] * B[0][0] + A[1][1] * B[1][0]) % mod, (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % mod]] def mat_pow(A, x): assert len(A)==len(A[0]) n = len(A) R = [[0 for j in range(n)]for i in range(n)] for i in range(n): R[i][i] = 1 while x > 0: if x&1: R = mat_mul(R, A) A = mat_mul(A,A) x >>= 1 return R A = [na(), na()] S, T = na() N, mod = na() B = mat_pow(A, N) R = B[0][0] * S + B[0][1] * T U = B[1][0] * S + B[1][1] * T print(R % mod, U % mod)