🔗 引用站外地址，请注意甄别
P10112 [GESP202312 八级] 奖品分配
洛谷

这道题目总的来说代码量不多，但是思维很麻烦。

题目说，所有的奖品加起来正好等于 $n$ 或等于 $n+1$。

那么，就可以进行分类讨论。

第一种情况：奖品数正好等于 $n$。

这种情况下就是说每个同学正好只拿一个奖品。

假设有 $10$ 名同学，奖品有 $3$ 种，每种奖品的个数分别为 $3,2,5$。

首先，我们要从 $10$ 个人中选择 $5$ 个人拿第三种奖品，那么组合情况数 $C_{10}^{5}$。

接下来，从剩下的 $5$ 个人中选择 $2$ 个人拿第二种奖品，那么组合情况数为 $C_{5}^{2}$。

那么最后只剩下 $3$ 个人，只能拿第一种奖品，即组合情况数位 $C_{3}^{3}$。

这样的选取方法结果就是 $C{10}^{5}\times C{5}^{2}\times C_{3}^{3}=2520$。

如果换一种顺序取选取奖品，假如说从前往后取，先取第一种奖品，再取第二种奖品，最后取第三种奖品，结果就是 $C{10}^{3}\times C{7}^{2}\times C_{5}^{5}=2520$。

两个式子的结果相等的，这就证明了这种计算方法的正确性。

这种情况下的公式为 $C{n}^{a_1}\times C{n-a1}^{a_2}\times C{n-a1-a_2}^{a_3}\times…\times C{n-a1-a_2-…-a{n-1}}^{a_n}$ 。

第二种情况：奖品数等于 $n+1$。

如果奖品数等于 $n+1$ 的话，最终就会多出来一个奖品。

仍然举一个例子：有 $10$ 名同学，$3$ 种奖品，每种奖品的数量分别是 $4,5,2$。

第一种思路：我们可以假设多出的奖品分别是第几种奖品。

假设多出的是第一种奖品，那就减掉好了，奖品数就变成了 $3,5,2$。

假设多出的是第二种奖品，奖品数就变成了 $4,4,2$。

假设多出的是第三种奖品，奖品数就变成了 $4,5,1$。

一共就得到了三种情况，分别按照第一种情况算即可。

分别相加，得到结果为 $C{10}^{3}\times C{7}^{5}\times C{2}^{2}+C{10}^{4}\times C{6}^{4}\times C{2}^{2}+C{10}^{4}\times C{6}^{5}\times C_{1}^{1}=6930$。

但是这样做的复杂度是多少呢？毫无疑问，是 $O(MT)$，很明显会超时。

第二种思路：不是去掉物品，而是多加一个人。因为多出的奖品即使不给人也要放在那里，因此可以假设多出来一个人，多出的一个奖品正好给多出的一个人。这样就转换成了第一种情况。

最终结果为 $C{11}^{4}\times C{7}^{5}\times C_{2}^{2}=6930$。

第一种思路的结果和第二种思路的结果正好相等，说明了第二种思路的正确性。

因为只是让同学数加一，所以复杂度和第一种情况相等，完全可以通过。

这种情况下的公式为 $C{n+1}^{a_1}\times C{(n+1)-a1}^{a_2}\times C{(n+1)-a1-a_2}^{a_3}\times…\times C{(n+1)-a1-a_2-…-a{n-1}}^{a_n}$ 。

题目中说，所有奖品的数量不是等于 $n$ 就是等于 $n+1$，简单整理以下，设 $sum$ 为所有奖品的总数量，最终的答案就是 $C{sum}^{a_1}\times C{sum-a1}^{a_2}\times C{sum-a1-a_2}^{a_3}\times…\times C{sum-a1-a_2-…-a{n-1}}^{a_n}$ 。

至于组合数可以使用杨辉三角预处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
const int mod = 1e9 + 7;

int a[N], C[N][N];

//利用杨辉三角预处理组合数
void init() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0 || j == i) C[i][j] = 1;
            //边加边取模
            else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
        }
    }
}
int main() {
    init();
    int T;
    scanf("%d", &T);
    while(T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        int sum = 0;
        for (int i = 1; i <= m; i++) {
            scanf("%d", &a[i]);
            sum += a[i];
        }
        long long ans = 1;//注意开long long
        for (int i = 1; i <= m; i++) {
            //这里的结果计算方法参考上面的讲解
            //直接用sum来计算答案省的考虑两种情况
            ans = (ans * C[sum][a[i]]) % mod;
            sum -= a[i];
        }
        printf("%lld\n", ans);
    }
    return 0;
}