結果
問題 | No.534 フィボナッチフィボナッチ数 |
ユーザー |
|
提出日時 | 2017-06-23 23:17:53 |
言語 | Python2 (2.7.18) |
結果 |
AC
|
実行時間 | 11 ms / 2,000 ms |
コード長 | 621 bytes |
コンパイル時間 | 53 ms |
コンパイル使用メモリ | 6,944 KB |
実行使用メモリ | 6,272 KB |
最終ジャッジ日時 | 2024-10-03 03:36:30 |
合計ジャッジ時間 | 1,496 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 42 |
ソースコード
#!/usr/bin/python2# -*- coding: utf-8 -*-# †def matmul(A, B, mod):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 matpow(A, n, mod):res = [1, 0, 0, 1]while n > 0:if n & 1:res = matmul(res, A, mod)A = matmul(A, A, mod)n >>= 1return resdef fib(n, mod):A = [1, 1, 1, 0]R = matpow(A, n-1, mod)return R[0]n = int(raw_input())if n == 0:print 0exit(0)m = fib(n, 2000000016)x = fib(m, 10**9 + 7)print x