Luogu5401 CTS2019珍珠（生成函数+容斥原理+NTT）

　　显然相当于求有不超过n-2m种颜色出现奇数次的方案数。由于相当于是对各种颜色选定出现次数后有序排列，可以考虑EGF。

　　容易构造出EGF(e^x-e^-x)/2=Σx^2k+1/(2k+1)!，即表示该颜色只能选奇数个。同理有EGF(e^x+e^-x)/2=Σx^2k/(2k)!，即表示该颜色只能选偶数个。

　　考虑暴力枚举有多少种颜色出现了奇数次。不妨设恰有i种颜色出现了奇数次的方案数为f(i)，那么f(i)=n!·C(D,i)·[xⁿ](((e^x-e^-x)/2)ⁱ·((e^x+e^-x)/2)^D-i)，答案显然为Σf(i) (i=0~n-2m)。

　　然而看了一眼题解这种求f(i)的方式可能有点麻烦，不妨考虑容斥，设g(i)为钦定有i种颜色出现了奇数次的方案数，则显然有f(i)=Σ(-1)^j-i·C(j,i)·g(j)。如果求得了所有g(i)，f(i)显然可以NTT计算。

　　于是考虑求g(i)，有g(i)=n!·C(D,i)·[xⁿ](((e^x-e^-x)/2)ⁱ·(e^x)^D-i)，后一个EGF变的更简单，更易推导。使用二项式定理暴力展开前一个EGF，有g(i)=n!·C(D,i)·[xⁿ](ΣC(i,j)·(-1)^j·e^-jx·e^(i-j)x)·e⁽^D-i)x/2ⁱ，指数相加后变成异常优美的g(i)=n!·C(D,i)·[xⁿ](ΣC(i,j)·(-1)^j·e⁽^D-2j)x)/2ⁱ。由泰勒展开容易知道[xⁿ]e⁽^D-2j)x=(D-2j)ⁿ/n!。于是g(i)=C(D,i)/2ⁱ·ΣC(i,j)·(-1)^j·(D-2j)ⁿ。同样是卷积形式，NTT计算即可。

　　虽然推导过程看起来很简单，但这辈子都不可能会的。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define P 998244353

#define N 550000

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int D,n,m,f[N],g[N],r[N],fac[N],inv[N],ans;

int ksm(int a,int k)

{

	if (a<0) a+=P;

	int s=1;

	for (;k;k>>=1,a=1ll*a*a%P) if (k&1) s=1ll*s*a%P;

	return s;

}

int Inv(int a){return ksm(a,P-2);}

void DFT(int *a,int n,int g)

{

	for (int i=0;i<n;i++) if (i<r[i]) swap(a[i],a[r[i]]);

	for (int i=2;i<=n;i<<=1)

	{

		int wn=ksm(g,(P-1)/i);

		for (int j=0;j<n;j+=i)

		{

			int w=1;

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

			{

				int x=a[k],y=1ll*w*a[k+(i>>1)]%P;

				a[k]=(x+y)%P,a[k+(i>>1)]=(x-y+P)%P;

			}

		}

	}

}

void FFT(int *f,int *g,int t)

{

	DFT(f,t,3),DFT(g,t,3);

	for (int i=0;i<t;i++) f[i]=1ll*f[i]*g[i]%P;

	DFT(f,t,Inv(3));

	for (int i=0;i<t;i++) f[i]=1ll*f[i]*Inv(t)%P;

}

int C(int n,int m){return 1ll*fac[n]*inv[m]%P*inv[n-m]%P;}

int main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

	const char LL[]="%I64d\n";

#else

	const char LL[]="%lld\n";

#endif

	D=read(),n=read(),m=read();

	m=n-2*m;

	if (m>=D) {cout<<ksm(D,n);return 0;}

	if (m<0) {cout<<0;return 0;}

	fac[0]=1;for (int i=1;i<=D;i++) fac[i]=1ll*fac[i-1]*i%P;

	inv[0]=inv[1]=1;for (int i=2;i<=D;i++) inv[i]=P-1ll*(P/i)*inv[P%i]%P;

	for (int i=2;i<=D;i++) inv[i]=1ll*inv[i-1]*inv[i]%P;

	int t=1;while (t<=(D<<1)) t<<=1;

	for (int i=0;i<t;i++) r[i]=(r[i>>1]>>1)|(i&1)*(t>>1);

	for (int i=0;i<=D;i++) f[i]=1ll*ksm(-1,i)*ksm(D-2*i,n)%P*inv[i]%P;

	for (int i=0;i<=D;i++) g[i]=inv[i];

	FFT(f,g,t);

	for (int i=0;i<=D;i++) f[i]=1ll*f[i]*fac[i]%P*ksm(Inv(2),i)%P*C(D,i)%P;

	for (int i=0;i<=D;i++) f[i]=1ll*f[i]*fac[i]%P;

	for (int i=D+1;i<t;i++) f[i]=0;

	for (int i=0;i<=D;i++) g[i]=1ll*ksm(-1,i)*inv[i]%P;

	reverse(g,g+D+1);

	for (int i=D+1;i<t;i++) g[i]=0;

	FFT(f,g,t);

	for (int i=D;i<=D+D;i++) f[i]=1ll*f[i]*inv[i-D]%P;

	for (int i=D;i<=D+m;i++) ans=(ans+f[i])%P;

	cout<<ans;

	return 0;

}

巴特西

Luogu5401 CTS2019珍珠（生成函数+容斥原理+NTT）

最新文章

热门文章