题解 | #不可道F题题解（多项式）#

F题多项式。谢谢出题人，题目出的好，答疑很良心，爱了qwq

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
// #define debug(x) cout<<"[debug]"#x<<"="<<x<<endl
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const double eps=1e-8;
const int INF=0x3f3f3f3f;

#ifndef ONLINE_JUDGE
#define debug(...)
#include<debug>
#else
#define debug(...)
#endif

int n,m,k;
namespace NTT
{
    typedef vector<ll> Poly;
    const int mod=998244353,G=3,Gi=332748118;
    const int M=6e5;//TODO
    int bit,tot;
    int rev[M];
    int inv[M];
    int init_inv=[](){
    inv[0]=inv[1]=1;
    for(int i=2;i<M;i++)
        inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    return 0;
    }();
    ll qmi(ll a,ll b,ll p)
    {
        ll res=1;
        while(b)
        {
            if(b&1)
            res=res*a%p;

            a=a*a%p;
            b>>=1;
        }
        return res;
    }
    void NTT(Poly &a,int inv)
    {
        for(int i=0;i<tot;i++)
            if(i<rev[i]) swap(a[i],a[rev[i]]);
    
        for(int mid=1;mid<tot;mid*=2)
        {
            ll w1=qmi(inv==1?G:Gi,(mod-1)/(2*mid),mod);
            for(int i=0;i<tot;i+=mid*2)
            {
                ll wk=1;
                for(int j=0;j<mid;j++,wk=wk*w1%mod)
                {
                    ll x=a[i+j];
                    ll y=wk*a[i+j+mid]%mod;
                    a[i+j]=(x+y)%mod;
                    a[i+j+mid]=(x-y+mod)%mod;
                }
            }
        }
    
        if(inv==-1)//就不用后面除了
        {
            ll intot=qmi(tot,mod-2,mod);
            for(int i=0;i<tot;i++)
            {
                a[i]=a[i]*intot%mod;
            }
        }
    }
    Poly mul(Poly a,Poly b)//deg是系数的数量，所以有0~deg-1次项
    {
        int deg=(int)a.size()+b.size()-1;
        bit=0;
        while((1<<bit)<deg) bit++;//至少要系数的数量
        tot=1<<bit; //系数项为0~tot-1
        for(int i=0;i<tot;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));

