結果

問題 No.194 フィボナッチ数列の理解(1)
ユーザー 東前頭十一枚目東前頭十一枚目
提出日時 2019-04-20 10:38:57
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 5,495 bytes
コンパイル時間 1,816 ms
コンパイル使用メモリ 179,252 KB
実行使用メモリ 814,720 KB
最終ジャッジ日時 2024-09-25 07:58:37
合計ジャッジ時間 4,461 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 9 ms
5,376 KB
testcase_03 AC 3 ms
5,376 KB
testcase_04 AC 5 ms
5,376 KB
testcase_05 AC 4 ms
5,376 KB
testcase_06 AC 4 ms
5,376 KB
testcase_07 AC 7 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 5 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 4 ms
5,376 KB
testcase_12 AC 4 ms
5,376 KB
testcase_13 AC 3 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 7 ms
5,376 KB
testcase_16 AC 7 ms
5,376 KB
testcase_17 AC 3 ms
5,376 KB
testcase_18 AC 7 ms
5,376 KB
testcase_19 AC 8 ms
5,376 KB
testcase_20 AC 2 ms
5,376 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 -- -
権限があれば一括ダウンロードができます

ソースコード

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;
    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;
}
0