結果
問題 | No.194 フィボナッチ数列の理解(1) |
ユーザー | googol_S0 |
提出日時 | 2021-02-10 00:27:13 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 82 ms / 5,000 ms |
コード長 | 892 bytes |
コンパイル時間 | 165 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 138,624 KB |
最終ジャッジ日時 | 2024-07-07 05:49:02 |
合計ジャッジ時間 | 3,169 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
N,K=map(int,input().split())A=list(map(int,input().split()))mod=10**9+7def m(a,b):r=[[0]*len(b[0]) for i in range(len(a))]for i in range(len(a)):for k in range(len(b)):for j in range(len(b[0])):r[i][j]=(r[i][j]+a[i][k]*b[k][j])%modreturn rdef p(a,n):r=[[0]*len(a) for i in range(len(a))]b=[]for i in range(len(a)):r[i][i]=1b.append(a[i][:])l=nwhile l>0:if l&1:r=m(b,r)b=m(b,b)l>>=1return rif K<=10**6:C=[0]for i in range(N):C.append(C[i]+A[i])for i in range(K):C.append((C[N+i]-C[i]+C[-1])%mod)print((C[K]-C[K-1])%mod,C[K])exit()B=[[0]*(N+1) for i in range(N+1)]for i in range(N):B[i][-1]=A[-i-1]C=[[0]*(N+1) for i in range(N+1)]for i in range(N-1):C[i+1][i]=1C[0][i+1]=1C[N][i+1]=1C[0][0]=1C[N][0]=1C[N][N]=1X=m(p(C,K-N),B)print(X[0][N],(X[N][N]+sum(A))%mod)