結果

問題 No.995 タピオカオイシクナーレ
コンテスト
ユーザー suzuken_w
提出日時 2020-03-13 23:57:35
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 14 ms / 2,000 ms
コード長 3,258 bytes
コンパイル時間 2,217 ms
コンパイル使用メモリ 184,892 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-23 01:34:06
合計ジャッジ時間 3,837 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
constexpr ll mod=1000000007;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
struct mint{
    using ull=unsigned long long int;
    ull v;
    mint(ll vv=0){s(vv%mod+mod);}
    mint& s(ull vv){
        v=vv<mod?vv:vv-mod;
        return *this;
    }
    //オーバーロード
    mint operator-()const{return mint()-*this;}//符号反転
    mint&operator+=(const mint&val){return s(v+val.v);}
    mint&operator-=(const mint&val){return s(v+mod-val.v);}
    mint&operator*=(const mint&val){
        v=ull(v)*val.v%mod;
        return *this;
    }
    mint&operator/=(const mint&val){return *this*=val.inv();}
    mint operator+(const mint&val){return mint(*this)+=val;}
    mint operator-(const mint&val){return mint(*this)-=val;}
    mint operator*(const mint&val){return mint(*this)*=val;}
    mint operator/(const mint&val){return mint(*this)/=val;}
    mint pow(ll n)const{
        mint res(1),x(*this);
        while(n){
            if(n&1)res*=x;
            x*=x;
            n>>=1;
        }
        return res;
    }
     mint inv()const{return pow(mod-2);}
    //拡張ユークリッドの互除法
    /* mint inv()const{
        int x,y;
        int g=extgcd(v,mod,x,y);
        assert(g==1);
        if(x<0)x+=mod;
        return mint(x);
    }*/
    friend ostream& operator<<(ostream&os,const mint&val){
        return os<<val.v;
    }//出力
    bool operator<(const mint&val)const{return v<val.v;}
    bool operator==(const mint&val)const{return v==val.v;}
    bool operator>(const mint&val)const{return v>val.v;}
};
ll n;//n項前のフィボナッチ数列　O(n^3 log k)
vector<mint> matmul(vector<mint> &dp,vector<vector<mint>> &mat){
    vector<mint> res(n,0);
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)res[i]+=mat[i][j]*dp[j];
    return res;
}
vector<vector<mint>> update(vector<vector<mint>> &mat){
    vector<vector<mint>> res(n,vector<mint>(n,0));
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int k=0;k<n;k++)res[i][j]+=mat[i][k]*mat[k][j];
    return res;
}
void matpow(vector<mint> &dp,vector<vector<mint>> &mat,ll k){
    while(k){
        if(k&1)dp=matmul(dp,mat);
        mat=update(mat);
        k>>=1;
    }
}
int main(){
    n=2;
  ll N,m,k,p,q;
  cin>>N>>m>>k>>p>>q;
  V<ll> b(N);
  for(int i=0;i<N;i++)cin>>b[i];
  mint A,B;
  B=mint(p)/mint(q);
  A=mint(1)-B;
  vector<mint> dp1(2,1),dp2(2,1);
  dp1[1]=0;dp2[0]=0;
vector<vector<mint>> mat1(2,vector<mint>(2)),mat2(2,vector<mint>(2));
mat1[0][0]=mat1[1][1]=A;
mat1[0][1]=mat1[1][0]=B;
mat2[0][0]=mat2[1][1]=A;
mat2[0][1]=mat2[1][0]=B;
matpow(dp1,mat1,k);
matpow(dp2,mat2,k);
mint ans=0;
for(int i=0;i<N;i++){
    if(i<m)ans+=dp1[0]*mint(b[i]);
    else ans+=dp2[0]*mint(b[i]);
}
cout<<ans<<"\n";
}
0