結果
問題 | No.534 フィボナッチフィボナッチ数 |
ユーザー |
![]() |
提出日時 | 2021-02-24 07:00:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 45 ms / 2,000 ms |
コード長 | 856 bytes |
コンパイル時間 | 394 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 59,136 KB |
最終ジャッジ日時 | 2024-09-23 05:55:52 |
合計ジャッジ時間 | 3,329 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 42 |
ソースコード
def polymul(f,g,MOD):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] %= MODreturn resdef fps_nth_term(f,g,N,MOD):assert g[0] != 0while N:h = g[:]for i in range(1,len(g),2):h[i] = -h[i]f = polymul(f,h,MOD)[N%2:N+1:2]g = polymul(g,h,MOD)[:N+1:2]N //= 2return 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,MOD):L = len(g)assert len(a) == L-1f = polymul(a,g,MOD)[:L-1]return fps_nth_term(f,g,N,MOD)n = int(input())MOD = 10**9+7MOD2 = 2*(MOD+1)x = rec_nth_term([0,1],[1,-1,-1],n,MOD2)y = rec_nth_term([0,1],[1,-1,-1],x,MOD)print(y%MOD)