「TJOI2019」唱、跳、rap和篮球

发表于 | 分类于 | | 浏览量： 次

鲲鲲来啦！

传送门

洛谷P5339

BZOJ5510

题解

比较好玩的一个数数题。

考虑如何计算有连续4个位置的同学依次喜欢唱、跳、rap、篮球的情况的数量。

首先可以枚举这种四元组的数量，设有$i$个四元组。

那么这些四元组的出现位置的方案数就为$\tbinom{n-3i}{i}$。

证明：

首先这些四元组显然是两两不交的。

考虑一排点，共有有$n-3i$个，选择$i$个点将它们展开成一个四元组，那么展开之后一共有$n$个点，刚好对应一种出现位置的方案，一共有$\binom{n-3i}{i}$种选择方法。

证毕。

除了四元组之外，考虑其他位置上的同学怎么安排。

如果随便排的话，可能会再次产生四元组，考虑通过容斥把多算的减掉。

所以含有四元组的方案数为：

考虑剩下位置的方案数怎么算，设喜欢唱、跳、rap、篮球的人分别取了$e,f,g,h$个$(e\leq a-i,f\leq b-i,g\leq c-i,h\leq d-i)$，那么方案数就是：

所以就可以构四个多项式，其中第一个为：

剩下三个多项式同理。然后把四个多项式用NTT卷乘起来，$x^{n-4i}$项的系数就是我们所要求的剩下位置的方案数。

由于要求的是不包含任意一个四元组的方案数，所以最后的答案为：

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

代码

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1005,maxl=2050,TT=998244353;
int n,a,b,c,d,fac[maxn],inv[maxn],r[maxl],ans,A[maxl],B[maxl],C[maxl],D[maxl],E[maxl];
inline int QP(int a,int b)
{
	int ret=1,w=a;
	while(b)
	{
		if(b&1) ret=(LL)ret*w%TT;
		w=(LL)w*w%TT;b>>=1;
	}
	return ret;
}
inline void NTT(int* A,int limit,int typ)
{
	for(int i=0;i<limit;i++)
		if(i<r[i])
			swap(A[i],A[r[i]]);
	for(int mid=1;mid<limit;mid<<=1)
	{
		int gn=QP(3,(TT-1)/(mid<<1));
		if(typ<0) gn=QP(gn,TT-2);
		for(int j=0;j<limit;j+=mid<<1)
		{
			int g=1;
			for(int k=0;k<mid;k++,g=(LL)g*gn%TT)
			{
				int x=A[j+k],y=(LL)g*A[j+k+mid]%TT;
				A[j+k]=(x+y)%TT;
				A[j+k+mid]=(x-y+TT)%TT;
			}
		}
	}
	if(typ<0)
	{
		int inv=QP(limit,TT-2);
		for(int i=0;i<limit;i++) A[i]=(LL)A[i]*inv%TT;
	}
}
inline int Com(int n,int m){return (LL)fac[n]*inv[m]%TT*inv[n-m]%TT;}
inline void Solve()
{
	fac[0]=inv[0]=1;
	for(int i=1;i<=1000;i++)
	{
		fac[i]=(LL)fac[i-1]*i%TT;
		inv[i]=QP(fac[i],TT-2);
	}
	int mg=min(min(min(a,b),min(c,d)),n/4);
	for(int i=0;i<=mg;i++)
	{
		memset(A,0,sizeof(A));memset(B,0,sizeof(B));memset(C,0,sizeof(C));memset(D,0,sizeof(D));
		for(int j=0;j<=a-i;j++) A[j]=inv[j];
		for(int j=0;j<=b-i;j++) B[j]=inv[j];
		for(int j=0;j<=c-i;j++) C[j]=inv[j];
		for(int j=0;j<=d-i;j++) D[j]=inv[j];
		int limit=1,l=0;
		while(limit<=a+b+c+d-4*i){limit<<=1;l++;}
		for(int j=0;j<limit;j++)
			r[j]=(r[j>>1]>>1)|((j&1)<<(l-1));
		NTT(A,limit,1);NTT(B,limit,1);NTT(C,limit,1);NTT(D,limit,1);
		for(int j=0;j<limit;j++) E[j]=(LL)A[j]*B[j]%TT*C[j]%TT*D[j]%TT;
		NTT(E,limit,-1);
		ans=(ans+(LL)QP(-1,i)*Com(n-3*i,i)*fac[n-4*i]%TT*E[n-4*i]%TT+TT)%TT;
	}
}
int main()
{
	scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
	Solve();
	printf("%d\n",ans);
	return 0;
}