题解：P10112 [GESP202312 八级] 奖品分配

题目

班上有 名同学，学号从 到 。有 种奖品要分给这些同学，其中，第 种奖品总共有 个 （）。

巧合的是，奖品的数量不多不少，每位同学都可以恰好分到一个奖品，且最后剩余的奖品不超过 个（即：）。

现在，请你求出每个班级礼物分配的方案数，所谓方案，指的是为每位同学都分配一个种类的奖品。

只要有一位同学获得了不同种类的奖品，即视为不同的方案。方便起见，你只需要输出方案数对 取模后的结果即可。

共有 个班级都面临着奖品分配的问题，你需要依次为他们解答。

数据范围

。

题解

考虑分配的过程其实就是选取一部分人去拿某种奖品，这个角度看，答案就比较明显：

• 总过程可分为对每中奖品的“分配操作”；
• 操作 的方案数等效于从 中抽出 个人的方案数；
• 每一步之间的关系是遵循乘法原则；
• 组合的意义上，奖品顺序是不重要的，因为分配操作是一致的，这个需要理解一下；

问题在于奖品个数 怎么办？

剩下一个可以理解为分配给了空气人，因为它就是一种确定的分配方案。

代码如下：

#include<bits/stdc++.h>
#define LL long long

using namespace std;

const int MAXN = 1005;
const LL mod = 1e9 + 7;

int T;

int n, m;
int a[MAXN], sum;
LL C[MAXN][MAXN];

inline void C_init() {
    for (int i = 0; i < MAXN; ++i)
        for (int j = 0; j <= i; ++j) {
            if (j == 0)
                C[i][j] = 1;
            else
                C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
        }
    return;
}

inline void solve(int manCnt) {
    LL res = 1;
    for (int i = 1; i <= m; ++i) {
        res = (res * C[manCnt][a[i]]) % mod;
        manCnt -= a[i];
    }
    cout << res << '\n';
    return;
}

int main() {
    C_init();
    scanf("%d", &T);
    while (T--) {
        sum = 0;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; ++i) {
            scanf("%d", &a[i]);
            sum += a[i];
        }
        solve(sum);
    }
    return 0;
}