結果
問題 |
No.3228 Very Large Fibonacci Sum
|
ユーザー |
![]() |
提出日時 | 2025-08-11 22:03:15 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 90 ms / 2,000 ms |
コード長 | 856 bytes |
コンパイル時間 | 215 ms |
コンパイル使用メモリ | 82,712 KB |
実行使用メモリ | 64,512 KB |
最終ジャッジ日時 | 2025-08-11 22:03:19 |
合計ジャッジ時間 | 2,462 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
a,b,c,d,e,N=map(int,input().split()) v=[0]*5 v[0]=a v[1]=a+b v[2]=v[1]+b*c+a*d+e mod=10**9+7 if N<=2: print(v[N]%mod) exit() u=[[[0]*4 for i in range(4)] for k in range(70)] u[0][0][0]=c+1 u[0][0][1]=d-c u[0][0][2]=-d u[0][0][3]=e u[0][3][3]=1 u[0][1][0]=1 u[0][2][1]=1 for k in range(1,70): for i in range(4): for j in range(4): for w in range(4): u[k][i][j]+=u[k-1][i][w]*u[k-1][w][j] u[k][i][j]%=mod A=[[0]*4 for i in range(4)] for i in range(4): A[i][i]=1 for k in range(70): if ((N-2)>>k)&1: A2=[[0]*4 for i in range(4)] for i in range(4): for j in range(4): for w in range(4): A2[i][j]+=A[i][w]*u[k][w][j] A2[i][j]%=mod for i in range(4): for j in range(4): A[i][j]=A2[i][j] result=A[0][0]*v[2]+A[0][1]*v[1]+A[0][2]*v[0]+A[0][3] result%=mod print(result)