結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
    }
    // テスト1
    if(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;
    }
    // テスト2
    mint 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;
}
0