結果

問題 No.995 タピオカオイシクナーレ
コンテスト
ユーザー monkukui2
提出日時 2020-02-11 21:03:31
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 42 ms / 2,000 ms
コード長 4,734 bytes
コンパイル時間 1,273 ms
コンパイル使用メモリ 106,948 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-08 22:36:28
合計ジャッジ時間 2,914 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */
// 状態遷移図（確率）を書いて，連立漸化式立てて，行列式に変形して，行列累乗（僕これ苦手）
template<typename T,T MOD = 1000000007>
struct Mint{
    T v;
    Mint():v(0){}
    Mint(signed v):v(v){}
    Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}

    Mint pow(long long k){
        Mint res(1),tmp(v);
        while(k){
            if(k&1) res*=tmp;
            tmp*=tmp;
            k>>=1;
        }
        return res;
    }

    static Mint add_identity(){return Mint(0);}
    static Mint mul_identity(){return Mint(1);}

    Mint inv(){return pow(MOD-2);}

    Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}
    Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}
    Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}
    Mint& operator/=(Mint a){return (*this)*=a.inv();}

    Mint operator+(Mint a) const{return Mint(v)+=a;};
    Mint operator-(Mint a) const{return Mint(v)-=a;};
    Mint operator*(Mint a) const{return Mint(v)*=a;};
    Mint operator/(Mint a) const{return Mint(v)/=a;};

    Mint operator-() const{return v?Mint(MOD-v):Mint(v);}

    bool operator==(const Mint a)const{return v==a.v;}
    bool operator!=(const Mint a)const{return v!=a.v;}
    bool operator <(const Mint a)const{return v <a.v;}

    static Mint comb(long long n,int k){
        Mint res(1);
        for(int i=0;i<k;i++){
            res*=Mint(n-i);
            res/=Mint(i+1);
        }
        return res;
    }
};

// 逆元を求める. a と m は互いに素であることが要請される.
long long modinv(long long a, long long m) {
  long long b = m, u = 1, v = 0;
  while(b){
    long long t = a / b;
    a -= t * b; swap(a, b);
    u -= t * v; swap(u, v);
  }
  u %= m; 
  if (u < 0) u += m;
  return u;
}

// before your coding, you have to write a line "math_init()"

template<typename T>
struct SquareMatrix{
    
    vector<vector<T>> dat;
    size_t N;
    SquareMatrix() = default;
    SquareMatrix(size_t N, T val = T()):N(N){
        dat = vector<vector<T>> (N, vector<T> (N));
        for(size_t i=0;i<N;i++)
            for(size_t j=0;j<N;j++)
                dat[i][j]=val;
    }
    SquareMatrix& operator=(const SquareMatrix& a){
        dat=a.dat;
        return (*this);
    }
    bool operator==(const SquareMatrix& a) const{
        return dat==a.dat;
    }

    size_t size() const{return N;};
    vector<T>& operator[](size_t k){return dat[k];};
    const vector<T>& operator[](size_t k) const {return dat[k];};

    SquareMatrix operator*(const SquareMatrix &B) const{
        SquareMatrix res(N, 0);
        for(size_t i=0;i<N;i++)
            for(size_t j=0;j<N;j++)
                for(size_t k=0;k<N;k++)
                    res[i][j]=res[i][j]+(dat[i][k]*B[k][j]);
        return res;
    }

    SquareMatrix operator+(const SquareMatrix &B) const{
        SquareMatrix res(N, 0);
        for(size_t i=0;i<N;i++)
            for(size_t j=0;j<N;j++)
                res[i][j]=dat[i][j]+B[i][j];
        return res;
    }

    SquareMatrix pow(long long n) const{
        SquareMatrix a=*this;
        SquareMatrix res(N, 0);
        for(size_t i = 0; i < N; i++) res[i][i] = 1;    
        while(n){
            if(n&1) res=res*a;      
            a=a*a;
            n>>=1;
        }
        return res;
    }
};

int main() {
  
  using modint = Mint<lint>;

  lint n, m, k; cin >> n >> m >> k;
  lint p; // 状態が変化する確率
  lint pp, qq; cin >> pp >> qq;
  p = pp * modinv(qq, MOD) % MOD;
  
  SquareMatrix<modint> mat(2);
  mat[0][0] = mat[1][1] = modint(1 - p);
  mat[1][0] = mat[0][1] = modint(p);
  
  mat = mat.pow(k);
  
  modint tapi = 0;
  modint oka = 0;
  for(int i = 1; i <= n; i++) {
    lint b; cin >> b;
    if(i <= m) tapi += b;
    else oka += b;
  }

  modint ak = mat[0][0];
  modint bk = mat[1][0];

  cout << (tapi * ak + oka * bk).v << endl;
  return 0;
}
0