[loj#3106] [TJOI2019] 唱、跳、rap 和篮球

题意简述

每个学生喜欢唱、跳、\(rap\)、篮球中的一项，喜欢各项的人数分别为 \(a,b,c,d\)
从中选出 \(n\) 个学生排成一列，要求不存在连续4个同学一次喜欢唱、跳、\(rap\)、篮球。
求排列总数，对998244353取模。

\(n\leq 1000\)
\(a,b,c,d\leq 500\)

想法

很经典的容斥题目，然而我太不熟练了……

设 \(f[m]\) 为至少有 \(m\) 堆不符合条件的排列数。
则由二项式反演或广义容斥原理， \(ans=\sum\limits_{i=0}^n (-1)^i\binom{i}{0} f[i]=\sum\limits_{i=0}^n (-1)^i f[i]\)

如何计算 \(f[m]\) 呢？
先将连成一堆的同学打包，然后给它们排位置，共 \(\binom{n-3m}{m}\) 种排法。
然后填剩余同学的爱好。
剩余 \(n-4m\) 个位置，剩 \(a-m,b-m,c-m,d-m\) 个喜欢唱、跳、\(rap\)、篮球的名额。
这是带重复的排列问题，设 \(n-4m\) 个位置中恰有 \(ta,tb,tc,td\) 个喜欢唱、跳、\(rap\)、篮球的同学，那么排列数为 \(\frac{(n-4m)!}{ta!tb!tc!td!}\)
剩余同学的总排列数为 \(\sum\limits_{ta+tb+tc+td=n-4m} \frac{(n-4m)!}{ta!tb!tc!td!}\)
然后怎么搞呢？注意到 \(ta+tb+tc+td=n-4m\) ，这让我们想到卷积（或生成函数）。

设 \(fa(x)=\sum\limits_{i=0}^{a-m} \frac{1}{i!}x^i\) , \(fb(x)=\sum\limits_{i=0}^{b-m} \frac{1}{i!}x^i\)
\(fc(x)=\sum\limits_{i=0}^{c-m} \frac{1}{i!}x^i\), \(fd(x)=\sum\limits_{i=0}^{d-m} \frac{1}{i!}x^i\)
设 \(g(x)=fa(x)fb(x)fc(x)fd(x)\) 的 \(x^{n-4m}\) 的系数为 \(p\)
把 \(fa(x),fb(x),fc(x),fd(x)\) 都正向 \(ntt\) 成点值后全乘起来，之后再逆向 \(ntt\) 求出 \(p\)
剩余同学的总排列数为 \(p(n-4m)!\)

则 \(f[m]=\binom{n-3m}{m}p(n-4m)!\)

求完 \(f[]\) 后代入广义容斥原理的式子就可求出答案了。
总复杂度为 \(O(n^2 logn)\)

总结

模型

一种由至少算恰好的容斥模型吧（广义容斥原理，二项式反演）

二项式反演：
\(f(n)=\sum\limits_{i=0}^n \binom{n}{i} g(i) \Rightarrow g(n)=\sum\limits_{i=0}^n (-1)^{n-i}\binom{n}{i} f(i)\)
\(f(k)=\sum\limits_{i=k}^n \binom{i}{k} g(i) \Rightarrow g(k)=\sum\limits_{i=k}^n (-1)^{i-k}\binom{i}{k} f(i)\)

码力

注意 \(ntt\) 中数组大小的问题。
若两个多项式最高次数为 \(n,m\) (分别 \(n+1,m+1\) 项)，则乘起来后的最高次数为 \(n+m\) (\(n+m+1\) 项)

代码

#include<cstdio>
#include<iostream>
#include<algorithm>

#define P 998244353

using namespace std;

const int N = 2050;

int n,a,b,c,d;
int f[N],C[N][N],mul[N],inv[N];

int Plus(int x,int y) { return x+y>=P ? x+y-P : x+y; }
int Minus(int x,int y) { return x>=y ? x-y : x-y+P; }

int Pow_mod(int x,int y){
	int ret=1;
	while(y){
		if(y&1) ret=1ll*ret*x%P;
		x=1ll*x*x%P;
		y>>=1;
	}
	return ret;
}
int l,r[N],X[N];
void ntt(int *A,int ty){
	for(int i=0;i<l;i++) X[r[i]]=A[i];
	for(int i=0;i<l;i++) A[i]=X[i];
	for(int i=2;i<=l;i<<=1){
		int wn=Pow_mod(3,(P-1)/i);
		if(ty==-1) wn=Pow_mod(wn,P-2);
		for(int j=0;j<l;j+=i){
			int w=1;
			for(int k=j;k<j+i/2;k++){
				int t=1ll*A[k+i/2]*w%P;
				A[k+i/2]=Minus(A[k],t);
				A[k]=Plus(A[k],t);
				w=1ll*w*wn%P;
			}
		}
	}
	if(ty==1) return;
	int Inv=Pow_mod(l,P-2);
	for(int i=0;i<l;i++) A[i]=1ll*A[i]*Inv%P;
}

int x[N],y[N];
void cal(int i){
	l=1;
	while(l<a+b+c+d-4*i) l<<=1;  /**/
	for(int j=1;j<l;j++) r[j]=(r[j>>1]>>1)|((j&1)*(l>>1));
	//[0,a-x]
	for(int j=0;j<=a-i;j++) x[j]=inv[j];
	for(int j=a-i+1;j<l;j++) x[j]=0;
	ntt(x,1);
	for(int j=0;j<l;j++) y[j]=x[j];
	//[0,b-x]
	for(int j=0;j<=b-i;j++) x[j]=inv[j];
	for(int j=b-i+1;j<l;j++) x[j]=0;
	ntt(x,1);
	for(int j=0;j<l;j++) y[j]=1ll*x[j]*y[j]%P;
	//[0,c-x]
	for(int j=0;j<=c-i;j++) x[j]=inv[j];
	for(int j=c-i+1;j<l;j++) x[j]=0;
	ntt(x,1);
	for(int j=0;j<l;j++) y[j]=1ll*x[j]*y[j]%P;
	//[0,d-x]
	for(int j=0;j<=d-i;j++) x[j]=inv[j];
	for(int j=d-i+1;j<l;j++) x[j]=0;
	ntt(x,1);
	for(int j=0;j<l;j++) y[j]=1ll*x[j]*y[j]%P;
	//re
	ntt(y,-1);
}

int main()
{
	scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
	int mn=min(min(a,b),min(c,d));
	
	C[0][0]=1;
	for(int i=1;i<=n;i++){
		C[i][0]=C[i][i]=1;
		for(int j=1;j<i;j++)
			C[i][j]=Plus(C[i-1][j-1],C[i-1][j]);
	}
	mul[0]=1;
	for(int i=1;i<=1000;i++) mul[i]=1ll*mul[i-1]*i%P; /**/
	inv[1000]=Pow_mod(mul[1000],P-2);
	for(int i=999;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%P; /**/
	
	for(int i=0;i*4<=n && i<=mn;i++){
		f[i]=1ll*C[n-3*i][i]*mul[n-4*i]%P;
		cal(i);
		f[i]=1ll*f[i]*y[n-4*i]%P;
	}

	int ans=0;
	for(int i=0;i*4<=n && i<=mn;i++){
		if(i&1) ans=Minus(ans,f[i]);
		else ans=Plus(ans,f[i]);
	}
	printf("%d\n",ans);
	
	return 0;
}

[loj#3106] [TJOI2019] 唱、跳、rap 和篮球

原文：https://www.cnblogs.com/lindalee/p/12488494.html