結果

問題 No.891 隣接3項間の漸化式
コンテスト
ユーザー bayashiko
提出日時 2021-01-27 04:55:07
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 7,194 bytes
コンパイル時間 4,841 ms
コンパイル使用メモリ 165,052 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-24 02:33:52
合計ジャッジ時間 6,161 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
//#include<boost/multiprecision/cpp_int.hpp>
//#include<boost/multiprecision/cpp_dec_float.hpp>
//namespace mp=boost::multiprecision;
//#define mulint mp::cpp_int
//#define mulfloat mp::cpp_dec_float_100
//#include<atcoder/all>
//using namespace atcoder;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(lint (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(lint (i)=(n-1);(i)>=0;(i)--)
#define flc(x) __builtin_popcountll(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define vec vector<lint>
#define nep(x) next_permutation(all(x))
typedef long long lint;
typedef __int128_t llint;
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
const int MAX_N=3e5+5;
//struct edge{lint to,num;};
//vector<int> bucket[MAX_N/1000];
constexpr int MOD=1000000007;
//constexpr int MOD=998244353;

struct mint {
    lint x; // typedef long long ll;
    mint(lint x=0):x((x%MOD+MOD)%MOD){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += MOD-a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= MOD; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(lint t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(MOD-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

template<class T>
struct Matrix{
    vector<vector<T>> A;
    Matrix(){};
    Matrix(size_t n,size_t m):A(n,vector<T>(m,0)){};
    Matrix(size_t n):A(n,vector<T>(n,0)){};
    size_t height() const{
        return (A.size());
    }
    size_t width() const{
        return (A[0].size());
    }
    inline const vector<T> &operator[](int k) const{
        return (A.at(k));
    }
    inline vector<T> &operator[](int k){
        return (A.at(k));
    }

    static Matrix I(size_t n) {
        Matrix mat(n);
        rep(i,n) mat[i][i]=1;
        return (mat);
    }

    static Matrix O(size_t n) {
        Matrix mat(n);
        return (mat);
    }

    static Matrix make(vector<vector<T>> tsumugi){
        Matrix mat(tsumugi.size(),tsumugi[0].size());
        rep(i,tsumugi.size()) rep(j,tsumugi[0].size()){
            mat[i][j]=tsumugi[i][j];
        }
        return (mat);
    } 

    Matrix &operator+=(const Matrix &B) {
        size_t n=height(),m=width();
        assert(n==B.height() && m==B.width());
        rep(i,n) rep(j,m) (*this)[i][j]+=B[i][j];
        return (*this);
    }

    Matrix &operator-=(const Matrix &B) {
        size_t n = height(), m = width();
        assert(n == B.height() && m == B.width());
        rep(i,n) rep(j,m) (*this)[i][j] -= B[i][j];
        return (*this);
    }

    Matrix &operator*=(const Matrix &B) {
        size_t n = height(), m = B.width(), p = width();
        assert(p == B.height());
        vector< vector< T > > C(n, vector< T >(m, 0));
        rep(i,n) rep(j,m) rep(k,p) C[i][j]=(C[i][j]+(*this)[i][k]*B[k][j]);
        A.swap(C);
        return (*this);
    }

    Matrix &operator^=(long long k) {
        Matrix B=Matrix::I(height());
        while(k>0) {
            if(k&1) B*=*this;
            *this*=*this;
            k>>=1LL;
        }
        A.swap(B.A);
        return (*this);
    }

    Matrix operator+(const Matrix &B) const{return (Matrix(*this) += B);}
    Matrix operator-(const Matrix &B) const{return (Matrix(*this) -= B);}
    Matrix operator*(const Matrix &B) const{return (Matrix(*this) *= B);}
    Matrix operator^(const long long k) const{return (Matrix(*this) ^= k);}

    friend ostream &operator<<(ostream &os, Matrix &p) {
        size_t n = p.height(), m = p.width();
        for(int i = 0; i < n; i++) {
            os << "[";
            for(int j = 0; j < m; j++) {
            os << p[i][j] << (j + 1 == m ? "]\n" : ",");
            }
        }
    return (os);
    }

    T determinant() {
        Matrix B(*this);
        assert(width() == height());
        T ret = 1;
        for(int i = 0; i < width(); i++) {
            int idx = -1;
            for(int j = i; j < width(); j++) {
                if(B[j][i] != 0) idx = j;
            }
            if(idx == -1) return (0);
            if(i != idx) {
                ret *= -1;
                swap(B[i], B[idx]);
            }
            ret *= B[i][i];
            T vv = B[i][i];
            for(int j = 0; j < width(); j++) {
                B[i][j] /= vv;
            }
            for(int j = i + 1; j < width(); j++) {
                T a = B[j][i];
                for(int k = 0; k < width(); k++) {
                    B[j][k] -= B[i][k] * a;
                }
            }
        }
        return (ret);
    }
};

vector<vector<mint>> mtx{
    {1,1},//F(N-1),F(N-2),...,F(N-K)の係数
    {1,0}
}; // K次正方行列

vector<vector<mint>> F{{0,1}}; //F(1)~F(K)の値


Matrix<mint> MTX;
Matrix<mint> func;

void powerinit(){
    MTX=MTX.make(mtx);
    func=func.make(F);
}

template<class T>
Matrix<T> Maker(vector<vector<lint>> base){
    Matrix<T> res=res.make(base);
    return res;
}

template<class T>
Matrix<T> PowMatSum(Matrix<T> A,lint n){ //A+A^2+...+A^Nを返す
    int msize=A.height();
    Matrix<T> B(msize*2);
    rep(i,msize) rep(j,msize) B[i][j]=A[i][j];
    rep(i,msize) B[msize+i][i]=B[msize+i][msize+i]=1;
    B^=n+1;
    rep(i,msize) B[msize+i][i]-=1;
    Matrix<T> res(msize);
    rep(i,msize) rep(j,msize) res[i][j]=B[msize+i][j];
    return res;
}

template<class T>
T calc(lint n,Matrix<T> A,Matrix<T> f){ //F(N)の計算
    if(n==0) return 0;
    A^=n-1;
    T res=0; //零元
    rep(i,A.height()) res+=A[A.height()-1][i]*f[0][A.height()-1-i]; //演算 適宜演算子を変える
    return res;
}
template<class T>
T calcsum(lint n,Matrix<T> A,Matrix<T> f){ //Σ[i=1..N]F(i)の計算
    if(n==0) return 0;
    int msize=A.height();
    Matrix<T> B(msize*2);
    rep(i,msize) rep(j,msize) B[i][j]=A[i][j];
    rep(i,msize) B[msize+i][i]=B[msize+i][msize+i]=1;
    B^=n;
    rep(i,msize) B[msize+i][i]-=1;
    T res=0; //零元
    rep(i,msize) res+=B[msize*2-1][i]*f[0][msize-1-i]; //演算 適宜演算子を変える
    return res;
}

int main(){
    int a,b,n;
    cin >> a >> b >> n;
    mtx[0][0]=a,mtx[0][1]=b;
    powerinit();
    cout << calc(n+1,MTX,func) << endl;
}
0