結果
問題 |
No.526 フィボナッチ数列の第N項をMで割った余りを求める
|
ユーザー |
![]() |
提出日時 | 2020-08-09 13:17:35 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 476 ms / 2,000 ms |
コード長 | 771 bytes |
コンパイル時間 | 78 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 44,600 KB |
最終ジャッジ日時 | 2024-10-04 11:55:39 |
合計ジャッジ時間 | 8,336 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
N,M=map(int,input().split()) import numpy as np def 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) % mod else: mat = matrix_power(A, N//2, mod) return np.dot(np.dot(mat, mat) % mod, A) % mod def Fibonacci(N, mod): # return the n-th term of the fivonacci sequence in O(logN). # F0=0,F1=1 d = 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]) % mod print(Fibonacci(N-1,M))