結果

問題 No.1547 [Cherry 2nd Tune *] 偶然の勝利の確率
ユーザー 沙耶花
提出日時 2021-06-11 22:35:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 146 ms / 2,000 ms
コード長 3,430 bytes
コンパイル時間 4,789 ms
コンパイル使用メモリ 260,324 KB
最終ジャッジ日時 2025-01-22 06:15:50
ジャッジサーバーID
（参考情報） 		judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf 100000000000000000
template <typename T,typename F0,typename F1>
struct matrix{
    F0 func0;
    F1 func1;
    vector<vector<T>> value;
    int height,width;
    T init_value0,init_value1;
    
    matrix(vector<vector<T>> X,F0 f0,F1 f1,T iv0,T iv1):func0(f0),func1(f1){
        height = X.size();
        width = X[0].size();
        value = X;
        init_value0 = iv0,init_value1 = iv1;
    }
    
    matrix(int h,int w,F0 f0,F1 f1,T iv0,T iv1):func0(f0),func1(f1){
        vector<vector<T>> d(h,vector<T>(w,iv0));
        height = h,width = w;
        value = d;
        init_value0 = iv0,init_value1 = iv1;
    }
    
    
    void set_1(){
        for(int i=0;i<height;i++){
            for(int j=0;j<width;j++){
                if(i==j)value[i][j] = init_value1;
                else value[i][j]=init_value0;
            }
        }
    }
    
    void show(){
        for(int i=0;i<height;i++){
            for(int j=0;j<width;j++){
                if(j!=0)cout<<' ';
                cout<<value[i][j];
            }
            cout<<endl;
        }
    }
    
    matrix &operator=(const matrix &another){
        value = another.value;
        height = another.height;
        width = another.width;
        return *this;
    }
    
    matrix &operator*=(const matrix &another){
        matrix<T,decltype(func0),decltype(func1)> R(height,another.width,func0,func1,init_value0,init_value1);
        for(int i=0;i<R.value.size();i++){
            for(int j=0;j<R.value[i].size();j++){
                R.value[i][j]=init_value0;
                for(int k=0;k<width;k++){
                    R.value[i][j] = func0(R.value[i][j],func1(value[i][k],another.value[k][j]));
                }
            }
        }
        value = R.value;
        return (*this);
    }
    
    matrix operator*(const matrix &another)const{
        return (matrix(*this)*=another);
    }
    
    matrix beki(long long cnt){
        matrix<T,decltype(func0),decltype(func1)> R(height,width,func0,func1,init_value0,init_value1);
        R.set_1();
        auto temp = *this;
        while(cnt!=0LL){
            if(cnt%2==1){
                R *= temp;
            }
            temp *= temp;
            cnt/=2;
        }
        return R;
    }
};
int main(){
    
    mint Pa,Pb;
    
    int S,T;
    
    {
        int x,y;
        cin>>x>>y;
        
        Pa = x;
        Pa /= y;
        cin>>S;
    }
    
    {
        int x,y;
        cin>>x>>y;
        
        Pb= x;
        Pb /= y;
        cin>>T;
    }
    
    //cout<<mint(0).pow(5).val()<<endl;
    
    vector<vector<mint>> A(105,vector<mint>(105,0));
    int c = 52;
    S = c+S;
    T = c-T;
    rep(i,105){
        int cur = i;
        if(cur == S || cur == T){
            A[cur][cur] = 1;
            continue;
        }
        if(cur > S || cur < T)continue;
        
        rep(j,105){
            int c2 = cur + j;
            if(c2 > S)break;
            mint p = Pa.pow(j);
            if(c2 != S){
                p *= mint(1)-Pa;
            }
            else{
                A[c2][cur] = p;
                continue;
            }
            rep(k,105){
                int c3 = c2 - k;
                if(c3 < T)continue;
                mint pp = p * Pb.pow(k);
                if(c3 != T){
                    pp *= mint(1)-Pb;
                }
                /*
                if(i==c&&j==0&&k==0){
                    cout<<c3<<','<<cur<<','<<pp.val()<<endl;
                }
                */
                A[c3][cur] += pp;
            }           
        }
    }
    /*
    for(int i=c;i<=S;i++){
        cout<<i<<','<<c<<endl;
        cout<<i-c<<','<<(A[i][c]*27).val()<<endl;
    }
    */
    
    auto f0 = [](mint a,mint b){
        return a+b;
    };
    
    auto f1 = [](mint a,mint b){
        return a*b;
    };
    
    matrix<mint,decltype(f0),decltype(f1)> AA(A,f0,f1,0,1);
    long long K;
    cin>>K;
    AA = AA.beki(K);
    
    vector<vector<mint>> B(105,vector<mint>(1,0));
    B[c][0] = 1;
    
    matrix<mint,decltype(f0),decltype(f1)> BB(B,f0,f1,0,1);
    
    AA = AA * BB;
    
    mint ans0 = AA.value[S][0];
    mint ans1 = AA.value[T][0];
    
    //cout<<(ans0*81).val()<<endl;
    
    cout<<ans0.val()<<endl<<ans1.val()<<endl;
    
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0