結果

問題 No.995 タピオカオイシクナーレ
コンテスト
ユーザー ngtkana
提出日時 2020-03-28 00:15:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 15 ms / 2,000 ms
コード長 1,317 bytes
コンパイル時間 3,505 ms
コンパイル使用メモリ 198,872 KB
最終ジャッジ日時 2025-01-09 10:33:27
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using lint=long long;
lint mod=1'000'000'007;
lint inverse(lint a, lint m){
    lint u=0,v=1;
    while(a!=0){
        lint t=m/a;
        m-=t*a;std::swap(a,m);
        u-=t*v;std::swap(u,v);
    }
    assert(m==1);
    if(u<mod)u+=mod;
    return u;
}
int main(){
    std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);
    std::cout.setf(std::ios_base::fixed);std::cout.precision(15);
    lint n,m,K,p,q;std::cin>>n>>m>>K>>p>>q;
    p=p*inverse(q,mod)%mod;
    lint A=0,B=0;
    for(lint i=0;i<n;i++){
        lint x;std::cin>>x;
        (i<m?A:B)+=x;
    }
    A%=mod,B%=mod;
    std::vector<std::vector<lint>>zero(2,std::vector<lint>(2));
    auto a=zero;
    for(lint i=0;i<2;i++)for(lint j=0;j<2;j++){
        a.at(i).at(j)=i==j?(mod+1-p)%mod:p;
    }
    auto mul=[zero](auto&&a,auto&&b){
        auto c=zero;
        for(lint i=0;i<2;i++)for(lint j=0;j<2;j++)for(lint k=0;k<2;k++){
            c.at(i).at(k)+=a.at(i).at(j)*b.at(j).at(k);
        }
        for(lint i=0;i<2;i++)for(lint j=0;j<2;j++)c.at(i).at(j)%=mod;
        return c;
    };
    auto b=zero;
    for(lint i=0;i<2;i++)for(lint j=0;j<2;j++){
        b.at(i).at(j)=i==j;
    }
    for(;K;K/=2){
        if(K%2)b=mul(b,a);
        a=mul(a,a);
    }
    std::cout<<(b.at(0).at(0)*A+b.at(0).at(1)*B)%mod<<'\n';
}
0