OI题解 - 珍珠(LOJ)

因为我自己也不是很擅长生成函数，所以尽可能写详细点吧

---

# 题面

> LOJ 3120

---

# 解析

首先对题目的要求做一个等价的变形：在 $n$ 个变量中出现次数为奇数的值的个数不超过 $(n-2m)$。

等价也非常显然，如果一个值出现次数为奇数，两两配对后这个值就会剩下一个。如果剩下的个数超过 $n-2m$ 个，那就不足够产生 $m$ 对了。

根据这个，我们定义 $f_i$ 表示出现次数为奇数的值的个数恰好为 $i$ 的方案数，那么答案就是 $\sum\limits_{i=1}^{\min\{D,n-2m\}}f_i$。

但是我们发现这样定义非常难计算（当然可以计算，有一些题解就直接算的，但是我觉得不是很好理解）……所以我们定义 $g_i$ 表示我们先钦定 $i$ 个值的出现次数为奇数，其他值的出现次数不做要求的方案数。

Note. 这里的“钦定”意味着：如果钦定的那 $i$ 个值不同，即使最后的状态一样，也视作不同的方案。

然后借助生成函数来计算 $g_i$，并且要用到指数型生成函数。先把 $g_i$ 的式子列出来：

$$g_i=C_D^in!\times\left\{\left(\frac{e^x-e^{-x}}{2}\right)^i\times(e^x)^{D-i}\right\}[x^n]$$

下面解释一下该式每个部分的含义：

1. $C_D^i$：这里是指组合数，从 $D$ 个值中选定 $i$ 个；

2. $(e^x)^{D-i}$：$e^x$ 对应的是指数型生成函数 $1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\dots$，可以看出 $e^x$ 的意义就是“某一个值的出现次数可以随便取”；$(e^x)^{D-i}$ 就是有 $D-i$ 个值的出现次数可以随便取。

3. $\left(\frac{e^x-e^{-x}}{2}\right)^i$：$\frac{e^x-e^{-x}}{2}=\frac{x}{1!}+\frac{x^3}{3!}+\frac{x^5}{5!}+\dots$，也就是“某一个值的出现次数只能是奇数”；$\left(\frac{e^x-e^{-x}}{2}\right)^i$ 就是钦定的那 $i$ 个值的出现次数只能是奇数；

4. $\left\{\left(\frac{e^x-e^{-x}}{2}\right)^i\times(e^x)^{D-i}\right\}[x^n]$ ：取生成函数中 $x^n$ 项的系数，$x^n$ 表示所有值的总的出现次数为 $n$；

5. $n!\times\left\{\left(\frac{e^x-e^{-x}}{2}\right)^i\times(e^x)^{D-i}\right\}[x^n]$：设在钦定 $i$ 个值出现次数为奇数时，存在方案 $K_i=\{k_{i,1},k_{i,2},\dots,k_{i,D}\}$ （$k_{i,j}$ 表示值 $j$ 的出现次数），且 $K_i$ 的方案数为 $V_i$

   这种出现次数 $K_i$ 对应的珍珠的方案为可重排 $\frac{n!}{k_{i,1}!k_{i,2}!\dots k_{i,D}!}$；

   而生成函数的第 $n$ 项就是 $\sum\limits_{K_i}\frac{V_i}{k_{i,1}!k_{i,2}!\dots k_{i,D}!}$（分子是因为指数型生成函数）；

   于是第 $n$ 项与 $n!$ 相乘就是 $D$ 个值中钦定 $i$ 个出现奇数次的珍珠的方案数。

这个式子再化简一下：

$$\begin{split} g_i&=C_D^in!\times\left\{\frac{\sum_{j=0}^iC_i^j(e^x)^{i-j}(-e^{-x})^{j}}{2^i}\times(e^x)^{D-i}\right\}[x^n]\\ &=C_{D}^i\frac{n!}{2^i}\times\left\{\sum_{j=0}^i C_i^j(-1)^je^{(i-2j)x}\times e^{(D-i)x}\right\}[x^n]\\ &=C_D^i\frac{n!}{2^i}\times\left\{\sum_{j=0}^i\frac{i!}{j!(i-j)!}\times (-1)^j\times e^{(D-2j)x}\right\}[x^n] \end{split}$$

到这一步，就要用到指数型生成函数的一个性质：$e^{ax}$ 的第 $n$ 项为 $\frac{a^n}{n!}$，于是可以继续化简：

$$\begin{split} g_i&=C_D^i\frac{n!}{2^i}\times\left(\sum_{j=0}^i\frac{i!(-1)^j(D-2j)^n}{j!(i-j)!n!}\right)\\ &=\frac{C_D^ii!}{2^i}\times\left(\sum_{j=0}^i\frac{(-1)^j(D-2j)^n}{j!}\times\frac{1}{(i-j)!}\right) \end{split}$$

可以看到等式右边的括号就是一个卷积，于是可以算出 $g_i$。

根据 $g_i,f_i$ 的定义：

$$g_i=\sum_{j=i}^DC_j^if_j$$

