bzoj 4710 [Jsoi2011]分特产

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，考虑如何求f，设f[i][j]表示前i种特产，一共j个人，不要求每人至少分一个的方案数，则f[0][j]=1，f[i][j]=f[i-1][j]*C(a[i]+j-1,j-1)，即不考虑第i种特产的方案数乘以将第i种特产任意分配的方案数

然后利用容斥原理得出每个人至少分得一个特产的方案数，设为g

$g[i]=f[i]-\sum_{j = 1}^{i – 1} C(i,j)*g[j]$

#include <cstdio>
using namespace std;
const int mod = 1000000007;
int C[2010][2010], n, m, a[2010], f[2010][2010], g[2010];
main() {
    scanf("%d%d", &n, &m);
    C[0][0] = C[1][0] = 1;
    for (int i = 1; i <= 2000; ++i, C[i][0] = 1)
        for (int j = 1; j <= i; ++j)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    for (int i = 1; i <= m; ++i)
        scanf("%d", &a[i]);
    f[1][0] = 1;
    for (int i = 1; i <= n; ++i, f[i][0] = 1)
        for (int j = 1; j <= m; ++j)
            f[i][j] = (1ll * f[i][j - 1] * C[a[j] + i - 1][i - 1]) % mod;
    for (int i = 1; i <= n; ++i) {
        g[i] = f[i][m];
        for (int j = 1; j < i; ++j)
            (g[i] += mod - 1ll * C[i][j] * g[j] % mod) %= mod;
    }
    printf("%d\n", g[n]);
}