結果
問題 |
No.718 行列のできるフィボナッチ数列道場 (1)
|
ユーザー |
|
提出日時 | 2019-07-02 00:20:59 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 33 ms / 2,000 ms |
コード長 | 676 bytes |
コンパイル時間 | 91 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 10,880 KB |
最終ジャッジ日時 | 2024-07-18 09:56:40 |
合計ジャッジ時間 | 1,674 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#!/usr/bin/python3 #!coding: utf-8 from itertools import product N=int(input()) def mat2_mul(X, Y): Z = [ [0, 0], [0, 0] ] for (i,j,k) in product(range(2),range(2),range(2)): Z[i][j] += X[i][k] * Y[k][j]%1000000007 return Z def mat2_pow(X, n): if n == 0: return [ [1, 0], [0, 1] ] elif n % 2: return mat2_mul(X, mat2_pow(X, n-1)) else: half_pow = mat2_pow(X, n/2) return mat2_mul(half_pow, half_pow) def fib(n): if n == 0: return 0 else: F = [ [0, 1], [1, 1] ] return mat2_pow(F, n-1)[1][1] print(fib(N)*fib(N+1)%1000000007) exit()