「CTS2019」珍珠

题目链接

如果我们设第 \(i\) 种颜色一共出现了 \(cnt_i\) 次，那么不难发现如果方案合法则有 \[ \sum\limits_{i=1}^D\lfloor \frac{cnt_i}{2} \rfloor\geqslant m \] 我们简单推一下式子 \[ \begin{aligned} &\sum\limits_{i=1}^D\lfloor \frac{cnt_i}{2} \rfloor\geqslant m\\ =&\sum\limits_{i=1}^D cnt_i-(cnt_i\bmod 2) \geqslant 2m\\ =&\sum\limits_{i=1}^D cnt_i\bmod 2\leqslant n-2m \end{aligned} \] 即我们要关注 \(cnt_i\) 的奇偶性。

当 \(n-2m\geqslant D\) 或 \(n-2m<0\) 时需要特判一下。

我们设 \(f_i\) 为在满足 \(\sum cnt=n\) 的情况下，\(cnt\) 为奇数的颜色恰好有 \(i\) 个的方案数。由于难以直接算 \(f\)，考虑二项式反演，设 \(g_i\) 为在满足 \(\sum cnt=n\) 的情况下，钦定 \(i\) 个颜色 \(cnt\) 为奇数，剩下任意的方案数。

我们考虑利用生成函数解决这个问题。

不难发现，对于某一个颜色，\(cnt\) 为奇数的方案数所对应的指数生成函数为 \(\frac{e^x-e^{-x}}{2}\)，\(cnt\) 任意的方案数对应的指数生成函数为 \(e^x\)（因为每个珍珠是有编号的，所以用 EGF）。那么有 \[ \begin{aligned} g_i&=\binom{D}{i}n^i(e^x)^{D-i}\\ &=\binom{D}{i}\frac{n!}{2^i}[x^n](e^x-e^{-x})^i(e^x)^{D-i} \end{aligned} \] 然后我们用二项式定理把 \((e^x-e^{-x})^i\) 展开。 \[ \begin{aligned} g_i&=\binom{D}{i}\frac{n!}{2^i}[x^n]\sum\limits_{j=0}^i\binom{i}{j}(e^x)^j(-e^x)^{i-j}(e^x)^{D-i}\\ &=\binom{D}{i}\frac{n!}{2^i}[x^n]\sum\limits_{j=0}^i\binom{i}{j}(-1) ^{i-j}(e^x)^j(e^{-x})^{i-j}(e^x)^{D-i}\\ &=\binom{D}{i}\frac{n!}{2^i}[x^n]\sum\limits_{j=0}^i\binom{i}{j}(-1) ^{i-j}(e^x)^j(e^x)^{j-i}(e^x)^{D-i}\\ &=\binom{D}{i}\frac{n!}{2^i}[x^n]\sum\limits_{j=0}^i\binom{i}{j}(-1) ^{i-j}(e^x)^{D-2(i-j)} \end{aligned} \] 然后我们把 \((e^x)^{D-2(i-j)}\)（它的系数为 \(\frac{(D-2(i-j))^n}{n!}\)）与组合数展开 \[ \begin{aligned} g_i&=\frac{D!}{i!(D-i)!}\frac{n!}{2^i}\sum\limits_{j=0}^i\frac{i!}{j!(i-j)!}(-1) ^{i-j}\frac{(D-2(i-j))^n}{n!}\\ &=\frac{D!}{(D-i)!}\frac{1}{2^i}\sum\limits_{j=0}^i\frac{1}{j!(i-j)!}(-1) ^{i-j}(D-2(i-j))^n\\ &=\frac{D!}{(D-i)!}\frac{1}{2^i}\sum\limits_{j=0}^i\frac{1}{j!(i-j)!}(-1)^{j}(D-2j)^n\\ \end{aligned} \] 注意最后一行用 \(i-j\) 替换了 \(j\)。求和号内部的东西显然是卷积形式，NTT 计算即可。

然后我们需要反演回去，但是不能直接两重 for，复杂度爆炸，注意到二项式反演的式子 \[ \begin{aligned} f_i&=\sum\limits_{j=i}^d\binom{j}{i}(-1)^{j-i}g_j\\ &=\frac{1}{i!}\sum\limits_{j=i}^d\frac{j!}{(j-i)!}(-1)^{j-i}g_j\\ \end{aligned} \] 注意到求和号后面是差一定的形式，把 \(j!g_j\) 的多项式系数反转就可以卷积了。

答案为 \(\sum\limits_{i=0}^{n-2m}f_i\)。注意你差一定的多项式卷完了以后系数也是反的，最后应该取的是多项式的 \(x^{d-n+2m}\) 到 \(x^d\) 项。

代码如下（两次 NTT 之间记得清空）：

#include<bits/stdc++.h>
using namespace std;
int const p=998244353,g=3,gi=(p+1)/3;
int r[400005],F[400005],G[400005],fac[400005],inv[400005];
int pw(int x,int y)
{
    int res=1;
    while(y)
    {
        if(y&1)res=1ll*res*x%p;
        x=1ll*x*x%p;
        y>>=1;
    }
    return res;
}
void ntt(int *f,int n,int op)
{
    for(int i=1;i<n;i++)r[i]=(r[i>>1]>>1)+((i&1)?(n>>1):0);
    for(int i=1;i<n;i++)if(i<r[i])swap(f[i],f[r[i]]);
    for(int len=2;len<=n;len<<=1)
    {
        int q=len>>1,wn=pw(op==1?g:gi,(p-1)/len);
        for(int i=0;i<n;i+=len)
            for(int j=i,w=1;j<i+q;j++,w=1ll*w*wn%p)
            {
                int d=1ll*f[j+q]*w%p;
                f[j+q]=(f[j]-d+p)%p;
                f[j]+=d,f[j]%=p;
            }
    }
    if(op==-1)
    {
        int t=pw(n,p-2);
        for(int i=0;i<n;i++)f[i]=1ll*f[i]*t%p;
    }
}
int main()
{
    int d,n,m;
    scanf("%d%d%d",&d,&n,&m);
    if(n-2*m<0){puts("0");return 0;}
    if(n-2*m>=d){printf("%d",pw(d,n));return 0;}
    fac[0]=inv[0]=1;
    for(int i=1;i<=d;i++)fac[i]=1ll*fac[i-1]*i%p,inv[i]=1ll*inv[i-1]*pw(i,p-2)%p;
    for(int i=0;i<=d;i++)F[i]=inv[i],G[i]=1ll*((i&1)?p-1:1)*inv[i]%p*pw((d-2*i+p)%p,n)%p;
    int lim=1;
    while(lim<=(d<<1))lim<<=1;
    ntt(F,lim,1),ntt(G,lim,1);
    for(int i=0;i<lim;i++)G[i]=1ll*F[i]*G[i]%p;
    ntt(G,lim,-1);
    for(int i=0;i<=d;i++)G[i]=1ll*G[i]*fac[d]%p*inv[d-i]%p*pw(2,p-1-i)%p*fac[i]%p;
    reverse(G,G+d+1);
    for(int i=d+1;i<=lim;i++)F[i]=G[i]=0;
    for(int i=0;i<=d;i++)F[i]=1ll*inv[i]*((i&1)?p-1:1)%p;
    ntt(F,lim,1),ntt(G,lim,1);
    for(int i=0;i<lim;i++)G[i]=1ll*F[i]*G[i]%p;
    ntt(G,lim,-1);
    int ans=0;
    for(int i=d+2*m-n;i<=d;i++)ans+=1ll*G[i]*inv[d-i]%p,ans%=p;
    printf("%d",ans);
    return 0;
}