【BZOJ4710】[Jsoi2011]分特产

Description

JYY 带队参加了若干场ACM/ICPC 比赛，带回了许多土特产，要分给实验室的同学们。

JYY 想知道，把这些特产分给N 个同学，一共有多少种不同的分法？当然，JYY 不希望任何一个同学因为没有拿到特产而感到失落，所以每个同学都必须至少分得一个特产。

例如，JYY 带来了2 袋麻花和1 袋包子，分给A 和B 两位同学，那么共有4 种不同的分配方法：

A：麻花，B：麻花、包子

A：麻花、麻花，B：包子

A：包子，B：麻花、麻花

A：麻花、包子，B：麻花

Input

输入数据第一行是同学的数量N 和特产的数量M。

第二行包含M 个整数，表示每一种特产的数量。

N, M 不超过1000，每一种特产的数量不超过1000

Output

输出一行，不同分配方案的总数。由于输出结果可能非常巨大，你只需要输出最终结果MOD 1,000,000,007 的数值就可以了。

Sample Input

5 4
1 3 3 5

Sample Output

384835

题解：组合数还是不够熟练啊~

显然要容斥，设f[i]表示将所有物品都只分给i个人（不一定全都分到）的方案数，那么分开考虑每个物品，如果物品j的数量为v，那么方案数等价于将v个物品分成i个子集的方案数，即f[i]*=C(v+i-1,i-1)。

求出了f数组，考虑容斥，ans=至少0人未分到-至少1人未分到+至少2人未分到...

于是枚举有k个人未分到，ans+=(-1)^k*C(n,k)*f[n-k]。

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

typedef long long ll;

const ll P=1000000007;

const int maxn=1000010;

int n,m,tot;

ll ans;

ll jc[maxn],jcc[maxn],ine[maxn],f[maxn];

int v[maxn];

ll c(int a,int b)

{

	return jc[a]*jcc[b]%P*jcc[a-b]%P;

}

ll pm(ll x,ll y)

{

	ll z=1;

	while(y)

	{

		if(y&1)	z=z*x%P;

		x=x*x%P,y>>=1;

	}

	return z;

}

int main()

{

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

	int i,j;

	for(i=1;i<=m;i++)	scanf("%d",&v[i]),tot+=v[i];

	if(n>tot)

	{

		printf("0");

		return 0;

	}

	ine[1]=ine[0]=jc[1]=jc[0]=jcc[1]=jcc[0]=1;

	for(i=2;i<=tot;i++)	ine[i]=(P-(P/i)*ine[P%i])%P,jc[i]=jc[i-1]*i%P,jcc[i]=jcc[i-1]*ine[i]%P;

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

	for(i=1;i<=m;i++)	for(j=1;j<=n;j++)	f[j]=f[j]*c(v[i]+j-1,j-1)%P;

	for(i=0;i<n;i++)	ans=(ans+((i&1)?-1:1)*c(n,i)%P*f[n-i]%P+P)%P;

	printf("%lld\n",ans%P);

	return 0;

}//2 2 1 2

巴特西

【BZOJ4710】[Jsoi2011]分特产组合数+容斥

【BZOJ4710】[Jsoi2011]分特产

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

巴特西

【BZOJ4710】[Jsoi2011]分特产 组合数+容斥

【BZOJ4710】[Jsoi2011]分特产

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

【BZOJ4710】[Jsoi2011]分特产组合数+容斥