結果
問題 |
No.718 行列のできるフィボナッチ数列道場 (1)
|
ユーザー |
![]() |
提出日時 | 2021-03-15 17:39:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 773 bytes |
コンパイル時間 | 381 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 59,392 KB |
最終ジャッジ日時 | 2024-11-07 05:04:42 |
合計ジャッジ時間 | 2,536 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
def polymul(f,g): lf = len(f) lg = len(g) res = [0]*(lf+lg-1) for i in range(lf): for j in range(lg): res[i+j] += f[i]*g[j] res[i+j] %= MOD return res def fps_nth_term(f,g,N): assert g[0] != 0 while N: h = g[:] for i in range(1,len(g),2): h[i] = -h[i] f = polymul(f,h)[N%2:N+1:2] g = polymul(g,h)[:N+1:2] N //= 2 return f[0]*pow(g[0],MOD-2,MOD)%MOD # a[0],...,a[L-2] とL-1次特性多項式 g が与えられているL項間漸化式の第N項 def rec_nth_term(a,g,N): L = len(g) assert len(a) == L-1 f = polymul(a,g)[:L-1] return fps_nth_term(f,g,N) MOD = 10**9+7 ans = rec_nth_term([0,1,2,6],[1,-1,-4,-1,1],int(input())) print(ans%MOD)