奖品分配 题解

题目分析

班上有 $N$ 名同学（学号 $0 \sim N-1$），有 $M$ 种奖品。第 $i$ 种奖品共有 $a_i$ 个。保证奖品总数 $\text{sum} = \sum_{i=0}^{M-1} a_i$ 满足 $N \le \text{sum} \le N+1$，即恰好够每人分一个，或只多出一个。每位同学获得一个奖品，同种奖品之间不可区分，同学之间可区分（学号不同）。只要有一位同学获得的奖品种类不同，就算不同的方案。求方案数模 $10^9+7$。

共有 $T$ 个班级需要处理。

关键点：

• 奖品有数量限制，最后会剩余 $0$ 个或 $1$ 个奖品。
• 同学是有序的，所以这是一个带限制的多重集排列问题。

解题思路

设 $c_i$ 为第 $i$ 种奖品实际分给同学的数量。则需满足：

给定 $\text{sum} = \sum a_i$ 在 $N$ 和 $N+1$ 之间，因此可能的 $c_i$ 取值非常有限：

• 若 $\text{sum} = N$：只有唯一一种取值 $c_i = a_i$（所有奖品全部分配）。
• 若 $\text{sum} = N+1$：恰好有一种奖品会剩下 $1$ 个，其余全部分配。即存在某个 $j$ 使得 $c_j = a_j - 1$（前提 $a_j>0$），其余 $c_i = a_i$。

情况一：$\text{sum} = N$

此时方案数等于将 $N$ 个不同位置（同学）分配给 $M$ 种物品，第 $i$ 种恰好有 $a_i$ 个的多重排列数：

情况二：$\text{sum} = N+1$

此时会选择一种奖品 $j$ 少拿一个。对每一种符合条件的 $j$，方案数为：

因为 $N = \text{sum} - 1$，上式可写成：

对所有 $a_j>0$ 的 $j$ 求和，总方案数为：

令人惊喜的是，两种情况下的公式统一为：

其中 $\text{sum} = \sum a_i$（等于 $N$ 或 $N+1$）。所以无论剩余 $0$ 个还是 $1$ 个奖品，答案都是 $\text{sum}$ 个物品的全排列数除以各物品内部排列数的商。

组合意义解释

该公式有一个更直接的组合解释：我们暂时假设真的有 $\text{sum}$ 个“位置”（同学），把 $\text{sum}$ 个奖品全部分配给这 $\text{sum}$ 个位置。方案数为 $\text{sum}! / \prod a_i!$。如果实际只有 $N$ 个同学，且 $\text{sum}=N+1$，那么多出的那个奖品相当于“空气同学”，去掉它并不影响分配方案间的区别，因为每种剩余哪个奖品的情况在公式中已经按比例体现。因此公式统一成立。

算法说明

模数 $10^9+7$ 是质数，数据范围 $N \le 1000$，$\text{sum} \le N+1 \le 1001$。我们可以直接计算上述公式：

• 预计算阶乘 $\text{fact}[i]$ 和阶乘的逆元 $\text{invfact}[i]$，然后答案为 $\text{fact}[\text{sum}] \times \prod \text{invfact}[a_i] \bmod \text{MOD}$。
• 也可以使用组合数连乘的方法：想象从 $\text{sum}$ 个位置中先选 $a_0$ 个放第 $0$ 种奖品，有 $C_{\text{sum}}^{a_0}$ 种方式；再从剩余 $\text{sum}-a_0$ 个位置中选 $a_1$ 个放第 $1$ 种奖品…… 依次相乘的结果正是 $\frac{\text{sum}!}{\prod a_i!}$。这种方法避免直接求逆元，对于小范围非常方便。

参考代码采用组合数递推的方式，预处理出 $C[n][k]$ 表（模 $10^9+7$），最大 $n \le 1005$，空间和时间都可以接受。

组合数预处理

cpp
复制
1C[0][0] = 1;
2for (int i = 1; i <= N; i++) {
3    C[i][0] = C[i][i] = 1;
4    for (int j = 1; j < i; j++) {
5        C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod;
6    }
7}

对于每个班级

读入 $N, M$ 和 $a_i$，累加得到总数 $\text{sum}$。初始化答案 $\text{ans}=1$，然后遍历每种奖品：

最后输出 $\text{ans}$。

时间复杂度分析

• 预处理组合数：$O(\text{MAX}^2)$，$\text{MAX}=1005$，计算量约 $5\times 10^5$，瞬间完成。
• 每个班级处理：需要累加 $M$ 个 $a_i$ 并循环 $M$ 次做乘法与组合数查表，$O(M)$。
• 总时间复杂度：$O(\text{MAX}^2 + T \cdot M)$。本题 $T \le 1000$，$\sum M$ 没有特别说明，但每个 $M \le 1001$，总运算量在最坏情况下约 $10^6$ 级别，完全可以在 1 秒内运行通过。

参考代码

cpp
复制
1#include <cstdio>
2#include <cstring>
3#include <algorithm>
4#include <iostream>
5using namespace std;
6
7const int N = 1005;
8const int mod = 1e9 + 7;
9
10int C[N + 5][N + 5], a[N + 5];
11
12// 组合数预处理
13void init() {
14    C[0][0] = 1;
15    for (int i = 1; i <= N; i++) {
16        C[i][0] = C[i][i] = 1;
17        for (int j = 1; j < i; j++) {
18            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod;
19        }
20    }
21}
22
23int main() {
24    init();
25    
26    int T;
27    scanf("%d", &T);
28    
29    while (T--) {
30        int n, m, sum = 0;
31        scanf("%d%d", &n, &m);
32        
33        for (int i = 1; i <= m; i++) {
34            scanf("%d", &a[i]);
35            sum += a[i];
36        }
37        
38        int ans = 1;
39        for (int i = 1; i <= m; i++) {
40            ans = 1LL * ans * C[sum][a[i]] % mod;
41            sum -= a[i];
42        }
43        
44        printf("%d\n", ans);
45    }
46    
47    return 0;
48}

代码解释

• init()：利用杨辉三角递推公式 $C_n^k = C_{n-1}^{k-1} + C_{n-1}^k$ 预计算所有组合数，并对 $10^9+7$ 取模。
• 主循环：sum 为当前班级奖品的总数。每次从未分配的位置数 sum 中选出 a[i] 个位置分配给第 $i$ 种奖品，方案数乘上 $C[\text{sum}][a_i]$，然后将 sum 减去已分配的数量。由于组合数的乘积恰等于 $\frac{\text{sum}!}{\prod a_i!}$，既直观又易于实现。
• 注意用 1LL * 避免乘法溢出，以及及时的取模操作。

总结

本题的关键在于发现两种剩余情况拥有统一的数学表达式 $\frac{\text{sum}!}{\prod a_i!}$。这个结论可以大大简化代码，甚至可以直接用阶乘与逆元求解。参考代码采用组合数累乘的方法，同样简洁且易于理解，适合在竞赛中使用。