結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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)
0