結果

問題 No.995 タピオカオイシクナーレ
コンテスト
ユーザー yapoo
提出日時 2020-02-21 22:17:28
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 43 ms / 2,000 ms
コード長 1,379 bytes
コンパイル時間 1,646 ms
コンパイル使用メモリ 171,368 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-08 22:50:55
合計ジャッジ時間 3,249 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;

const ll mod = 1e9+7;

struct Matrix{
    Matrix(ll A, ll B, ll C, ll D){
        a = A%mod;  b = B%mod;  c = C%mod;  d = D%mod;
    }
    Matrix operator *(const Matrix &Y){
        return Matrix(
            (this->a*Y.a + this->b*Y.c)%mod,
            (this->a*Y.b + this->b*Y.d)%mod,
            (this->c*Y.a + this->d*Y.c)%mod,
            (this->c*Y.b + this->d*Y.d)%mod
        );
    }

    ll a, b, c, d;
};

Matrix mod_pow(Matrix X, ll p){
    if(p==0) return Matrix(1,0,0,1);
    Matrix res = mod_pow(X*X, p/2);
    if(p%2==1)
    res = res * X;
    return res;
}

ll mod_pow(ll n, ll p, ll mod){
    n %= mod;
    // return (n^p) % mod
    if(p==0) return 1;
    ll res = mod_pow(n*n%mod, p/2, mod);
    if(p%2==1) res = res * n % mod;
    return res;
}

int main(){
    ll N, M, K, p, q;
    cin >> N >> M >> K >> p >> q;
    vector<ll> b(N);
    for(int i=0; i<N; i++)
        cin >> b[i];
    
    ll A = ((q-p) * mod_pow(q, mod-2, mod))%mod;
    ll B = (p * mod_pow(q, mod-2, mod))%mod;
    Matrix X = Matrix(A, B, B, A);
    Matrix Y = mod_pow(X, K);

    ll ans = 0;
    for(int i=0; i<N; i++){
        if(i<M){
            ans = (ans + (Y.a*b[i]%mod))%mod;
        }else{
            ans = (ans + (Y.b*b[i]%mod))%mod;
        }
    }
    cout << ans%mod << endl;
}
0