题目地址：洛谷：暂无、BZOJ：Problem 4710. — [Jsoi2011]分特产

题目描述

JYY 带队参加了若干场ACM/ICPC 比赛，带回了许多土特产，要分给实验室的同学们。JYY 想知道，把这些特产分给N 个同学，一共有多少种不同的分法？当然，JYY 不希望任何一个同学因为没有拿到特产而感到失落，所以每个同学都必须至少分得一个特产。
例如，JYY 带来了2 袋麻花和1 袋包子，分给A 和B 两位同学，那么共有4 种不同的分配方法：
A：麻花，B：麻花、包子
A：麻花、麻花，B：包子
A：包子，B：麻花、麻花
A：麻花、包子，B：麻花

题意简述

有N个同学M种物品，每个物品有有限个，求每个同学都分到至少一个物品的方案数。

输入输出格式

输入格式：
输入数据第一行是同学的数量N 和特产的数量M。
第二行包含M 个整数，表示每一种特产的数量。
N, M 不超过1000，每一种特产的数量不超过1000

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

输入输出样例

输入样例#1：

5 4
1 3 3 5

输出样例#1：

384835

题解

首先我们会发现对于每个特产分开插板处理即可。插板解决一个可空分配方案数的答案是\mathrm{C}_{n+m-1}^{m-1}。
考虑一个常规的容斥思路，即：
答案=至少0人没分到特产的方案数-至少1人没分到特产的方案数+至少2人没分到特产的方案数-……
为了保证“至少”，我们要钦定一些人不被分到，然后按照上面类似的插板思路分配剩下的人。因此最后的答案是
\sum_{i=0}^n \left[ (-1)^i \mathrm{C}_n^i \prod_{j=1}^m \mathrm{C}_{n+a_j-i-1}^{n-i-1} \right]

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 2005, MO = 1e9 + 7;

int n, m;
LL num[MAXN];

LL C[MAXN][MAXN];

inline void calc() {
    C[0][0] = 1;
    for(int i = 1; i < MAXN; i++) {
        C[i][0] = 1;
        for(int j = 1; j <= i; j++) {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MO;
        }
    }
}

int main() {
    calc();
    n = readint(); m = readint();
    for(int i = 1; i <= m; i++) {
        num[i] = readint();
    }
    LL ans = 0, t = -1;
    for(int i = 0; i <= n; i++) {
        t *= -1;
        LL res = 1;
        for(int j = 1; j <= m; j++) {
            res = res * C[n + num[j] - i - 1][n - i - 1] % MO;
        }
        ans = (ans + t * C[n][i] * res % MO) % MO;
    }
    printf("%lld", (ans + MO) % MO);
    return 0;
}