結果

問題 No.2688 Cell Proliferation (Hard)
ユーザー pockynypockyny
提出日時 2024-04-14 14:18:14
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,574 ms / 4,000 ms
コード長 7,362 bytes
コンパイル時間 2,957 ms
コンパイル使用メモリ 140,544 KB
実行使用メモリ 55,364 KB
最終ジャッジ日時 2024-10-03 13:11:54
合計ジャッジ時間 30,852 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 3 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 139 ms
9,520 KB
testcase_04 AC 1,450 ms
53,752 KB
testcase_05 AC 764 ms
29,260 KB
testcase_06 AC 338 ms
16,028 KB
testcase_07 AC 337 ms
15,940 KB
testcase_08 AC 1,429 ms
52,528 KB
testcase_09 AC 1,441 ms
51,884 KB
testcase_10 AC 1,541 ms
54,072 KB
testcase_11 AC 1,466 ms
53,032 KB
testcase_12 AC 394 ms
16,876 KB
testcase_13 AC 1,545 ms
55,364 KB
testcase_14 AC 1,430 ms
50,072 KB
testcase_15 AC 1,550 ms
55,344 KB
testcase_16 AC 1,418 ms
49,720 KB
testcase_17 AC 801 ms
30,432 KB
testcase_18 AC 1,549 ms
54,192 KB
testcase_19 AC 788 ms
30,568 KB
testcase_20 AC 666 ms
26,976 KB
testcase_21 AC 671 ms
26,876 KB
testcase_22 AC 790 ms
30,124 KB
testcase_23 AC 702 ms
27,504 KB
testcase_24 AC 1,574 ms
53,960 KB
testcase_25 AC 463 ms
17,096 KB
testcase_26 AC 1,558 ms
54,468 KB
testcase_27 AC 834 ms
30,624 KB
testcase_28 AC 1,457 ms
49,836 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <iostream>
#include <vector>
#include <cassert>
#include <atcoder/modint>
#include <atcoder/convolution>

using namespace std;
using namespace atcoder;
using mint = modint998244353;
// verify: https://judge.yosupo.jp/submission/153840
vector<mint> fps_inv(vector<mint> f,int deg = -1){
    if(deg==-1) deg = f.size() - 1;
    assert(f.size());
    assert(f[0].val()!=0);
    vector<mint> g = {(mint)1/f[0]};
    for(int i=1;i<=deg;i<<=1){
        vector<mint> h = convolution(g,f);
        h.resize(2*i);
        for(mint &u:h) u = -u;
        h[0] += 2;
        g = convolution(g,h);
        g.resize(2*i);
    }
    g.resize(deg + 1);
    return g;
}

// vector<mint> fps_derivative(vector<mint> &f){
//     vector<mint> ret;
//     for(int i=1;i<f.size();i++){
//         ret.push_back(f[i]*i);
//     }
//     if(f.size()==1) ret.push_back(0);
//     return ret;
// }

// // get integral f(x) dx, s.t. const = 0;
// vector<mint> fps_integral(vector<mint> &f){
//     vector<mint> g(f.size());
//     for(int i=g.size() - 1;i>=1;i--){
//         g[i] = f[i - 1]/(mint)(i);
//     }
//     g[0] = 0;
//     return g;
// }

// // get log(f) = -sum (1 - f)^n/n 
// vector<mint> fps_log(vector<mint> f,int deg = -1){
//     if(deg==-1) deg = f.size() - 1;
//     assert(f[0].val()==1);
//     vector<mint> g = convolution(fps_derivative(f),fps_inv(f,deg));
//     g.resize(deg + 1);
//     return fps_integral(g);
// }

// // get exp(f) = sum f^i/i!
// vector<mint> fps_exp(vector<mint> f,int deg = -1){
//     if(deg==-1) deg = f.size() - 1;
//     assert(f.size());
//     assert(f[0].val()==0);
//     vector<mint> g = {(mint)1};
//     for(int i=1;i<=deg;i<<=1){
//         vector<mint> h(2*i);
//         h[0] = 1;
//         vector<mint> log_g = fps_log(g,h.size() - 1);
//         for(int j=0;j<h.size();j++) h[j] -= log_g[j];
//         for(int j=0;j<min(f.size(),h.size());j++) h[j] += f[j];
//         g = convolution(g,h);
//         g.resize(2*i);
//     }
//     g.resize(deg + 1);
//     return g;
// }

// using ll = long long;
// const int MX = 1000010;
// mint f[MX],inv[MX],fi[MX];
// constexpr ll mod = 998244353;
// void solve(){
//     inv[1] = 1;
//     for(int i=2;i<MX;i++){
//         inv[i] = mod - (mod/i)*inv[mod%i];
//     }
//     f[0] = fi[0] = 1;
//     for(int i=1;i<MX;i++){
//         f[i] = f[i-1]*i;
//         fi[i] = fi[i-1]*inv[i];
//     }
// }

// // input f(x) output g(x) = f(x + d)
// // 階乗の逆元の計算が必須
// vector<mint> shift(vector<mint> ff,int d){
//     int i,len = ff.size();
//     vector<mint> f1(len + 1),f2(len + 1);
//     mint x = 1;
//     for(i=0;i<len;i++){
//         f1[i] = ff[i]*f[i];
//         f2[len - i] = x*fi[i];
//         x *= d;
//     }
//     vector<mint> f3 = convolution(f1,f2);
//     vector<mint> ret;
//     for(i=len;i<2*len;i++){
//         ret.push_back(f3[i]*fi[i - len]);
//     }
//     return ret;
// }

