結果

問題 No.2688 Cell Proliferation (Hard)
ユーザー nonon
提出日時 2024-03-20 22:43:49
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,778 ms / 4,000 ms
コード長 4,142 bytes
コンパイル時間 2,690 ms
コンパイル使用メモリ 211,996 KB
最終ジャッジ日時 2025-02-20 09:45:49
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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