結果
問題 | No.718 行列のできるフィボナッチ数列道場 (1) |
ユーザー |
![]() |
提出日時 | 2018-07-27 23:28:45 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 41 ms / 2,000 ms |
コード長 | 574 bytes |
コンパイル時間 | 171 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 52,224 KB |
最終ジャッジ日時 | 2024-07-05 05:20:43 |
合計ジャッジ時間 | 1,917 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
M = 1000000007 # qiita.com/SaitoTsutomu/items/be069ea89c85191799fa def fib2(n): if n <= 1: return n result = [1, 0, 0, 1] matrix = [1, 1, 1, 0] while n > 0: if n % 2: result = mul(matrix, result) matrix = mul(matrix, matrix) n //= 2 return result[2] def mul(a, b): return [a[0]*b[0] % M + a[1]*b[2] % M, a[0]*b[1] % M + a[1]*b[3] % M, a[2]*b[0] % M + a[3]*b[2] % M, a[2]*b[1] % M + a[3]*b[3] % M] n = int(input()) ans = fib2(n) * fib2(n+1) % M print(ans)