BZOJ4710 分特产

题目链接：戳我

容斥题。

设\(f[i]\)表示至多有i个人能够分到（也就是至少n-i个人分不到）的方案数

\(f[i]=\prod_{j=1}^mC_{a[j]+i-1}^i-1\)

a[j]表示的是该特产的数量。

为什么组合数是那样子写的呢？大家考虑一下，a[j]个球，分成i份，每份可以为空是不是就是这样子写的呢？（当然大家也可以考虑一下如果不为空怎么写呢。。不会的话可以去看看数学选修2-3，不过当然，这个不在本题的讨论范围内啦）

然后根据容斥原理，我们知道每个人都至少有一个特产的方案数=至少有0个人没有-至少1个人没有+至少2个人没有。。。。。（等效于上面的至多嘛）

然后答案就是\(\sum_{i=1}^n(-1)^{n-i}C_n^if[i]\)啦

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 100010

#define mod 1000000007

using namespace std;

int n,m;

int a[MAXN];

long long ans=0;

long long dp[MAXN],f[MAXN],C[2010][2010];

inline void init()

{

	for(int i=0;i<=2000;i++) C[i][0]=1,C[i][i]=1;

	for(int i=2;i<=2000;i++)

		for(int j=1;j<i;j++)

			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;

}

int main()

{

	#ifndef ONLINE_JUDGE

	freopen("ce.in","r",stdin);

	#endif

	scanf("%d%d",&n,&m);

	for(int i=1;i<=m;i++)

		scanf("%d",&a[i]);

	init();

	for(int i=1;i<=n;i++) f[i]=1;

	for(int i=1;i<=n;i++)

	{

		for(int j=1;j<=m;j++)

			f[i]=1ll*f[i]*C[i+a[j]-1][i-1]%mod;

	}

	for(int i=1;i<=n;i++)

	{

		int op;

		if((n-i)&1) op=-1;

		else op=1;

		ans=(ans+1ll*op*C[n][i]*f[i]+mod)%mod;

	}

	printf("%I64d\n",ans);

	return 0;

}

巴特西

BZOJ4710 分特产

题目链接：戳我

最新文章

热门文章