#432873 (C++14) No.995 タピオカオイシクナーレ

提出ソース

結果

問題	No.995 タピオカオイシクナーレ
ユーザー	wakuwinmail
提出日時	2020-02-21 22:15:35
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	39 ms / 2,000 ms
コード長	5,392 bytes
コンパイル時間	2,318 ms
コンパイル使用メモリ	178,964 KB
実行使用メモリ	5,248 KB
最終ジャッジ日時	2024-10-08 22:48:12
合計ジャッジ時間	3,217 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	1 ms 5,248 KB
testcase_05	AC	2 ms 5,248 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	2 ms 5,248 KB
testcase_08	AC	2 ms 5,248 KB
testcase_09	AC	2 ms 5,248 KB
testcase_10	AC	2 ms 5,248 KB
testcase_11	AC	2 ms 5,248 KB
testcase_12	AC	2 ms 5,248 KB
testcase_13	AC	2 ms 5,248 KB
testcase_14	AC	1 ms 5,248 KB
testcase_15	AC	2 ms 5,248 KB
testcase_16	AC	39 ms 5,248 KB
testcase_17	AC	38 ms 5,248 KB
testcase_18	AC	38 ms 5,248 KB
testcase_19	AC	38 ms 5,248 KB
testcase_20	AC	38 ms 5,248 KB
testcase_21	AC	37 ms 5,248 KB
testcase_22	AC	37 ms 5,248 KB
testcase_23	AC	37 ms 5,248 KB
testcase_24	AC	38 ms 5,248 KB
testcase_25	AC	39 ms 5,248 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>

struct has_idplus_impl {
    template <class T>
    static auto check(T&& x)->decltype(x.idplus(),std::true_type{});

    template <class T>
    static auto check(...)->std::false_type;
};

template <class T>
class has_idplus :
        public decltype(has_idplus_impl::check<T>(std::declval<T>())) {};


template<typename T>
struct Matrix{
    using scalarvalue=T;
private:
    std::vector<std::vector<scalarvalue>> data;
    int col,row;
public:
    constexpr Matrix(){}

    constexpr Matrix(std::vector<std::vector<scalarvalue>> data):data(data){
        col=data.size();
        row=data[0].size();
    }

    constexpr Matrix(int col,int row,scalarvalue init=0):row(row),col(col){
        data.assign(col,std::vector<scalarvalue>(row,init));
    }

    constexpr Matrix &operator+=(const Matrix rhs){
        for(int i = 0; i < col; ++i){
            for(int j = 0; j < row; ++j){
                data[i][j]+=rhs[i][j];
            }
        }
    }

    constexpr Matrix &operator-=(const Matrix rhs){
        for(int i = 0; i < col; ++i){
            for(int j = 0; j < row; ++j){
                data[i][j]-=rhs[i][j];
            }
        }
    }

    constexpr Matrix &operator*=(const scalarvalue rhs){//スカラー倍
        for(int i = 0; i < col; ++i){
            for(int j = 0; j < row; ++j){
                data[i][j]*=rhs;
            }
        }
    }

    constexpr Matrix operator*(Matrix rhs){
        Matrix<scalarvalue> ret(col,rhs.get_row(),0);
        for(int i = 0; i < col; ++i){
            for(int j = 0; j < rhs.get_row(); ++j){
                for(int k = 0; k < row; ++k){
                    ret[i][j]+=data[i][k]*rhs[k][j];
                }
            }
        }
        return ret;
    }

    constexpr std::vector<scalarvalue>& operator[](const int i){
        return data[i];
    }

    constexpr Matrix pow(long long n){
        assert(is_square());//正方形じゃないと計算が定義できない
        Matrix<scalarvalue> ret(col,row,0);
        Matrix<scalarvalue> a(*this);
        for(int i = 0; i < col; ++i){
            ret[i][i]=1;//単位行列を作る
        }
        while(n>0){
            if((n&1)!=0){//n%2==1
                ret=ret*a;
            }
            a=a*a;
            n=n/2;
        }
        return ret;
    }




