bzoj 4710: [Jsoi2011]分特产

Description

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

JYY 想知道，把这些特产分给N 个同学，一共有多少种不同的分法？当然，JYY 不希望任

何一个同学因为没有拿到特产而感到失落，所以每个同学都必须至少分得一个特产。

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

分配方法：

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

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

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

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

解题报告：

用时：2h，1WA

首先要想到容斥，那么总方案是什么？对于每一种物品分给N个同学，那么就是可重组合\(C(n+a[i]-1,a[i])\)，然后再将每一个物品分给同学的方案相乘，但是可重组合公式中的方案并不保证每一个位置都有至少一个，所以我们要减去不合法方案，也就是存在有空位的方案，根据容斥原理：减去一个空位的，再加上两个空位的，再减去三个空位的，加上四个空位的.....，注意有\(i\)个空位的方案还需要乘上\(C(n,i)\)，因为空位可以是任意位置

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#define RG register

#define il inline

#define iter iterator

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

using namespace std;

typedef long long ll;

const int N=1005,mod=1000000007;

int a[N],n,m;ll c[N<<1][N<<1];

void work()

{

	int mx=0;

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

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

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

		mx=Max(a[i],mx);

	}

	mx+=n;

	for(int i=0;i<=mx;i++){

		c[i][0]=1;

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

			c[i][j]=c[i-1][j-1]+c[i-1][j];

			if(c[i][j]>=mod)c[i][j]-=mod;

		}

	}

	ll ans=1,tmp;

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

		ans*=c[a[i]+n-1][a[i]];

		ans%=mod;

	}

	int t=-1;

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

		tmp=1;

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

			tmp*=c[a[j]+n-i-1][a[j]];

			tmp%=mod;

		}

		tmp=tmp*c[n][i]%mod;

		ans+=tmp*t;ans=((ans%mod)+mod)%mod;

		t*=-1;

	}

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

}

int main()

{

	work();

	return 0;

}