BZOJ 4710 分特产

发表于 | 更新于

Link

容斥唉。。

Solution

加限制的记数就应该考虑一下容斥？ f[i][j]f[i][j]表示前ii中特产随便分给jj个人的方案数目，然后每个特产用插板法计算分法。。 然后枚举得不到特产的人数容斥。。

Tips

万用的插板法。。

Code

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
#include "lucida"
const int P=1000000007,MAXN=1000+11;
int64 C[MAXN<<1][MAXN<<1];
struct _{_(){
	C[0][0]=1;
	for(int i=1;i<=2000;++i) {//2000上界...
		C[i][0]=1;
		for(int j=1;j<=i;++j)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
	}
}}Auto;
int main() {
	freopen("input","r",stdin);
	static int f[MAXN][MAXN],c[MAXN];
	int n,co;
	is>>n>>co;
	//f[i][j] 表示把前i个物品随便分给j个人的方案数
	for(int i=1;i<=co;++i)
		is>>c[i];
	for(int i=1;i<=n;++i)
		f[0][i]=1;
	for(int i=1;i<=co;++i)
		for(int j=1;j<=n;++j)
			f[i][j]=f[i-1][j]*C[c[i]+j-1][j-1]%P;//[][j]..
	//f[n][i] 分给i个人的方案数目
	int64 Ans=0;
	for(int i=0;i<=n;++i)//i个人分不到的方案数目
		(Ans+=f[co][n-i]*C[n][i]*(i&1?-1:1))%=P;//没%
	(Ans+=P)%=P;
	os<<Ans<<'\n';
	return 0;
}