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=1,那这题就是一道简单的隔板法。可是 m > = 2 m >= 2 m>=2 咋办呢?先不管这个,我们先看看限制条件: n n n个人都有特产。
我们可以用总方案 - 有人没有特产的方案,有人没有特产,这个样子就是容斥了(类似于错排
于是我们不难列出一个式子:
a n s = <munderover> i = 0 n 1 </munderover> ( 1 ) i C n i f ( i ) ans = \sum\limits_{i=0}^{n-1} (-1)^iC_n^{i}f(i) ans=i=0n1(1)iCnif(i)
其中 f ( i ) f(i) f(i) 表示有 i i i 个人没有特产的方案数。
接下来我们只要求出 f ( i ) f(i) f(i),问题就解决了。
这时候我们发现每个特产对 f ( i ) f(i) f(i) 的贡献是独立的,因为可以有人没有特产(千万要区分每个人都有特产的情况),于是我们可以用乘法原理。
于是 f ( i ) = j = 1 m C a [ j ] + n i 1 <mtext>   </mtext> n i 1 f(i) = \prod\limits_{j=1}^{m}C_{a[j]+n-i-1}^{~n-i-1} f(i)=j=1mCa[j]+ni1 ni1
复杂度是 O ( n m ) O(nm) 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;
}