結果
問題 | No.718 行列のできるフィボナッチ数列道場 (1) |
ユーザー |
![]() |
提出日時 | 2018-07-27 23:00:27 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,819 bytes |
コンパイル時間 | 1,328 ms |
コンパイル使用メモリ | 164,872 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-05 03:30:44 |
合計ジャッジ時間 | 2,136 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll> P; #define fi first #define se second #define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++) #define rep(i,n) repl(i,0,n) #define all(x) (x).begin(),(x).end() #define dbg(x) cout<<#x"="<<x<<endl #define mmax(x,y) (x>y?x:y) #define mmin(x,y) (x<y?x:y) #define maxch(x,y) x=mmax(x,y) #define minch(x,y) x=mmin(x,y) #define uni(x) x.erase(unique(all(x)),x.end()) #define exist(x,y) (find(all(x),y)!=x.end()) #define bcnt __builtin_popcount #define INF 1e16 #define mod 1000000007 const long long M=1e9+7; typedef vector<long long> vec; typedef vector<vec> mat; struct Matrix{ int N; mat a; Matrix(int n){ N=n; a=mat(N,vec(N)); for(int i=0;i<N;i++)a[i][i]=1; } Matrix pow(long long b) const { Matrix res(N); Matrix d(N); for(int i=0;i<N;i++)for(int j=0;j<N;j++)d[i][j]=a[i][j]; for(;b>0;b>>=1,d=d*d)if(b&1)res=d*res; return res; } Matrix operator+(const Matrix& r) const { Matrix s(N); for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ s[i][j]=(a[i][j]+r.a[i][j])%M; } } return s; } Matrix operator*(const Matrix& r) const { Matrix s(N); for(int i=0;i<N;i++)s[i][i]=0; const long long modl=8*M*M; for(int i=0;i<N;i++){ for(int k=0;k<N;k++){ for(int j=0;j<N;j++){ s[i][j]+=a[i][k]*r.a[k][j]; if(s[i][j]>=modl)s[i][j]-=modl; } } for(int j=0;j<N;j++)s[i][j]%=M; } return s; } vector<long long>& operator[](int i){ return a[i]; } }; ll fib(ll n){ Matrix a(2); a[0][0]=1; a[0][1]=1; a[1][0]=1; a[1][1]=0; Matrix res=a.pow(n); return res[0][0]; } int main(){ ll n; cin>>n; cout<<fib(n-1)*fib(n)%mod<<endl; return 0; }