P5339 [TJOI2019]唱、跳、rap和篮球

容易想到的是，枚举讨论蔡徐坤的组数，设至少有 $k$ 组讨论蔡徐坤的人方案数是 $f(k)$ ，容斥一下，答案就是 $\sum _{i=0}^{n/4} f(k) \times (-1)^k$ 。

现在的主要问题是求出 $f(k)$ ，将讨论蔡徐坤的四个人缩成一个组，所以这样的组数是 $k$ 组，剩下的人数 $left=n-k \times 4$ 。

于是问题转化为一个长度为 $n-k \times 4+k$ 的序列，往里面放 $k$ 个讨论蔡徐坤的组，剩下放入 $a'$ 个喜欢唱的， $(0\le a' \le a-k)$ ，放入 $b'$ 个喜欢跳的， $(0 \le b' \le b-k)$ ，……，满足 $a'+b'+c'+d'=n-k \times 4$ 。（即放满）

放入 $k$ 个讨论蔡徐坤的组，方案数是 $C_{left+k}^k$ 。

剩下如何处理唱跳rap篮球呢？

第一种方法：

放入 $a'$ 个喜欢唱的，方法数 $C_{left}^{a'}$ ，剩下 $left-a'$ 个空位。

放入 $b'$ 个喜欢跳的，方法数 $C_{left-a'}^{b'}$ ，剩下 $left-a'-b'$ 个空位。

放入 $c'$ 个喜欢rap的，方法数 $C_{left-a'-b'}^{c'}$ ，由于确定了 $a',b',c'$ ，剩下的 $d'$ 即确定，后面的 $d'$ 不用枚举。

令 $A=a-k,B=b-k,C=c-k,D=d-k$ 。

答案方案数 $\sum_{a' \in [0,A],b' \in [0,B] ,c' \in [0,C]} C_{left}^{a'} \times C_{left-a'}^{b'} \times C_{left-a'-b'}^{c'}$ 。

但是注意到我们要枚举 $a',b',c'$ ，时间复杂度 $O(n^4)$ ，过不去。

就算是前缀和优化 $C_{left-a'-b'}^{c'}$ ，时间复杂度 $O(n^3)$ ，还是gg。

第二种方法：

不妨把喜欢唱和喜欢跳的放在一起考虑。

先枚举他们加起来的总数 $tot1=a'+b'$ ，方案数 $C_{left}^{tot1}$ 。

再枚举 $a'$ ，方案数 $C_{tot1}^{a'}$ ，同理，确定了 $a'$ ，剩下的 $b'$ 就确定了，所以不用枚举。

剩下的喜欢rap的和喜欢篮球的，总数也确定为 $tot2=left-tot1$

枚举 $c'$ ，方案数 $C_{tot2}^{c'}$ 。

这样答案就是 $\sum_{tot1 \in [0,left] ,a' \in [tot1-B,A] , c' \in [tot2-D,C]} C_{left}^{tot1} \times C_{tot1}^{a'} \times C_{tot2}^{c'}$

为什么是 $[tot1-B,A]$ ，因为 $i$ 的取值不能小于 $tot1-B$ ，否则喜欢跳的超过 $B$ ，不行。

注意到这样我们还是要枚举三个变量 $tot1,a',c'$ ，时间复杂度 $O(n^4)$ ，gg。

不妨考虑固定住 $tot1$ ，只考虑后面一坨。

答案就是 $\sum_{tot1 \in [0,left],tot2=left-tot1}C_{left}^{tot1}\times((\sum_{a'\in [tot1-B,A]} C_{tot1}^{a'}) \times (\sum_{c' \in [tot2-D,C]} C_{tot2}^{c'}))$

后面两坨都可以通过前缀和 $O(1)$ 算出，所以总时间复杂度 $O(n^2)$ ，可以 $AC$ 。

总结，可以通过类似于折半搜索的方法减少时间复杂度。

#include <bits/stdc++.h>
#define MOD 998244353
#define MAXN 1005
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}
int n,a,b,c,d;
int C[MAXN][MAXN],sum[MAXN][MAXN];
inline void Init(){
	for (register int i=0;i<=n;++i){
		C[i][0]=sum[i][0]=1;
		for (register int j=1;j<=i;++j){
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
		}
		for (register int j=1;j<=n;++j){
			sum[i][j]=(sum[i][j-1]+C[i][j])%MOD;
		}
	}
}
inline long long QuerySum(int i,int l,int r){
	if (l>r) return 0;
	if (l<=0) return sum[i][r];
	return (sum[i][r]-sum[i][l-1]+MOD)%MOD;
}
int main(){
	n=read();
	a=min(n,read());b=min(n,read());c=min(n,read());d=min(n,read());//超过n和n取min，因为任何一种都不可能用超过n次
	Init();
	int ans=0;
	for (register int cxk=0;cxk<=n/4ll;++cxk){//cxk是讨论cxk的组数 
		int ret=0;
		int left=n-cxk*4;
		for (register int i=0;i<=left;++i){//从剩下的人里面选出i个人讨论唱跳，剩下讨论rap篮球
			int j=left-i;//讨论rap和篮球
			ret=(ret+(long long)C[left][i]*QuerySum(i,i-b,a)%MOD*QuerySum(j,j-d,c)%MOD)%MOD;
		}
		ret=((long long)ret*C[cxk+left][cxk])%MOD;
		if (cxk&1) ans=(ans-ret+MOD)%MOD;
		else ans=(ans+ret)%MOD;
		--a,--b,--c,--d;
		if (a<0||b<0||c<0||d<0) break;
	}
	printf("%d\n",ans);
}