[CTS2019]珍珠（NTT+生成函数+组合计数+容斥）

这题72分做法挺显然的（也是我VP的分）：

对于n,D<=5000的数据，可以记录f[i][j]表示到第i次随机有j个数字未匹配的方案，直接O(nD)的DP转移即可。

对于D<=300的数据，根据转移系数建立矩阵，跑一遍矩阵快速幂，复杂度O(D³logn)，不过要注意卡常数，因为是稀疏矩阵可以判掉无用状态。

对于m较小数据，m=0快速幂，m=1为Dⁿ-A(n,D)，m=2暴力讨论一下有没有出现>=1次的值，如果有，唯一出现>=1次的值是出现2次还是3次。

当然还是水平低啊不会正解。正解是生成函数。转化是对的，匹配数>=m就是未匹配的数<=min(D,n-2m)，未匹配的数实际上就是出现奇数次的数。一个数出现奇数次的生成函数是：(e^x+e^-x)/2，偶数次为：(e^x-e^-x)/2。然后ans=n!(Σ((e^x+e^-x)/2+y(e^x-e^-x)/2)^D[xⁿ][y^k])，其中0<=k<=n-2m，由于我不会用LaTeX，打数学公式太长太慢了，直接写最终式子的结果：ans=(1/2)^DΣC(D,i)(2i-D)ⁿΣ(1-y)ⁱ(1-y)^D-i[y^k]，其中0<=i<=D，0<=k<=n-2m，然后将式子展开后发现后面的是一个阶乘式，阶乘展开后又是一个卷积形式，再加上mod=998244353，直接NTT处理即可。

#include<bits/stdc++.h>

using namespace std;

const int N=3e5+,mod=,inv2=;

int D,n,m,nn,ans,fac[N],inv[N],R[N],f[N],A[N],B[N];

int qpow(int a,int b)

{

    int ret=;

    while(b)

    {

        if(b&)ret=1ll*ret*a%mod;

        a=1ll*a*a%mod,b>>=;

    }

    return ret;

}

void NTT(int*a,int tp)

{

    for(int i=;i<nn;i++)if(i<R[i])swap(a[i],a[R[i]]);

    for(int i=;i<nn;i<<=)

    {

        int wn=qpow(,mod/(i<<));

        if(tp==-)wn=qpow(wn,mod-);

        for(int j=;j<nn;j+=i<<)

        for(int k=,w=;k<i;k++,w=1ll*w*wn%mod)

        {

            int x=a[j+k],y=1ll*w*a[i+j+k]%mod;

            a[j+k]=(x+y)%mod,a[i+j+k]=(x-y+mod)%mod;

        }

    }

    if(tp==)return;

    int invn=qpow(nn,mod-);

    for(int i=;i<nn;i++)a[i]=1ll*a[i]*invn%mod;

}

int C(int a,int b){return 1ll*fac[a]*inv[b]%mod*inv[a-b]%mod;}

int main()

{

    scanf("%d%d%d",&D,&n,&m);

    m=n-*m;

    fac[]=;for(int i=;i<=1e5;i++)fac[i]=1ll*fac[i-]*i%mod;

    inv[]=qpow(fac[],mod-);for(int i=1e5;i;i--)inv[i-]=1ll*inv[i]*i%mod;

    if(m>=D){printf("%d",qpow(D,n));return ;}

    if(m<=)

    {

        for(int i=-D;i<=D;i++)

        if((D+i)%==)ans=(ans+1ll*qpow(i+mod,n)*C(D,D+i>>))%mod;

        ans=1ll*ans*qpow(inv2,D)%mod;

        printf("%d",ans);

        return ;

    }

    A[]=;for(int i=;i<=D;i++)A[i]=1ll*C(i-,m)*(m&?mod-:)%mod;

    reverse(A,A+D+);

    for(int i=;i<=D;i++)A[i]=1ll*A[i]*qpow(,i)%mod*inv[i]%mod;

    for(int i=;i<=D;i++)B[i]=1ll*inv[i]*(i&?mod-:)%mod;

    nn=;int L=;

    while(nn<=D*)nn*=,L++;

    for(int i=;i<nn;i++)R[i]=R[i>>]>>|((i&)<<L-);

    NTT(A,),NTT(B,);

    for(int i=;i<nn;i++)f[i]=1ll*A[i]*B[i]%mod;

    NTT(f,-);

    for(int i=;i<=D;i++)ans=(ans+1ll*C(D,i)*qpow(mod+*i-D,n)%mod*f[i]%mod*fac[i])%mod;

    ans=1ll*ans*qpow(inv2,D)%mod;

    printf("%d",ans);

}

巴特西

[CTS2019]珍珠（NTT+生成函数+组合计数+容斥）

最新文章

热门文章