結果
問題 | No.526 フィボナッチ数列の第N項をMで割った余りを求める |
ユーザー |
![]() |
提出日時 | 2020-03-29 21:43:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 37 ms / 2,000 ms |
コード長 | 714 bytes |
コンパイル時間 | 316 ms |
コンパイル使用メモリ | 82,156 KB |
実行使用メモリ | 54,456 KB |
最終ジャッジ日時 | 2025-01-02 15:49:55 |
合計ジャッジ時間 | 1,506 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
# 内積 def product(a,b,mod=None): if mod is None: return sum(map(lambda x:x[0]*x[1], zip(a,b))) else: return sum(map(lambda x:x[0]*x[1]%mod, zip(a,b)))%mod # 行列積 def mul_of_matrix(a,b,mod=None): bt = [[b[i][j] for i in range(len(b))] for j in range(len(b[0]))] return [[product(ai,bj,mod) for bj in bt] for ai in a] # 行列累乗 def pow_of_matrix(a,n,mod=None): res = [[1 if i == j else 0 for j in range(len(a))] for i in range(len(a))] while n: if n&1: res = mul_of_matrix(res,a,mod) a = mul_of_matrix(a,a,mod) n >>= 1 return res n,m = map(int, input().split()) mat = pow_of_matrix([[1,1],[1,0]],n-1,m) print(mat[1][0])