結果
問題 |
No.526 フィボナッチ数列の第N項をMで割った余りを求める
|
ユーザー |
|
提出日時 | 2023-06-01 06:00:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 46 ms / 2,000 ms |
コード長 | 870 bytes |
コンパイル時間 | 271 ms |
コンパイル使用メモリ | 81,408 KB |
実行使用メモリ | 54,144 KB |
最終ジャッジ日時 | 2024-12-28 14:28:52 |
合計ジャッジ時間 | 1,871 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
import copy def matrixpow(A,n): pow2=[A.copy()] bit=2 while bit<=n: pow2.append([]) for i in range(len(A)): pow2[-1].append([]) for j in range(len(A)): cnt=0 for k in range(len(A)): cnt+=pow2[-2][i][k]*pow2[-2][k][j] cnt=cnt%M pow2[-1][-1].append(cnt) bit*=2 ret=0 bit=str(format(n,"b")) for i in range(len(bit)): if bit[-i-1]=="1": if ret==0: ret=pow2[i].copy() else: befret=copy.deepcopy(ret) for j in range(len(A)): for k in range(len(A)): cnt=0 for l in range(len(A)): cnt+=befret[j][l]*pow2[i][l][k] cnt=cnt%M ret[j][k]=cnt return ret N,M=map(int,input().split()) if N>=3: print(matrixpow([[1,1],[1,0]],N-2)[0][0]) else: if N==2: print(2) else: print(1)