結果

問題 No.995 タピオカオイシクナーレ
ユーザー ngtkanangtkana
提出日時 2020-03-28 00:15:59
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 12 ms / 2,000 ms
コード長 1,317 bytes
コンパイル時間 2,540 ms
コンパイル使用メモリ 209,080 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-10 16:52:28
合計ジャッジ時間 3,001 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 1 ms
6,944 KB
testcase_09 AC 1 ms
6,940 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 2 ms
6,944 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 2 ms
6,940 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 2 ms
6,940 KB
testcase_16 AC 12 ms
6,940 KB
testcase_17 AC 11 ms
6,944 KB
testcase_18 AC 11 ms
6,944 KB
testcase_19 AC 11 ms
6,940 KB
testcase_20 AC 12 ms
6,944 KB
testcase_21 AC 11 ms
6,944 KB
testcase_22 AC 12 ms
6,944 KB
testcase_23 AC 12 ms
6,940 KB
testcase_24 AC 12 ms
6,944 KB
testcase_25 AC 11 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

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