    bool is_square(){return col==row;}
    int get_col(){return col;}
    int get_row(){return row;}

};

template<std::uint64_t Mod> struct ModInt{
    using u64=uint64_t;
private:
    u64 a;
public:
    constexpr ModInt(){}
    constexpr ModInt(u64 x):a(x%Mod){}

    constexpr u64 &value(){return a;}
    constexpr const u64 &value()const{return a;}


    constexpr ModInt &operator+=(const ModInt rhs){
        a+=rhs.value();
        if(a>=Mod){
            a-=Mod;
        }
        return *this;
    }

    constexpr ModInt &operator-=(const ModInt rhs){
        if(a<rhs.value()){
            a+=Mod;
        }
        a-=rhs.value();
        return *this;
    }

    constexpr ModInt &operator*=(const ModInt rhs){
        a=a*rhs.value()%Mod;
        return *this;
    }

    constexpr ModInt &operator/=(ModInt rhs){
        u64 n=Mod-2;
        while(n>0){
            if((n&1)!=0){//n%2==1
                *this*=rhs;
            }
            rhs*=rhs;
            n=n/2;
        }
        return *this;
    }

    constexpr ModInt operator+(const ModInt rhs){
        return ModInt(*this)+=rhs;
    }

    constexpr ModInt operator-(const ModInt rhs){
        return ModInt(*this)-=rhs;
    }

    constexpr ModInt operator*(const ModInt rhs){
        return ModInt(*this)*=rhs;
    }

    constexpr ModInt operator/(const ModInt rhs){
        return ModInt(*this)/=rhs;
    }
    constexpr ModInt &operator++(){
        ++a;
        if(a>=Mod){
            a-=Mod;
        }
        return *this;
    }

    constexpr ModInt &operator--(){
        if(a==0){
            a+=Mod;
        }
        --a;
        return *this;
    }

    constexpr ModInt operator- (){
        if(a==0)return 0;
        else return ModInt(Mod-a);
    }


};

using Mi=ModInt<1000000007ull>;

Mi operator"" _mi(unsigned long long n){
    return Mi(n);
}

template<typename T>
T modinv(T a,T m=1000000007){
    T b=m,u=1,v=0;
    while(b!=0){
        T t=a/b;
        a-=t*b;
        std::swap(a,b);
        u-=t*v;
        std::swap(u,v);
    }
    u%=m;
    if(u<0)u+=m;
    return u;
}

long long mod=1000000007LL;

template<typename T>
constexpr T modpow(T a,T n){//(a^n)%MOD
    T ret=1;
    while(n>0){
        if((n&1)!=0){//n%2==1
            ret=ret*a%mod;
        }
        a=a*a%mod;
        n=n/2;
    }
    return ret;
}

using namespace std;
using ll=long long;

int main(){
    ll n,m,k,p,q;
    cin>>n>>m>>k>>p>>q;
    vector<vector<Mi>> op(2,vector<Mi>(2));
    op[0][0]=1_mi-Mi(p*modinv(q));

    op[0][1]=Mi(p*modinv(q));
    op[1][1]=1_mi-Mi(p*modinv(q));

    op[1][0]=Mi(p*modinv(q));
    Matrix<Mi> mt(op);
    vector<vector<Mi>> a(1,{1_mi,0_mi}),b(1,{0_mi,1_mi});
    Matrix<Mi> ma(a),mb(b);
    mt=mt.pow(k);
    ma=ma*mt;
    mb=mb*mt;

    vector<Mi> d(n);
    for (int i = 0; i < n; ++i) {
        ll t;
        cin>>t;
        d[i]=Mi(t);
    }
    Mi ans=0_mi;
    for (int i = 0; i < m; ++i) {
        ans+=d[i]*ma[0][0];

    }
    for (int i = m; i < n; ++i) {
        ans+=d[i]*mb[0][0];

    }
    cout<<ans.value()<<endl;
    return 0;
}

yukicoder

結果

テストケース

ソースコード