Steven_MengのBlog

传送门

img

容易想到的是,枚举讨论蔡徐坤的组数,设至少有$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$。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#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);
}

 评论