結果
問題 | No.194 フィボナッチ数列の理解(1) |
ユーザー | 東前頭十一枚目 |
提出日時 | 2019-04-20 10:57:18 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 12 ms / 5,000 ms |
コード長 | 5,938 bytes |
コンパイル時間 | 1,862 ms |
コンパイル使用メモリ | 178,856 KB |
実行使用メモリ | 19,036 KB |
最終ジャッジ日時 | 2024-09-25 08:17:38 |
合計ジャッジ時間 | 3,112 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<n;i++)#define all(x) (x).begin(),(x).end()using namespace std;const int INF=1145141919,MOD=1e9+7;const long long LINF=8931145141919364364,LMOD=998244353;inline long long mod(long long n,long long m){return(n%m+m)%m;}// const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};template<class T>struct Matrix{vector<vector<T>> mat;Matrix(const int h,const int w):mat(h,vector<T>(w,0)){}Matrix(const vector<vector<T>> &G):mat(G){}int height() const{return mat.size();}int width() const{return mat[0].size();}// 添字const vector<T> &operator[](int i) const{assert(0<=i&&i<(int)mat.size());return mat[i];}vector<T> &operator[](int i){assert(0<=i&&i<(int)mat.size());return mat[i];}// 単位元Matrix I(int n,T x){Matrix ret(n,n);for(int i=0;i<n;i++){ret[i][i]=x;}return ret;}// 加法Matrix &operator +=(const Matrix &_mat){int h=(*this).height(),w=(*this).width();assert(h==_mat.height()&&w==_mat.width());for(int y=0;y<h;y++){for(int x=0;x<w;x++){(*this)[y][x]+=_mat[y][x];}}return (*this);}Matrix operator +(const Matrix &_mat) const{return Matrix(*this)+=_mat;}// 差Matrix &operator -=(const Matrix &_mat){int h=(*this).height(),w=(*this).width();assert(h==_mat.height()&&w==_mat.width());for(int y=0;y<h;y++){for(int x=0;x<w;x++){(*this)[y][x]-=_mat[y][x];}}return (*this);}Matrix operator -(const Matrix &_mat) const{return Matrix(*this)-=_mat;}// 乗法Matrix &operator *=(const Matrix &_mat){int h=(*this).height(),w=(*this).width();int _h=_mat.height(),_w=_mat.width();assert(w==_h);vector<vector<T>> ret(h,vector<T>(_w,0));for(int y=0;y<h;y++){for(int x=0;x<_w;x++){for(int k=0;k<w;k++){ret[y][x]+=(*this)[y][k]*_mat[k][x];}}}mat=ret;return (*this);}Matrix operator *(const Matrix &_mat) const{return Matrix(*this)*=_mat;}// 冪乗Matrix pow(long long k){Matrix ret=I((*this).height(),1);while(k>0){if(k&1) ret*=(*this);(*this)*=(*this);k>>=1ll;}(*this)=ret;return (*this);}void debug(){int h=height(),w=width();for(int y=0;y<h;y++){for(int x=0;x<w;x++){cout<<mat[y][x]<<(x==w-1?"\n":" ");}}}};using int64 = int_fast64_t;template<int64 MOD>struct ModInt{int64 x;ModInt():x(0){}ModInt(int64 x):x(x>=0?x%MOD:(MOD-(-x)%MOD)%MOD){}// 負号ModInt operator -() const{return ModInt(-x);}// 加算ModInt &operator +=(const ModInt &rhs){x+=rhs.x;if(x>=MOD) x-=MOD;return (*this);}ModInt operator +(const ModInt &rhs) const{return ModInt(*this)+=rhs;}// 減算ModInt &operator -=(const ModInt &rhs){x+=MOD-rhs.x;if(x>=MOD) x-=MOD;return (*this);}ModInt operator -(const ModInt &rhs) const{return ModInt(*this)-=rhs;}// 乗算ModInt &operator *=(const ModInt &rhs){x*=rhs.x;if(x>=MOD) x%=MOD;return (*this);}ModInt operator *(const ModInt &rhs) const{return ModInt(*this)*=rhs;}// 除算ModInt &operator /=(const ModInt &rhs){(*this)*=rhs.inverse();return (*this);}ModInt operator /(const ModInt &rhs) const{return ModInt(*this)/=rhs;}// 等号bool operator ==(const ModInt &rhs){return x==rhs.x;}bool operator !=(const ModInt &rhs){return x!=rhs.x;}// 累乗ModInt pow(int64 n){int64 tmp=x;x=1;while(n>0){if(n&1) x=x*tmp%MOD;tmp=tmp*tmp%MOD;n>>=1ll;}return (*this);}// 逆元ModInt inverse(){int64 a=x,b=MOD,s=1,t=0;while(b>0){int64 u=b/a;b-=u*a;t-=u*s;swap(a,b);swap(s,t);}return ModInt(s);}// 入出力friend istream &operator >>(istream &lhs,ModInt<MOD> &rhs){int64 x; lhs>>x;rhs=ModInt<MOD>(x);return lhs;}friend ostream &operator <<(ostream &lhs,const ModInt<MOD> &rhs){return lhs<<rhs.x;}};int main(){const int MOD=1e9+7;using mint=ModInt<MOD>;long long n,k; cin>>n>>k;// はずれif(k<=n){mint f,sum=0;for(int i=1;i<=k;i++){cin>>f;sum+=f;}cout<<f<<" "<<sum<<endl;return 0;}// テスト1if(n>30){mint f[k+1],s[k+1];for(int i=1;i<=n;i++){cin>>f[i];s[i]=f[i]+s[i-1];}for(int i=n+1;i<=k;i++){f[i]=s[i-1]-s[i-n-1];s[i]=f[i]+s[i-1];}cout<<f[k]<<" "<<s[k]<<endl;return 0;}// テスト2mint f[n+1],s[n+1];for(int i=1;i<=n;i++){cin>>f[i];s[i]=f[i]+s[i-1];}Matrix<mint> mat(n+1,n+1);mat[0][0]=2;mat[0][n]=-1;for(int y=1;y<n+1;y++){mat[y][y-1]=1;}mat.pow(k-n);mint sk,sk1;for(int x=0;x<n+1;x++){sk+=mat[0][x]*s[n-x];sk1+=mat[1][x]*s[n-x];}cout<<sk-sk1<<" "<<sk<<endl;return 0;}