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个人分包裹并且每个人都拿到的方案数
然后简单容斥就可以了
#include<bits/stdc++.h>
using namespace std;
const int N = 2010;
const int Mod = 1e9 + 7;
int n, m, a[N], f[N];
int fac[N], inv[N];
int add(int a, int b) {
return (a += b) >= Mod ? a - Mod : a;
}
int sub(int a, int b) {
return (a -= b) < 0 ? a + Mod : a;
}
int mul(int a, int b) {
return 1ll * a * b % Mod;
}
int fast_pow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = mul(res, a);
b >>= 1;
a = mul(a, a);
}
return res;
}
int C(int a, int b) {
return mul(fac[a], mul(inv[a - b], inv[b]));
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) scanf("%d", &a[i]);
fac[0] = inv[0] = 1;
for (int i = 1; i < N; i++) fac[i] = mul(fac[i - 1], i);
inv[N - 1] = fast_pow(fac[N - 1], Mod - 2);
for (int i = N - 2; i >= 1; i--) inv[i] = mul(inv[i + 1], i + 1);
f[1] = 1;
for (int i = 2; i <= n; i++) {
int cur = 1;
for (int j = 1; j <= m; j++) {
cur = mul(cur, C(i + a[j] - 1, i - 1));
}
for (int j = 1; j < i; j++) {
cur = sub(cur, mul(C(i, j), f[j]));
}
f[i] = cur;
}
printf("%d", f[n]);
return 0;
}