結果
問題 |
No.718 行列のできるフィボナッチ数列道場 (1)
|
ユーザー |
|
提出日時 | 2018-08-13 08:15:34 |
言語 | Python2 (2.7.18) |
結果 |
AC
|
実行時間 | 11 ms / 2,000 ms |
コード長 | 376 bytes |
コンパイル時間 | 118 ms |
コンパイル使用メモリ | 6,912 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-24 07:42:53 |
合計ジャッジ時間 | 1,274 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#yuki718 mod=10**9+7 def mul(a,b): return [(a[0]*b[0]+a[1]*b[2])%mod, (a[0]*b[1]+a[1]*b[3])%mod, (a[2]*b[0]+a[3]*b[2])%mod, (a[2]*b[1] + a[3]*b[3])%mod] def fib(n): if n<=1: return n res=[1,0,0,1] mx=[1,1,1,0] while n>0: if n%2: res=mul(mx,res) mx=mul(mx,mx) n/=2 return res[2]%mod N=int(raw_input()) print (fib(N)*fib(N+1))%mod