        Poly c(tot);
        a.resize(tot),b.resize(tot);
        NTT(a,1),NTT(b,1);
        for(int i=0;i<tot;i++) c[i]=a[i]*b[i]%mod;
        NTT(c,-1);
        c.resize(n+k+1);
        return c;
    }
    Poly operator *(Poly a,Poly b)
    {
        return mul(a,b);
    }
    Poly operator *(Poly a,int t)
    {
        Poly res;
        for(int i=0;i<a.size();i++) res.push_back(1ll*a[i]*t%mod);
        return res;
    }
    Poly operator *(Poly a,ll t)
    {
        Poly res;
        for(int i=0;i<a.size();i++) res.push_back(a[i]*t%mod);
        return res;
    }
    Poly operator +(Poly a,Poly b)
    {
        Poly res(a);
        res.resize(max(a.size(),b.size()));
        for(int i=0;i<b.size();i++) res[i]=(res[i]+b[i])%mod;
        return res;
    }
    Poly operator -(Poly a,Poly b)
    {
        Poly res(a);
        res.resize(max(a.size(),b.size()));
        for(int i=0;i<b.size();i++) res[i]=(res[i]-b[i]+mod)%mod;
        return res;
    }
    Poly Inv(Poly &f,int deg)//多项式f对于x^deg的逆元(注意rev[]等数组要开到2*deg的空间级别,f[]要开deg级别)
    {
        if(deg==1) return Poly(1,qmi(f[0],mod-2,mod));

        Poly B=Inv(f,(deg+1)>>1);//上一个逆元
        Poly A(f.begin(),f.begin()+deg);

        bit=0;
        while((1<<bit)<(deg<<1)) bit++;//至少要系数的数量
        tot=1<<bit; //系数项为0~tot-1
        for(int i=0;i<tot;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
        
        A.resize(tot),B.resize(tot);
        NTT(A,1),NTT(B,1);
        for(int i=0;i<tot;i++)
        A[i]=B[i]*(2-A[i]*B[i]%mod+mod)%mod;
        NTT(A,-1);
        A.resize(deg);
        return A;
    }
    Poly cdq_ntt(int l,int r,vector<Poly> &f)
    {
        if(l==r) return f[l];
        int mid=l+r>>1;
        return mul(cdq_ntt(l,mid,f),cdq_ntt(mid+1,r,f));
    }
    namespace Cipolla
    {
        int W;
        struct cp
        {
            ll x,y;
            cp(ll x=0,ll y=0): x(x),y(y) {}
            cp operator+ (const cp _)const{
                return {(x+_.x)%mod,(y+_.y)%mod};
            } 
            cp operator* (const cp _)const{
                return {(x*_.x%mod+y*_.y%mod*W%mod)%mod,(x*_.y+y*_.x)%mod};
            }
        };
        cp qmi(cp a,int b)
        {
            cp res=1;
            while(b)
            {
                if(b&1) res=res*a;

                a=a*a;
                b>>=1;
            }
            return res;
        }
        int cipolla(int n)
        {
            if(qmi(n,(mod-1)>>1).x!=1)
            {
                return -1;
            }
            int a=rand()%mod;
            while(!a||qmi((1ll*a*a-n+mod)%mod,(mod-1)>>1).x==1)
            {
                a=rand()%mod;
            }
            W=(1ll*a*a-n+mod)%mod;

            int x=qmi(cp(a,1),(mod+1)>>1).x;
            if(x>mod-x) x=mod-x;
            return x;
        }
    }
    Poly Sqrt(Poly &A,int deg)
    {
        if(deg==1)
        {
            return {Cipolla::cipolla(A[0])};//A[0]=1修改这里即可
        }

        Poly f0=Sqrt(A,(deg+1)>>1);
        f0.resize(deg);
        Poly inf0=Inv(f0,deg);
        Poly temp(A.begin(),A.begin()+deg);
        temp=mul(inf0,temp);
        temp.resize(deg);
        for(int i=0;i<deg;i++) f0[i]=(f0[i]+temp[i])*inv[2]%mod;

        return f0;
    }
    Poly Deriv(Poly f)//求导
    {
        for(int i=0;i<f.size();i++) f[i]=f[i+1]*(i+1)%mod;
        f.pop_back();
        return f;
    }
    Poly Integ(Poly f)//积分
    {
        f.push_back(0);
        for(int i=f.size()-1;i>=1;i--) f[i]=f[i-1]*inv[i]%mod;
        f[0]=0;
        return f;
    }
    Poly Ln(Poly f,int deg)//f[0]=1
    {
        f=mul(Deriv(f),Inv(f,deg));
        f.resize(deg-1);
        return Integ(f);
    }
    Poly Exp(Poly &A,int deg)//A[0]=0，记得至少开deg大小
    {
        if(deg==1) return {1};
        Poly f0=Exp(A,(deg+1)>>1);
        Poly temp=f0;
        temp.resize(deg);
        temp=Ln(temp,deg);
        for(int i=0;i<deg;i++) temp[i]=(A[i]-temp[i]+mod)%mod;
        temp[0]=(temp[0]+1)%mod;
        temp=mul(f0,temp);
        temp.resize(deg);
        return temp;
    }
    Poly qmi_ntt(Poly A,int k,int deg=-1)//A(x)^k且A[0]=1
    {
        if(deg==-1) deg=(A.size()-1)*k+1;
        A.resize(deg);
        A=Ln(A,deg);
        A=A*k;
        A=Exp(A,deg);
        return A;
    }
    Poly qmi_ntt(Poly A,string s,int deg=-1)//A(x)^k
    {
        ll k=0;//mod (p)
        ll kk=0;//mod (p-1),即phi(p)
        bool ty=false;
        for(int i=0;i<s.size();i++)
        {
            k=(1ll*k*10+(s[i]-'0'));
            if(k>=mod) k%=mod,ty=true;
            kk=(1ll*kk*10+(s[i]-'0'))%(mod-1);
        }
        if(deg==-1) deg=(A.size()-1)*k+1;
        A.resize(deg);
        int n=A.size();
        int t=0;
        while(t<n&&!A[t]) t++;

        if(t==n||ty&&t>=1)
        {
            return Poly(n,0);
        }
        ll temp=qmi(A[t],mod-2,mod);
        Poly B;
        for(int i=t;i<A.size();i++) B.push_back(A[i]*temp%mod);
        B=Ln(B,B.size());
        B=B*k;
        B=Exp(B,B.size());
        B.resize(n);
        Poly res(n);
        temp=qmi(A[t],kk,mod);
        for(ll i=1ll*t*k;i<n;i++) res[i]=B[i-1ll*t*k]*temp%mod;
        return res;
    }
    Poly psqmi_ntt(Poly A,int k)
    {
        Poly res(1,1);
        while(k)
        {
            if(k&1) res=res*A;
            A=A*A;
            k>>=1;
        }
        return res;
    }
}
using namespace NTT;

const int N=100005;
int fact[N],infact[N];
void init(int n)
{
    fact[0]=1;
    for(int i=1;i<=n;i++)
    {
        fact[i]=1ll*fact[i-1]*i%mod;
    }

    infact[n]=qmi(fact[n],mod-2,mod);
    for(int i=n-1;i>=0;i--)
    {
        infact[i]=1ll*infact[i+1]*(i+1)%mod;
    }
}
int main()
{
    init(N-1);
    scanf("%d%d%d",&n,&m,&k);
    Poly A(n+k+1),B(n+k+1),C(n+k+1);
    for(int i=0;i<=n;i++)
    {
        C[i]=infact[i];
        if(i<k) A[i]=infact[i];
        else B[i-k]=infact[i];
    }
    Poly Am=qmi_ntt(A,m,n+k+1);
    Poly res=qmi_ntt(C,m+1,n+k+1)-Am*C*(m+1)+Am*A*m;
    res=res*Inv(B,n+1);
    ll ans=res[n+k]*fact[n]%mod*qmi(qmi(m,n,mod),mod-2,mod)%mod;
    printf("%lld\n",ans);
}