// // input: s[0] + s[1]x + ... s[n - 1]x^n - 1
// // output: (c[0] - c[1] - .. c[d])s = 0かつc[0] = 1なるcを存在すればどれか一つ
// // copied from: https://nyaannyaan.github.io/library/fps/berlekamp-massey.hpp
// // verified: https://judge.yosupo.jp/submission/199848
// // algorithmの気持ち
// // deg(c) = kの時に s[i] + Σ_{j<k} c[j]*s[i - 1 - j]　を計算する
// // 0ならOKで、0じゃないときは、1個前のcの線形結合で補正項を入れる
// // 今までは成功していてたので、1個前のcの線形結合で補正したら、自分より下はつじつまが合うし、補正を入れるので徐々にあっていく
// template <typename mint>
// vector<mint> BerlekampMassey(const vector<mint> &s) {
//     const int N = (int)s.size();
//     vector<mint> b, c;
//     b.reserve(N + 1);
//     c.reserve(N + 1);
//     b.push_back(mint(1));
//     c.push_back(mint(1));
//     mint y = mint(1);
//     for(int ed = 1; ed <= N; ed++){
//         int l = int(c.size()), m = int(b.size());
//         mint x = 0;
//         for (int i = 0; i < l; i++) x += c[i] * s[ed - l + i];
//         b.emplace_back(mint(0));
//         m++;
//         if(x == mint(0)) continue;
//         mint freq = x / y;
//         if(l < m){
//             auto tmp = c;
//             c.insert(begin(c), m - l, mint(0));
//             for (int i = 0; i < m; i++) c[m - 1 - i] -= freq * b[m - 1 - i];
//             b = tmp;
//             y = x;
//         }else{
//             for (int i = 0; i < m; i++) c[l - 1 - i] -= freq * b[m - 1 - i];
//         }
//     }
//     reverse(begin(c), end(c));
//     return c;
// }

// // BostanMori
// // input: P(x)/Q(x),deg(P(x))<deg(Q(x)),
// // output: [x^N](P(x)/Q(x)) 
// // O(dlog(d)logN), (d := deg(Q(x)))
// // TODO: MSB-firstにするともっと早いらしい
// // verified: https://judge.yosupo.jp/submission/199853
// mint BostanMori(vector<mint> P,vector<mint> Q,ll N){
//     while(N){
//         vector<mint> _Q(Q.size());
//         for(int i=0;i<Q.size();i++) _Q[i] = i&1 ? -Q[i] : Q[i];
//         vector<mint> nP = convolution(P,_Q);
//         vector<mint> nQ = convolution(Q,_Q);
//         Q.resize(nQ.size()/2 + 1);
//         for(int i=0;i<nQ.size();i+=2) Q[i/2] = nQ[i];
//         if(N&1){
//             P.resize(nP.size()/2);
//             for(int i=1;i<nP.size();i+=2) P[i/2] = nP[i];
//         }else{
//             P.resize((nP.size() + 1)/2);
//             for(int i=0;i<nP.size();i+=2) P[i/2] = nP[i];
//         }
//         N /= 2;
//     }
//     return P[0]/Q[0];
// }

// mint pw(mint a,ll x){
//     mint ret = 1;
//     while(x){
//         if(x&1) (ret *= a);
//         (a *= a); x /= 2;
//     }
//     return ret;
// }

// // f^k mod x^N をsparceなfに対して計算
// // [x^0]f \neq 0 を仮定
// // fの非零項がm個で、O(mN) になる
// // verified: https://atcoder.jp/contests/nadafes2022_day1/submissions/52160796
// vector<mint> sparse_pow(vector<mint> &f,int k,int N){
//     assert(f.size());
//     assert(f[0]!=0);
//     mint iv = pw(f[0],mod - 2);
//     vector<pair<int,mint>> ff;
//     for(int i=1;i<f.size();i++){
//         if(f[i].val()) ff.push_back({i,f[i]});
//     }
//     vector<mint> ret(N);
//     ret[0] = pw(f[0],k);
//     for(int i=1;i<N;i++){
//         for(int j=0;j<ff.size();j++){
//             int deg = ff[j].first;
//             if(deg>i) break;
//             ret[i] += ff[j].second*deg*ret[i - deg];
//         }
//         ret[i] *= k;
//         for(int j=0;j<ff.size();j++){
//             int deg = ff[j].first;
//             if(deg>i) break;
//             ret[i] -= ff[j].second*(i - deg)*ret[i - deg];
//         }
//         ret[i] *= inv[i];
//     }
//     return ret;
// }

int main(){
    int p1,p2,q1,q2,t; cin >> p1 >> p2 >> q1 >> q2 >> t;   
    mint p = (mint)p1/(mint)p2; mint q = (mint)q1/(mint)q2;
    vector<mint> g(t + 2),h(t + 1);
    mint pr = 1,a = q;
    for(int i=0;i<=t;i++){
        g[i + 1] = -pr;
        h[i] = pr;
        pr *= a; a *= q;
    }
    g[0] = 1;
    for(int i=1;i<=t;i++) g[i] *= p;
    vector<mint> f = convolution(fps_inv(g),h);
    cout << f[t].val() << "\n";
    // for(int i=0;i<=2;i++) cout << (g[i]*8).val() << " ";
    // cout << "\n";
    // for(int i=0;i<=2;i++) cout << (h[i]*64).val() << " ";
    // cout << "\n";
}
0