結果

問題 No.2688 Cell Proliferation (Hard)
ユーザー nononnonon
提出日時 2024-03-20 22:43:49
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,541 ms / 4,000 ms
コード長 4,142 bytes
コンパイル時間 2,406 ms
コンパイル使用メモリ 220,036 KB
実行使用メモリ 39,676 KB
最終ジャッジ日時 2024-09-30 08:50:42
合計ジャッジ時間 26,826 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
7,416 KB
testcase_01 AC 3 ms
7,452 KB
testcase_02 AC 3 ms
7,436 KB
testcase_03 AC 123 ms
10,428 KB
testcase_04 AC 1,283 ms
33,916 KB
testcase_05 AC 717 ms
24,144 KB
testcase_06 AC 328 ms
15,368 KB
testcase_07 AC 323 ms
15,300 KB
testcase_08 AC 1,207 ms
33,272 KB
testcase_09 AC 1,120 ms
32,640 KB
testcase_10 AC 1,427 ms
38,832 KB
testcase_11 AC 1,248 ms
33,776 KB
testcase_12 AC 383 ms
15,740 KB
testcase_13 AC 1,537 ms
39,664 KB
testcase_14 AC 977 ms
31,628 KB
testcase_15 AC 1,541 ms
39,676 KB
testcase_16 AC 952 ms
31,260 KB
testcase_17 AC 802 ms
24,876 KB
testcase_18 AC 1,442 ms
38,976 KB
testcase_19 AC 807 ms
24,936 KB
testcase_20 AC 484 ms
19,276 KB
testcase_21 AC 473 ms
19,264 KB
testcase_22 AC 775 ms
24,544 KB
testcase_23 AC 538 ms
19,744 KB
testcase_24 AC 1,411 ms
38,688 KB
testcase_25 AC 391 ms
15,936 KB
testcase_26 AC 1,463 ms
39,020 KB
testcase_27 AC 837 ms
24,960 KB
testcase_28 AC 970 ms
31,408 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/modint>
using namespace std;
using mint=atcoder::modint998244353;
template<typename mint>
struct Number_Theoretic_Transform
{
    static vector<mint>dw,dw_inv;
    static int log;
    static mint root;
    static void ntt(vector<mint>& f)
    {
        init();
        const int n=f.size();
        for(int m=n;m>>=1;)
        {
            mint w=1;
            for(int s=0,k=0;s<n;s+=(m<<1))
            {
                for(int i=s,j=s+m;i<s+m;i++,j++)
                {
                    mint x=f[i],y=f[j]*w;
                    f[i]=x+y,f[j]=x-y;
                }
                w*=dw[__builtin_ctz(++k)];
            }
        }
    }
    static void intt(vector<mint>& f, bool flag=true)
    {
        init();
        const int n=f.size();
        for(int m=1;m<n;m<<=1)
        {
            mint w=1;
            for(int s=0,k=0;s<n;s+=(m<<1))
            {
                for(int i=s,j=s+m;i<s+m;i++,j++)
                {
                    mint x=f[i],y=f[j];
                    f[i]=x+y,f[j]=(x-y)*w;
                }
                w*=dw_inv[__builtin_ctz(++k)];
            }
        }
        if(flag)
        {
            mint cef=mint(n).inv();
            for(int i=0;i<n;i++)f[i]*=cef;
        }
    }
private:
    Number_Theoretic_Transform()=default;
    static void init()
    {
        if(!dw.empty())return;
        long long mod=998244353;
        long long tmp=mod-1;
        log=1;
        while(tmp%2==0)
        {
            tmp>>=1;
            log++;
        }
        dw.resize(log);
        dw_inv.resize(log);
        for(int i=0;i<log;i++)
        {
            dw[i]=-root.pow((mod-1)>>(i+2));
            dw_inv[i]=dw[i].inv();
        }
    }
};
template<typename mint>
vector<mint>Number_Theoretic_Transform<mint>::dw=vector<mint>();
template<typename mint>
vector<mint>Number_Theoretic_Transform<mint>::dw_inv=vector<mint>();
template<typename mint>
int Number_Theoretic_Transform<mint>::log=0;
template<typename mint>
mint Number_Theoretic_Transform<mint>::root=mint(3);
template<typename mint>
struct relaxed_convolution
{
    using NTT=Number_Theoretic_Transform<mint>;
    relaxed_convolution(int n_):n(n_),i(0)
    {
        a.resize(n+1);
        b.resize(n+1);
        c.resize(n+1);
    }
    mint get(mint x, mint y)
    {
        assert(i<=n);
        a[i]=x,b[i]=y;
        c[i]+=a[i]*b[0]+(i?b[i]*a[0]:0);
        i++;
        if(i>n)return c[i-1];
        for(int d=1,k=0;d<=i;d<<=1,k++)
        {
            if(i%(2*d)!=d)continue;
            f.assign(2*d,0);
            g.assign(2*d,0);
            if(i==d)
            {
                for(int j=0;j<d;j++)f[j]=a[j];
                for(int j=0;j<d;j++)g[j]=b[j];
                NTT::ntt(f);
                NTT::ntt(g);
                for(int j=0;j<2*d;j++)f[j]*=g[j];
            }
            else
            {
                calc(k);
                for(int j=0;j<d;j++)f[j]=a[i-d+j];
                for(int j=0;j<d;j++)g[j]=b[i-d+j];
                NTT::ntt(f);
                NTT::ntt(g);
                for(int j=0;j<2*d;j++)f[j]=f[j]*bs[k][j]+g[j]*as[k][j];
            }
            NTT::intt(f);
            for(int j=i;j<min(i+d,n+1);j++)c[j]+=f[d+j-i];
        }
        return c[i-1];
    }
private:
    int n,i;
    vector<mint>a,b,c,f,g;
    vector<vector<mint>>as,bs;
    void calc(int k)
    {
        if((int)as.size()<=k)
        {
            as.resize(k+1);
            bs.resize(k+1);
        }
        if(!as[k].empty())return;
        int d=1<<k;
        vector<mint> s(a.begin(),a.begin()+2*d);
        vector<mint> t(b.begin(),b.begin()+2*d);
        NTT::ntt(s);
        NTT::ntt(t);
        as[k]=s,bs[k]=t;
    }
};
long P1,P2,Q1,Q2,T;
mint dp[1<<20];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>P1>>P2>>Q1>>Q2>>T;
    mint P=mint(P1)/P2;
    mint Q=mint(Q1)/Q2;
    relaxed_convolution<mint> F(T+1);
    dp[0]=1;
    for(long i=1;i<=T;i++)
    {
        dp[i]=P*F.get(dp[i-1],Q.pow(i*(i-1)/2));
    }
    mint ans=0;
    for(long i=0;i<=T;i++)ans+=dp[i]*Q.pow((T-i+1)*(T-i)/2);
    cout<<ans.val()<<endl;
}
0