結果
問題 | No.194 フィボナッチ数列の理解(1) |
ユーザー | roaris |
提出日時 | 2020-12-11 22:23:12 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 101 ms / 5,000 ms |
コード長 | 1,405 bytes |
コンパイル時間 | 151 ms |
コンパイル使用メモリ | 82,324 KB |
実行使用メモリ | 76,464 KB |
最終ジャッジ日時 | 2024-09-19 21:34:31 |
合計ジャッジ時間 | 4,135 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
import sysinput = sys.stdin.readlinedef mat_mul(A, B):C = [[0]*len(B[0]) for _ in range(len(A))]for i in range(len(A)):for j in range(len(B[0])):for k in range(len(A[0])):C[i][j] += A[i][k]*B[k][j]C[i][j] %= MODreturn Cdef mat_pow(A, n):res = [[0]*len(A) for _ in range(len(A))]for i in range(len(A)):res[i][i] = 1while n>0:if n&1:res = mat_mul(res, A)n >>= 1A = mat_mul(A, A)return resN, K = map(int, input().split())A = list(map(int, input().split()))MOD = 10**9+7if K<=10**6:dp = [0]*Kfor i in range(N):dp[i] = A[i]s = sum(A)for i in range(N, K):dp[i] = ss += dp[i]-dp[i-N]s %= MODprint(dp[K-1], sum(dp)%MOD)else:M1 = [[0]*N for _ in range(N)]for i in range(N-1):M1[i][i+1] = 1for i in range(N):M1[N-1][i] = 1x = [[A[i]] for i in range(N)]F = mat_mul(mat_pow(M1, K-N), x)[N-1][0]M2 = [[0]*(N+1) for _ in range(N+1)]for i in range(N):M2[i][i+1] = 1M2[N][0] = -1M2[N][N] = 2x = [[0]]acc = 0for i in range(N):acc += A[i]x.append([acc])S = mat_mul(mat_pow(M2, K-N), x)[N][0]print(F, S)