結果
問題 |
No.718 行列のできるフィボナッチ数列道場 (1)
|
ユーザー |
![]() |
提出日時 | 2018-07-29 16:10:39 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 907 bytes |
コンパイル時間 | 964 ms |
コンパイル使用メモリ | 89,392 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-18 01:20:52 |
合計ジャッジ時間 | 1,692 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include<iostream> #include<vector> #include<stdlib.h> #include<time.h> #include<math.h> #include<string.h> #include<algorithm> #include<queue> #include<map> #include<iomanip> using namespace std; #define VV vector<vector<long long int>> #define MOD 1000000007 VV mul(VV &M1,VV &M2){ VV ans={{0,0},{0,0}}; ans[0][0]=((M1[0][0]*M2[0][0] % MOD)+(M1[0][1]*M2[1][0] % MOD)) % MOD; ans[0][1]=((M1[0][0]*M2[0][1] % MOD)+(M1[0][1]*M2[1][1] % MOD)) % MOD; ans[1][0]=((M1[1][0]*M2[0][0] % MOD)+(M1[1][1]*M2[1][0] % MOD)) % MOD; ans[1][1]=((M1[1][0]*M2[0][1] % MOD)+(M1[1][1]*M2[1][1] % MOD)) % MOD; return ans; } VV pow(VV A,long long int n){ VV ans; if(n==0){ return {{1,0},{0,1}}; } ans=pow(mul(A,A),n/2); if(n%2==1)ans=mul(A,ans); return ans; } int main(void){ VV A={{1,1},{1,0}}; VV ans; long long int n; cin>>n; ans=pow(A,n); std::cout<<ans[0][0]*ans[0][1]%MOD<<std::endl; }