結果
問題 | No.534 フィボナッチフィボナッチ数 |
ユーザー |
👑 |
提出日時 | 2022-03-25 20:39:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 46 ms / 2,000 ms |
コード長 | 768 bytes |
コンパイル時間 | 317 ms |
コンパイル使用メモリ | 82,396 KB |
実行使用メモリ | 55,424 KB |
最終ジャッジ日時 | 2024-10-14 04:33:26 |
合計ジャッジ時間 | 3,689 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 42 |
ソースコード
from copy import deepcopyMOD = 10 ** 9 + 7def matpow(A, B, w, MOD):l = len(A)while w:if w & 1:C = [0] * lfor i in range(l):for j in range(l):C[i] += A[i][j] * B[j]C[i] %= MODB = C.copy()C = [[0] * l for _ in range(l)]for i in range(l):for j in range(l):for k in range(l):C[i][j] += A[i][k] * A[k][j]C[i][j] %= MODA = deepcopy(C)w >>= 1return Bdef fibo(x, MOD):A = [[1, 1], [1, 0]]B = [1, 0]if x == 0:return 0return matpow(A, B, x - 1, MOD)[0]n = int(input())print(fibo(fibo(n, 2 * MOD + 2), MOD))