結果
問題 | No.534 フィボナッチフィボナッチ数 |
ユーザー |
![]() |
提出日時 | 2020-03-24 02:20:21 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 574 ms / 2,000 ms |
コード長 | 1,075 bytes |
コンパイル時間 | 245 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 44,616 KB |
最終ジャッジ日時 | 2024-12-30 03:27:10 |
合計ジャッジ時間 | 27,561 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 42 |
ソースコード
#!/usr/bin/ python3.8import sysread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlinesimport numpy as npN = int(read())MOD = 10 ** 9 + 7MOD1 = (MOD + 1) * 2def coef_of_generating_function(P, Q, N, MOD):"""compute the coefficient [x^N] P/Q of rational power series.Parameters----------P : np.ndarraynumerator.Q : np.ndarraydenominatorQ[0] == 1 and len(Q) == len(P) + 1 is assumed.N : intThe coefficient to compute."""def convolve(f, g):return np.convolve(f, g) % MODwhile N:Q1 = Q.copy()Q1[1::2] = np.negative(Q1[1::2])if N & 1:P = convolve(P, Q1)[1::2]else:P = convolve(P, Q1)[::2]Q = convolve(Q, Q1)[::2]N >>= 1return P[0]def fibonacci_mod(N, MOD):P = np.array([0, 1], np.int64)Q = np.array([1, -1, -1], np.int64)return coef_of_generating_function(P, Q, N, MOD)F = fibonacci_mod(N, MOD1)print(fibonacci_mod(F, MOD))