結果

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
//const ull mod = 1e9 + 7;
const ll mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

// debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
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; }

// conversion number to bit
string num2bit(ll num, ll len){
  string bit = "";
  REP(i, len){
    bit += char('0'+(num>>i & 1));
  }
  return bit;
}

typedef vector<ll> arr;
typedef vector<arr> mat;

mat eye(ll n){
	mat I(n, arr(n, 0));
	REP(i, n) I[i][i] = 1;
	return I;
}

mat mul(const mat &A, const mat &B){
	mat C(A.size(), arr(B[0].size(), 0));
	REP(i, C.size()){
		REP(j, C[0].size()){
			REP(k, A[0].size()){
				C[i][j] += A[i][k]*B[k][j];
				C[i][j] %= mod;
			}
		}
	}
	return C;
}

mat matpow(const mat &A, ll k){
	mat res = eye(A.size());
	mat tmp = A;
	REP(i, 64){ // 64より大きい値にするとバグるので注意．long long が64バイトで表現されていることに依存する．65とかでも一見まともに動くがバグってる．
		if(k>>i&1) res = mul(res, tmp);
		tmp = mul(tmp, tmp);
	}
	return res;
}

ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll N, M, K, p, q;
    cin >> N >> M >> K >> p >> q;
    vector<ll> b(N);
    REP(i, N) cin >> b[i];
    ll B = p * modinv(q, mod) % mod;
    ll A = (1 - B + mod)%mod;
    mat X(2, arr(2, 0));
    X[0][0] = A;
    X[0][1] = B;
    X[1][0] = B;
    X[1][1] = A;

    auto Y = matpow(X, K);

    ll res = 0;
    REP(i, N){
    	if(i<M) res += Y[0][0] * b[i] % mod;
    	else res += Y[1][0] * b[i] % mod; 
    	res %= mod;
    }
    cout << res << endl;
    return 0;
}
0