結果
問題 | No.534 フィボナッチフィボナッチ数 |
ユーザー |
![]() |
提出日時 | 2020-08-09 13:56:44 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 834 bytes |
コンパイル時間 | 97 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 44,600 KB |
最終ジャッジ日時 | 2024-10-04 14:20:52 |
合計ジャッジ時間 | 22,934 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 WA * 21 |
ソースコード
import numpy as npN = int(input())mod = 10**9 + 7cycle = 2000000016def matrix_power(A, N, mod):# returnA^N %mod in O(K**3 log N). (K is the size of A.)assert A.shape[0] == A.shape[1]K = A.shape[0]if N == 0:return np.eye(K, dtype=np.int64)else:if N % 2 == 0:mat = matrix_power(A, N//2, mod)return np.dot(mat, mat) % modelse:mat = matrix_power(A, N//2, mod)return np.dot(np.dot(mat, mat) % mod, A) % moddef Fibonacci(N, mod):# return the n-th term of the fivonacci sequence in O(logN).# F0=0,F1=1d = np.array([1, 0])A = np.array([[1, 1], [1, 0]], dtype=np.int64)res = np.dot(matrix_power(A, N, mod), d)return int(res[-1]) % modfibN = Fibonacci(N % cycle, mod)print(Fibonacci(fibN, mod))