【bzoj4710】[Jsoi2011]分特产 容斥原理+组合数学

题目描述

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

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

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

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

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

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

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

输入

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

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

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

输出

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

样例输入

5 4
1 3 3 5

样例输出

384835

---

题解

容斥原理+组合数学

由于“每个同学都必须至少分得一个特产”这个限制比较难处理，所以我们可以考虑容斥，用 没有限制-至少1个人没分到+至少2个人没分到-... 得到答案。

考虑如果i个人没分到该怎么处理：n个人选出i个不分，方案数为$C_n^i$；对于每种特产，分给$(n-i)$个同学，相当于把$n-i$个数分成$k$段，每段可以为空，方案数为$C_{n-i+k-1}^{k-1}$。

故最终答案为$\sum\limits_{i=0}^{n-1}(-1)^iC_n^i\sum\limits_{j=1}^mC_{n-i+a[j]-1}^{k-1}$。

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 2010

using namespace std;

typedef long long ll;

const ll mod = 1000000007;

ll c[N][N];

int w[N];

int main()

{

	int n , m , i , j;

	ll ans = 0 , tmp;

	for(i = 0 ; i <= 2000 ; i ++ )

	{

		c[i][0] = 1;

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

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

	}

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

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

	for(i = 0 ; i < n ; i ++ )

	{

		tmp = c[n][i];

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

			tmp = tmp * c[w[j] + n - i - 1][w[j]] % mod;

		if(i & 1) ans = (ans - tmp + mod) % mod;

		else ans = (ans + tmp) % mod;

	}

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

	return 0;

}