#340994 (C++14) No.194 フィボナッチ数列の理解(1)

提出ソース

結果

問題	No.194 フィボナッチ数列の理解(1)
ユーザー	東前頭十一枚目
提出日時	2019-04-20 10:38:57
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	MLE
実行時間	-
コード長	5,495 bytes
コンパイル時間	1,870 ms
コンパイル使用メモリ	178,644 KB
実行使用メモリ	813,736 KB
最終ジャッジ日時	2023-10-25 23:55:49
合計ジャッジ時間	4,993 ms
ジャッジサーバーID （参考情報）	judge13 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,372 KB
testcase_01	AC	2 ms 4,372 KB
testcase_02	AC	8 ms 4,372 KB
testcase_03	AC	2 ms 4,372 KB
testcase_04	AC	4 ms 4,372 KB
testcase_05	AC	4 ms 4,372 KB
testcase_06	AC	4 ms 4,372 KB
testcase_07	AC	6 ms 4,372 KB
testcase_08	AC	2 ms 4,372 KB
testcase_09	AC	5 ms 4,372 KB
testcase_10	AC	3 ms 4,372 KB
testcase_11	AC	3 ms 4,372 KB
testcase_12	AC	4 ms 4,372 KB
testcase_13	AC	2 ms 4,372 KB
testcase_14	AC	2 ms 4,372 KB
testcase_15	AC	7 ms 4,372 KB
testcase_16	AC	7 ms 4,372 KB
testcase_17	AC	3 ms 4,372 KB
testcase_18	AC	6 ms 4,372 KB
testcase_19	AC	8 ms 4,372 KB
testcase_20	AC	1 ms 4,372 KB
testcase_21	MLE	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
    mint a[n+1];
    for(int i=1;i<=n;i++) cin>>a[i];
    mint s[n+1];
    for(int i=1;i<=n;i++) s[i]=a[i]+s[i-1];
    if(k<=n){
        cout<<a[k]<<" "<<s[k]<<endl;
        return 0;
    }
    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;
}

yukicoder

結果

テストケース

ソースコード