[CTS2019]珍珠 | GVZ's Blog

首先我们考虑， $i$ 有 $cnt_i$ 个，那么最多能填满的瓶子的个数就是 $\sum_{i=1}^D \lfloor \frac{cnt_i}{2}\rfloor$

很容易发现，当 $cnt_i$ 为奇数的时候，最多能填满的瓶子个数和 $cnt_i-1$ 时是一样的，所以多的那一个珍珠就被“浪费”了。那么设 $cnt_{odd}=\sum_{i=1}^D[cnt_i\bmod2\neq 0]$ 。那么最多能填满的个数就是 $\frac{(\sum_{i=1}^Dcnt_i)-cnt_{odd}}{2}$ ，方案合法当且仅当 $\frac{(\sum_{i=1}^Dcnt_i)-cnt_{odd}}{2}\geq m$ ，也就是说 $cnt_{odd}\leq n-2m$ 。

特判一下，显然有 $2m\leq n-D$ 时 $ans=D^n$ ， $2m>n$ 时 $ans=0$ 。

令 $odd_i$ 为有 $i$ 个元素个数（即 $cnt$ ）为奇数的方案数。则最后的答案就是 $ans=\sum_{i=0}^{n-2m}odd_i$ 。

记 $f(n)$ 表示 “钦定（指定） $n$ 个作为奇数”， $g(n)$ 表示 “恰好选 $n$ 个”，则对于任意的 $i\geq n$ ， $g(i)$ 在 $f(n)$ 中被计算了 $\binom{i}{n}$ 次，故 $f(n)=∑_{i=n}^m\binom{i}{n} g(i)$ ，其中 $m$ 是数目上界。

**注意：在定义中， $f(n)$ 表示先钦定（指定） $n$ 个为奇数，其他的随意选，再统计钦定情况如此的方案数，其中会包含重复的方案，因为一个方案可以有多种钦定情况。具体地，对于恰好选择 $i$ 个，钦定情况数为 $\binom{i}{n}$ ，故 $g(i)$ 在 $f(i)$ 中被计算了 $\binom{i}{n}$ 次。切勿将 $f(n)$ 来理解为普通的后缀和。**转自二项式反演及其应用

二项式反演的结论就是：

f(n)=\sum\limits_{i=0}^n{n\choose i}g(i)\Leftrightarrow g(n)=\sum\limits_{i=0}^n(-1)^{n-i}{n\choose i}f(i)

f(n)=\sum\limits_{i=n}^m{i\choose n}g(i)\Leftrightarrow g(n)=\sum\limits_{i=n}^m(-1)^{i-n}{i\choose n}f(i)

那么有 $f_k=\sum_{i=k}^D\binom{i}{k}odd_i$ 。

然后二项式反演一波：

\begin{aligned} \operatorname{odd}_{i} &=\sum_{j=i}^D(-1)^{j-i}\left(\begin{array}{c} j \\ i \end{array}\right) f_{j} \\ &=\sum_{j=i}^D(-1)^{j-i} \frac{j !}{i !(j-i) !} f_{j} \end{aligned}

因为我们想要两个变量( $j-i$ ， $j$ )的和为一个定值（只和 $i$ 相关），所以我们令 $G(D-j)=j!f_j$ ，然后把 $G$ 代入进去即可。最后 $odd_i$ 的值的位置就在 $(D-j)+(j-i)=D-i$ 这个位置。

我们把问题转换成求 $f$ 。

因为 $f_k$ 是指钦定选 $k$ 个，其他随意的方案数。也就是说我们先枚举组合数 $\binom{D}{k}$ ，然后计算这 $k$ 个选奇数，其余的随意的方案数。因为奇数的 $EGF$ 是 $\frac{e^{x}-e^{-x}}{2}$ 。这里之所以要用 $EGF$ 是因为在这道题里面，生成的随机序列是个排列，顺序不同也算不同的方案数。所以我们枚举了每种元素有多少个后，还要重新给每个元素编号确定位置，所以最后要乘上一个全排列。又因为同一种元素之间的相对顺序进行排列是没有意义的（同种球是完全相同的）。所以我们就要用 $EGF$ 做一个可重排列（除掉每种元素个数的阶乘即可）。（钟神曾经说过， $EGF$ 可以理解成 $OGF$ 多一个系数）

那么写一下柿子：

\begin{aligned} f_{k} &=\left(\begin{array}{l} D \\ k \end{array}\right) n !\left[x^{n}\right]\left(\frac{e^{x}-e^{-x}}{2}\right)^{k}\left(e^{x}\right)^{D-k} \\ &=\left(\begin{array}{l} D \\ k \end{array}\right) \frac{n !}{2^{k}}\left[x^{n}\right]\left(e^{x}-e^{-x}\right)^{k}\left(e^{x}\right)^{D-k} \\ &=\left(\begin{array}{l} D \\ k \end{array}\right) \frac{n !}{2^{k}}\left[x^{n}\right] \sum_{j=0}^{k}\left(\begin{array}{l} k \\ j \end{array}\right) e^{j x}\left(-e^{-x}\right)^{k-j} e^{(D-k) x} \\ &=\left(\begin{array}{l} D \\ k \end{array}\right) \frac{n !}{2^{k}} \sum_{j=0}^{k}\left(\begin{array}{l} k \\ j \end{array}\right)(-1)^{k-j}\left[x^{n}\right] e^{(D-2(k-j)) x} \end{aligned}

中间那一步就是二项式反演： $(a+b)^n=\sum_{i=0}^n\binom{n}{i}a^ib^{n-i}$ ， $\left[x^{n}\right]$ 表示多项式的第 $n$ 项。

