[TJOI2019]唱，跳，rap，篮球（生成函数，组合数学，NTT）

算是补了个万年大坑了吧。

根据 wwj 的题解（最准确），设一个方案 \(S\)（不一定合法）的鸡你太美组数为 \(w(S)\)。

答案就是 \(\sum\limits_{S}[w(S)=0]\)。

用二项式定理：\(\sum\limits_{S}[w(S)=0]=\sum\limits_{S}(1-1)^{w(S)}=\sum\limits_{S}\sum\limits_{i\ge 0}(-1)^i\binom{w(S)}{i}=\sum\limits_{i\ge 0}(-1)^i\sum\limits_{S}\binom{w(S)}{i}\)。

后面那个求和号，就是求对于所有方案，从鸡你太美组数中选出 \(i\) 组的方案数之和。

枚举被选出的组的位置，这里一共有 \(\binom{n-3i}{i}\) 种方案。（捆绑，一共有 \(n-3i\) 个人，其中 \(i\) 个人是鸡你太美）

剩下的排列方案，枚举每种爱好的人分别有多少个，\(\sum\limits_{w\le a-i}\sum\limits_{x\le b-i}\sum\limits_{y\le c-i}\sum\limits_{z\le d-i}[w+x+y+z=n-4i]\frac{(n-4i)!}{w!x!y!z!}\)。

明显是个卷积，对每个 \(i\) 做一遍 NTT 就好了。

时间复杂度 \(O(n^2\log n)\)。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> PII;

const int maxn=2222,mod=998244353;

#define MP make_pair

#define PB push_back

#define lson o<<1,l,mid

#define rson o<<1|1,mid+1,r

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline ll read(){

	char ch=getchar();ll x=0,f=0;

	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();

	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();

	return f?-x:x;

}

int n,a,b,c,d,fac[maxn],invfac[maxn],A[maxn],B[maxn],C[maxn],D[maxn],F[maxn],lim,l,rev[maxn],ans;

int qpow(int a,int b){

	int ans=1;

	for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) ans=1ll*ans*a%mod;

	return ans;

}

void init(int upr){

	for(lim=1,l=0;lim<upr;lim<<=1,l++);

	FOR(i,0,lim-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));

}

void NTT(int *A,int tp){

	FOR(i,0,lim-1) if(i<rev[i]) swap(A[i],A[rev[i]]);

	for(int i=1;i<lim;i<<=1)

		for(int j=0,Wn=qpow(3,mod-1+tp*(mod-1)/(i<<1));j<lim;j+=i<<1)

			for(int k=0,w=1;k<i;k++,w=1ll*w*Wn%mod){

				int x=A[j+k],y=1ll*A[i+j+k]*w%mod;

				A[j+k]=(x+y)%mod;

				A[i+j+k]=(x-y+mod)%mod;

			}

	if(tp==-1){

		int linv=qpow(lim,mod-2);

		FOR(i,0,lim-1) A[i]=1ll*A[i]*linv%mod;

	}

}

int calc(int x){

	init(a+b+c+d-4*x);

	FOR(i,0,lim-1) A[i]=B[i]=C[i]=D[i]=0;

	FOR(i,0,a-x) A[i]=invfac[i];

	FOR(i,0,b-x) B[i]=invfac[i];

	FOR(i,0,c-x) C[i]=invfac[i];

	FOR(i,0,d-x) D[i]=invfac[i];

	NTT(A,1);NTT(B,1);NTT(C,1);NTT(D,1);

	FOR(i,0,lim-1) F[i]=1ll*A[i]*B[i]%mod*C[i]%mod*D[i]%mod;

	NTT(F,-1);

//	printf("calc(%d),f=%d,fac=%d\n",x,F[n-4*x],fac[n-4*x]);

	return 1ll*fac[n-4*x]*F[n-4*x]%mod;

}

int CCC(int n,int m){

	return 1ll*fac[n]*invfac[m]%mod*invfac[n-m]%mod;

}

int main(){

	n=read();a=read();b=read();c=read();d=read();

	fac[0]=1;

	FOR(i,1,n) fac[i]=1ll*fac[i-1]*i%mod;

	invfac[n]=qpow(fac[n],mod-2);

	ROF(i,n-1,0) invfac[i]=1ll*invfac[i+1]*(i+1)%mod;

	FOR(i,0,min(n/4,min(a,min(b,min(c,d))))){

		int s=1ll*CCC(n-3*i,i)*calc(i)%mod;

//		printf("s=%d\n",s);

		if(i%2==0) ans=(ans+s)%mod;

		else ans=(ans-s+mod)%mod;

	}

	printf("%d\n",ans);

}

巴特西

[TJOI2019]唱，跳，rap，篮球（生成函数，组合数学，NTT）

最新文章

热门文章