結果
問題 | No.534 フィボナッチフィボナッチ数 |
ユーザー |
![]() |
提出日時 | 2017-06-23 23:07:06 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,059 bytes |
コンパイル時間 | 1,405 ms |
コンパイル使用メモリ | 166,016 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-03 03:32:04 |
合計ジャッジ時間 | 2,510 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 42 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define int long longint MOD=1000000007LL;typedef vector<int> arr;typedef vector<arr> mat;inline arr mul(mat a,arr& b,int mod){arr res(b.size(),0);for(int i=0;i<(int)b.size();i++)for(int j=0;j<(int)a[i].size();j++)(res[i]+=a[i][j]*b[j])%=mod;return res;}inline mat mul(mat a,mat& b,int mod){mat res(a.size(),arr(b[0].size(),0));for(int i=0;i<(int)a.size();i++)for(int j=0;j<(int)b[0].size();j++)for(int k=0;k<(int)b.size();k++)(res[i][j]+=a[i][k]*b[k][j])%=mod;return res;}mat base;inline mat mat_pow(mat a,int n,int mod){mat res(base);while(n){if(n&1) res=mul(a,res,mod);a=mul(a,a,mod);n>>=1;}return res;}typedef pair<int,int> P;signed main(){mat A(2,arr(2,1));mat B(2,arr(1,0));A[1][1]=0;B[0][0]=1;base = mat(2,arr(2,0));base[0][0]=base[1][1]=1;int n;cin>>n;int fib1=(mul(mat_pow(A,n,2*(MOD+1)),B,2*(MOD+1)))[1][0];int fib2=(mul(mat_pow(A,fib1,MOD),B,MOD))[1][0];cout<<fib2<<endl;return 0;}