[CTS2019]珍珠解题报告

有 (n) 个珍珠，每个珍珠会等概率拥有一个在 ([1,D]) 内的颜色，希望得到的珍珠可以装进 (m) 个瓶子里，使得每个瓶子里都有两个颜色一样的珍珠，求愿望实现的概率，答案乘上 (D^n) 再对 (998244353) 取模。

(n,mle 10^9 , Dle 10^5) 。

答案乘上 (D^n) 就是满足条件的个数，所以这是一道计数题。

第一步先将题目给出的条件转化为数学语言，设 (gs_x) 为颜色为 (x) 的珍珠的个数，那么有

[egin{cases}sumlimits_{i=1}^D gs_i = n\sumlimits_{i=1}^D leftlfloorfrac{gs_i}{2} ight floor ge mend{cases} ]

整合一下就有 (sumlimits_{i=1}^D gs_i\%2 le n-2m) ，如果像我一样想着直接做，那么就要处理一个将 (n) 个数分成 (D) 个子集，要求每个子集的大小是偶数这样一个东西，然后就会发现很难去重，如果用生成函数就要维护两个和式。

这时就要套路的运用二项式反演将恰好 (k) 个转为钦定 (k) 个，其余随便，设 (g_x) 为恰好有 (x) 个奇数的方案数， (f_x) 为钦定 (x) 个为奇数，其余随便的方案数，那么有 (f_x=sumlimits_{i=x}^D inom{i}{x} g_i) ，根据二项式反演有 (g_x=sumlimits_{i=x}^D (-1)^{i-x} inom{i}{x} f_i) ，最后答案是 (sumlimits_{i=0}^{n-2m} g_i) 。

可以使用生成函数计算 (f_x) 的值，首先有大小为奇数的 (EGF{[0,1,0,1,...]}=sumlimits_{i=0}^{infty} frac{1^i-(-1)^ix^i}{2i!}=frac{e^x-e^{-x}}{2}) ，那么有

[egin{aligned} f_k & =inom{D}{k}n![x^n](frac{e_x-e^{-x}}{2})^k (e^x)^{D-k} \ & =inom{D}{k}frac{n!}{2^k}[x^n]sumlimits_{i=0}^k inom{k}{i} e^{ix} (-e)^{-(k-i)x} e^{(D-k)x} \ & =inom{D}{k}frac{n!}{2^k}sumlimits_{i=0}^k inom{k}{i} (-1)^{i} [x^n]e^{(D-2i)x} \ & =inom{D}{k}frac{n!}{2^k}sumlimits_{i=0}^k inom{k}{i} (-1)^{i} frac{(D-2i)^n}{n!} \ & =frac{D!}{(D-k)!2^k}sumlimits_{i=0}^k frac{(-1)^i (D-2i)^n}{i!(k-i)!} end{aligned} ]

显然是卷积的形式，可以用 (NTT) 计算 (f_x) ，然后将二项式反演的式子拆开就是一个差值卷积了。

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int M=4e5+5,JYY=998244353;

int read(){
    int x=0,y=1;char ch=getchar();
    while(ch<'0'||ch>'9') y=(ch=='-'?-1:1),ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*y;
}

int rev[M],wn[35],fac[M],ifac[M];
int qpow(int x,int y){
	int res=1;x%=JYY,y%=(JYY-1);
	for(;y;x=x*x%JYY,y>>=1) if(y&1) res=res*x%JYY;
	return res;
}
void getwn(){
	for(int i=0;i<=25;i++){
		int t=(1<<i);
		wn[i]=qpow(3,(JYY-1)/t);
	}
}

void reverse(int A[],int l,int r){ for(int i=0;i<=(r-l)/2;i++) swap(A[l+i],A[r-i]); }
void NTT(int f[],int L,int inv){
	for(int i=0;i<L;i++) if(i<rev[i]) swap(f[i],f[rev[i]]);
	for(int mid=1,id=1;mid<L;mid<<=1,id++)
		for(int R=mid<<1,j=0;j<L;j+=R)
			for(int k=0,w=1;k<mid;k++,w=w*wn[id]%JYY){
				int u=f[j+k],v=w*f[j+k+mid]%JYY;
				f[j+k]=(u+v)%JYY;
				f[j+k+mid]=(u-v+JYY)%JYY;
			}
	if(inv==-1){
		reverse(f,1,L-1);int nL=qpow(L,JYY-2);
		for(int i=0;i<L;i++) f[i]=f[i]*nL%JYY;
	}
}
void poly_mul(int A[],int B[],int C[],int L1,int L2){
	int len=1,L=0;static int TA[M],TB[M];
	for(;len<L1+L2;len<<=1) L++;
	for(int i=0;i<len;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));
	for(int i=0;i<len;i++) TA[i]=(i<L1?A[i]:0);
	for(int i=0;i<len;i++) TB[i]=(i<L2?B[i]:0);
	NTT(TA,len,1),NTT(TB,len,1);
	for(int i=0;i<len;i++) C[i]=TA[i]*TB[i]%JYY;
	NTT(C,len,-1);
	for(int i=L1+L2-1;i<len;i++) C[i]=0;
}

int D,n,m,Ans=0,a[M],b[M],f[M];
void solve(){
    D=read(),n=read(),m=read();
    if(m+m<=n-D) return (void)(printf("%lld
",qpow(D,n)));
    if(m+m>n) return (void)(printf("0
"));
    fac[0]=fac[1]=ifac[0]=ifac[1]=1;getwn();
    for(int i=2;i<=D;i++) ifac[i]=(JYY-JYY/i)*ifac[JYY%i]%JYY;
    for(int i=2;i<=D;i++) fac[i]=fac[i-1]*i%JYY,ifac[i]=ifac[i-1]*ifac[i]%JYY;
    for(int i=0;i<=D;i++) a[i]=qpow(JYY-1,i)*qpow(D-i-i+JYY,n)%JYY*ifac[i]%JYY,b[i]=ifac[i];
    poly_mul(a,b,f,D+1,D+1);
    for(int i=0;i<=D;i++) f[i]=f[i]*fac[D]%JYY*qpow((JYY+1)/2,i)%JYY*ifac[D-i]%JYY;
    for(int i=0;i<=D;i++) a[i]=f[i]*fac[i]%JYY,b[D-i]=qpow(JYY-1,i)*ifac[i]%JYY;
    poly_mul(a,b,f,D+1,D+1);
    for(int i=0;i<=n-m-m;i++) Ans=(Ans+f[D+i]*ifac[i]%JYY)%JYY;
    printf("%lld
",Ans);
}

signed main(){
	// freopen("shuju.in","r",stdin);
    solve();
}

[CTS2019]珍珠 解题报告

[CTS2019]珍珠解题报告