bzoj 4710/ jsoi 2011 分特产（容斥原理

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

分析

如果 $m=1$m=1，那这题就是一道简单的隔板法。可是 $m>=2$m>=2 咋办呢？先不管这个，我们先看看限制条件： $n$n个人都有特产。
我们可以用总方案 - 有人没有特产的方案，有人没有特产，这个样子就是容斥了（类似于错排
于是我们不难列出一个式子：
$ans=\sum _{i=0}^{n-1}(-1{)}^i{C}_n^{i}f(i)$ans=i=0∑n−1​(−1)iCni​f(i)
其中 $f\left(i\right)$f(i) 表示有 $i$i 个人没有特产的方案数。
接下来我们只要求出 $f\left(i\right)$f(i)，问题就解决了。
这时候我们发现每个特产对 $f\left(i\right)$f(i) 的贡献是独立的，因为可以有人没有特产（千万要区分每个人都有特产的情况），于是我们可以用乘法原理。
于是 $f\left(i\right)={\prod }_{j=1}^m{C}_{a\left[j\right]+n-i-1}^{n-i-1}$f(i)=j=1∏m​Ca[j]+n−i−1 n−i−1​
复杂度是 $O\left(nm\right)$O(nm) 的。

代码如下

#include <bits/stdc++.h>
#define N 2005
#define mod 1000000007
#define LL long long
using namespace std;
int f[N], a[N], c[N][N];
LL z = 1, ans;
int main(){
	int i, j, k, n, m;
	scanf("%d%d", &n, &m);
	for(i = 0; i <= 2000; i++){
		c[i][0] = 1;
		for(j = 1; j <= i; j++) c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
	}
	for(i = 1; i <= m; i++) scanf("%d", &a[i]);
	for(k = 0; k <= n - 1; k++){
		f[k] = 1;
		for(i = 1; i <= m; i++) f[k] = z * f[k] * c[a[i] + n - k - 1][n - k - 1] % mod;
		if(k % 2) ans = (z * ans - z * c[n][k] * f[k] % mod) % mod;
		else ans = (z * ans + z * c[n][k] * f[k] % mod) % mod;
	}
	ans = (ans % mod + mod) % mod;
	printf("%lld", ans);
	return 0;
}