传送门

img

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

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

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

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

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

第一种方法：

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

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

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

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

答案方案数∑a′∈[0,A],b′∈[0,B],c′∈[0,C]Clefta′×Cleft−a′b′×Cleft−a′−b′c′\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′a',b',c'，时间复杂度O(n4)O(n^4)，过不去。

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

第二种方法：

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

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

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

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

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

这样答案就是∑tot1∈[0,left],a′∈[tot1−B,A],c′∈[tot2−D,C]Clefttot1×Ctot1a′×Ctot2c′\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][tot1-B,A]，因为ii的取值不能小于tot1−Btot1-B，否则喜欢跳的超过BB，不行。

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

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

答案就是∑tot1∈[0,left],tot2=left−tot1Clefttot1×((∑a′∈[tot1−B,A]Ctot1a′)×(∑c′∈[tot2−D,C]Ctot2c′))\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(1)算出，所以总时间复杂度O(n2)O(n^2)，可以ACAC。

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

#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);
}