换元法搞一下， $e^{a x}=\mathbf{E G F}\left\{\left[1, a, a^{2}, a^{3}, \ldots\right]\right\}$ ，所以有 $\left[x^{n}\right] e^{a x}=\frac{a^{n}}{n !}$ 。

带回去，将枚举 $j$ 换成枚举 $k-j$ ：

\begin{aligned} f_{k} &=\left(\begin{array}{c} D \\ k \end{array}\right) \frac{n !}{2^{k}} \sum_{j=0}^{k}\left(\begin{array}{c} k \\ j \end{array}\right)(-1)^{k-j} \frac{(D-2(k-j))^{n}}{n !} \\ &=\frac{D !}{2^{k}(D-k) !} \sum_{j=0}^{k} \frac{(-1)^{j}(D-2 j)^{n}}{j !} \cdot \frac{1}{(k-j) !} \end{aligned}

这玩意也是一个卷积。然后就可以求 $f$ 啦~求完了按照上个部分的柿子再卷积一下求出 $odd$ 就能直接求答案了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int mod=998244353;
const int maxn=4*2e5+10000;
ll frac[maxn];
ll ksm(ll num,ll t){
	ll res=1;num%=mod;
	for(;t;t>>=1,num=num*num%mod){
		if(t&1)res=num*res%mod;
	}
	return res;
}
struct NTT{
	ll tmp1[maxn],tmp2[maxn],wn[2][maxn];
	int rev[maxn];
	void get_wn(int len){
		for(int l=2;l<=len;l<<=1){
			ll w1=ksm(3,(mod-1)/l),w0=ksm(3,mod-1-(mod-1)/l);
			wn[0][l>>1]=wn[1][l>>1]=1;
			for(int j=1;j<(l>>1);j++){
				wn[0][(l>>1)+j]=wn[0][(l>>1)+j-1]*w0%mod;
				wn[1][(l>>1)+j]=wn[1][(l>>1)+j-1]*w1%mod;
			}
		}
	}
	NTT(){int top=maxn/2;int len=1,cnt=0;while(len<=top)len<<=1,cnt++;get_wn(len);}
	void get_rev(int cnt){rep(i,1,1<<cnt)rev[i]=(rev[i>>1]>>1)|((i&1)<<(cnt-1));}
	void ntt(int len,ll *c,int f){
		for(int i=0;i<len;i++)if(rev[i]>i)swap(c[rev[i]],c[i]);
		for(int l=2;l<=len;l<<=1){
			for(int i=0;i+l<=len;i+=l){
				for(int j=i;j<i+(l>>1);j++){
					ll tmp0=c[j],tmp1=1ll*c[j+(l>>1)]*wn[f][j-i+(l>>1)]%mod;
					c[j]=(tmp0+tmp1)%mod;
					c[j+(l>>1)]=((tmp0-tmp1)%mod+mod)%mod;
				}
			}
		}
		if(!f){
			ll inv=ksm(len,mod-2);
			rep(i,0,len-1)c[i]=c[i]*inv%mod;
		}
	}
	vi mul(const vi &a,const vi &b){
		int l1=a.size(),l2=b.size();int len=1,cnt=0;while(len<=l1+l2)len<<=1,cnt++;
		get_rev(cnt); 
		rep(i,0,len)tmp1[i]=tmp2[i]=0;
		rep(i,0,l1-1)tmp1[i]=a[i];
		rep(i,0,l2-1)tmp2[i]=b[i];
		ntt(len,tmp1,1);ntt(len,tmp2,1);
		for(int i=0;i<len;i++)tmp1[i]=tmp1[i]*tmp2[i]%mod;
		ntt(len,tmp1,0);
		vi re;
		for(int i=0;i<l1+l2;i++)re.pb(tmp1[i]);
		return re;
	}
}t;
int main(){
	//freopen("in","r",stdin);
	frac[0]=frac[1]=1;rep(i,2,maxn-1)frac[i]=frac[i-1]*i%mod;
	int D,n,m;scanf("%d%d%d",&D,&n,&m);
	if(2*m<=n-D){printf("%lld",ksm(D,n)%mod);return 0;}
	if(2*m>n){printf("0");return 0;}
	vi tmp1,tmp2;
	rep(j,0,D){
		tmp1.pb(ksm(-1,j)*ksm(D-2*j,n)%mod*ksm(frac[j],mod-2)%mod);
		tmp2.pb(ksm(frac[j],mod-2));
	}
	vi f1=t.mul(tmp1,tmp2);vi f2=f1;vi G;G.resize(f2.size()); 	
	rep(i,0,D)f1[i]=1ll*f1[i]*frac[D]%mod*ksm(ksm(2,i)*frac[D-i]%mod,mod-2)%mod;
	//cout<<">>f1 "<<f1[0]<<' '<<f1[1]<<' '<<f1[2]<<endl;
	rep(i,0,D)f2[i]=1ll*f1[D-i]*frac[D-i]%mod;
	//cout<<">>f2 "<<f2[0]<<' '<<f2[1]<<' '<<f2[2]<<endl;
	rep(i,0,D)G[i]=1ll*ksm(-1,i)*ksm(frac[i],mod-2)%mod;
	//cout<<">>G "<<G[0]<<' '<<G[1]<<' '<<G[2]<<endl;
	vi ans=t.mul(f2,G);
	rep(i,0,D)ans[i]=1ll*ans[i]*ksm(frac[D-i],mod-2)%mod;
	ll out=0;
	rep(i,0,n-2*m)out+=ans[D-i];
	cout<<out%mod;
	return 0;
}