这个式子就可以拿来二项式反演（这个我还是不太熟悉，就忽略为什么可以拿来二项式反演了）

$$\begin{split} f_i&=\sum_{j=i}^D(-1)^{j-i}C_{j}^ig_j\\ &=\frac1{i!}\sum_{j=i}^D\frac{(-1)^{j-i}}{(i-j)!}\times j!g_j \end{split}$$

因为 $j-(j-i)=i$ 是个定值，也是可以卷积的（或许叫做减法卷积？）具体方法就是把一个数列先 reverse 一下再卷积，最后卷积得到的数列再 reverse 一下。代码里把这两个 reverse 都标出来了。

---

# 源代码

/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e9,D=4e5,MOD=998244353;
inline int Add(const int &a,const int &b){return a+b>=MOD? a+b-MOD:a+b;}
inline int Sub(const int &a,const int &b){return a-b<0? a-b+MOD:a-b;}
inline int Mul(const int &a,const int &b){return 1ll*a*b%MOD;}
inline int Pow(int a,int b){int r=1;while(b){if(b&1)r=Mul(r,a);a=Mul(a,a);b>>=1;}return r;}

int fac[D+10],ifac[D+10],inv[D+10];
int rev[D+10],lg2[D+10],poww[30],invw[30];
int F[D+10],G[D+10],g[D+10],f[D+10];
int d,n,m;

void Init(){
    fac[0]=1;
    for(int i=1;i<=D;i++) fac[i]=Mul(fac[i-1],i);
    ifac[D]=Pow(fac[D],MOD-2);
    for(int i=D-1;i>=0;i--) ifac[i]=Mul(ifac[i+1],i+1);
    for(int i=1;i<=D;i++) inv[i]=Mul(ifac[i],fac[i-1]);
    lg2[1]=0;
    for(int i=2;i<=D;i++) lg2[i]=lg2[i>>1]+1;
    for(int i=1;i<30;i++){
        poww[i]=Pow(3,(MOD-1)/(1<<i));
        invw[i]=Pow(poww[i],MOD-2);
    }
}
void NTT(int *A,int len,int typ){
    rev[0]=0;
    for(int i=1;i<len;i++){
        rev[i]=rev[i>>1]>>1|((i&1)<<(lg2[len]-1));
        if(rev[i]<i) swap(A[rev[i]],A[i]);
    }
    for(int l=2,t=1,lgl=1;l<=len;l<<=1,t<<=1,lgl++){
        int per=typ==1? poww[lgl]:invw[lgl];
        for(int j=0;j<len;j+=l)
            for(int k=j,cur=1;k<j+t;k++,cur=Mul(cur,per)){
                int tmp=Mul(A[k+t],cur);
                A[k+t]=Sub(A[k],tmp);
                A[k]=Add(A[k],tmp);
            }
    }
    if(typ==1) return;
    for(int i=0;i<len;i++)
        A[i]=Mul(A[i],inv[len]);
}
int Comb(const int &a,const int &b){
    if(a>b) return 0;
    return Mul(Mul(fac[b],ifac[a]),ifac[b-a]);
}
int Model(int x){
    int ret=1;
    while(ret<=x) ret<<=1;
    return ret;
}
int main(){
    Init();
    scanf("%d%d%d",&d,&n,&m);
    for(int i=0;i<=d;i++){
        F[i]=Mul(Pow(Sub(d,i<<1),n),ifac[i]);
        G[i]=ifac[i];
        if(i&1) F[i]=Sub(0,F[i]);
    }
    int len=Model(d<<1);
    NTT(F,len,1),NTT(G,len,1);
    for(int i=0;i<len;i++) g[i]=Mul(F[i],G[i]);
    NTT(g,len,-1);
    for(int i=1,tmp=inv[2];i<=d;i++,tmp=Mul(tmp,inv[2]))
        g[i]=Mul(Mul(g[i],fac[i]),Mul(tmp,Comb(i,d)));
    for(int i=d+1;i<len;i++) g[i]=0;
    memset(F,0,sizeof F),memset(G,0,sizeof G);
    for(int i=0;i<=d;i++){
        //reverse !!
        F[i]=ifac[i];
        if(i&1) F[i]=Sub(0,F[i]);
        G[d-i]=Mul(fac[i],g[i]);
    }
    NTT(F,len,1),NTT(G,len,1);
    for(int i=0;i<len;i++) f[i]=Mul(F[i],G[i]);
    NTT(f,len,-1);
    //reverse !!
    reverse(f,f+d+1);
    int ans=0;
    for(int i=min(d,n-2*m);i>=0;i--)
        ans=Add(ans,Mul(f[i],ifac[i]));
    printf("%d\n",ans);
    return 0;
}

---

THE END

Thanks for reading!

$$\begin{split} “\ &当枯等的光明终于如约而至\\ &焚尽沉默的爱\ 追逐那灰烬所至\\ &纷飞火种之中\ 那红了眼眶的孩子\\ &逃向自由\ 从此刻开始\ ”\\ \text—&\text{—《逃子》By COP} \end{split}$$