【GESP八级真题解析】奖品分配问题：组合数学与预处理优...

15303105423

一、题目解读

2023年GESP八级题“奖品分配”（洛谷P10112）要求计算将N个奖品分配给M个人的方案总数，需满足每人至少获得1个奖品。题目核心在于组合数学的应用，需考虑不同分配情况下的组合数计算，同时涉及大数模运算（MOD=1e9+7）的优化。

二、解题思路

1. 组合数学核心：分配方案数可转化为组合数计算，即从N个奖品中选择M个位置放置分隔符（隔板法），但需排除每人未分到奖品的情况。

2. 预处理优化：为避免重复计算阶乘与逆阶乘，预先构建阶乘表fact和逆阶乘表inv_fact，利用快速幂算法加速模幂运算，降低时间复杂度。

3. 边界处理：分为两种分配情况：

    若奖品总数sum恰好等于N，则直接计算所有可能的排列组合；

    若sum < N（剩余1个奖品），需枚举剩余奖品分配给哪个人，并递归计算剩余情况。

三、解题步骤

1. 预处理阶乘与逆阶乘表：

    利用循环计算fact[0..max_n]（阶乘），再通过逆元公式推导inv_fact（逆阶乘），确保MOD下的正确性。

    快速幂算法pow_mod(x,n)实现O(log n)的模幂运算，避免超时。

2. 主循环处理输入：

    读入测试次数T，循环处理每组数据（N,M及奖品数组a）。

    计算奖品总和sum，判断分配是否可行。

3. 计算答案：

    若sum == N，直接计算C(N,M)并除以各a的阶乘逆元。

    若sum < N，枚举剩余奖品的位置，递归计算剩余情况的组合数。

四、代码与注释

1. #include <iostream>
   
2. #include <vector>
   
3. using namespace std;
   
4. 
   
5. const int MOD = 1e9 + 7;
   
6. 
   
7. // 预计算阶乘和逆阶乘数组
   
8. vector<long long> fact, inv_fact;
   
9. 
   
10. // 快速幂计算
    
11. long long pow_mod(long long x, long long n) {
    
12.     long long res = 1;
    
13.     while (n > 0) {
    
14.         if (n % 2 == 1) res = (res * x) % MOD;
    
15.         x = (x * x) % MOD;
    
16.         n /= 2;
    
17.     }
    
18.     return res;
    
19. }
    
20. 
    
21. // 初始化阶乘表
    
22. void init_fact(int max_n) {
    
23.     fact.resize(max_n + 1);
    
24.     inv_fact.resize(max_n + 1);
    
25.     fact[0] = 1;
    
26.     for (int i = 1; i <= max_n; ++i) {
    
27.         fact[i] = (fact[i-1] * i) % MOD;  // 计算阶乘
    
28.     }
    
29.     inv_fact[max_n] = pow_mod(fact[max_n], MOD-2);  // 计算逆阶乘（利用费马小定理）
    
30.     for (int i = max_n-1; i >= 0; --i) {
    
31.         inv_fact[i] = (inv_fact[i+1] * (i+1)) % MOD;  // 逆阶乘递推公式
    
32.     }
    
33. }
    
34. 
    
35. // 计算组合数C(n,k)
    
36. long long comb(int n, int k) {
    
37.     if (k < 0 || k > n) return 0;  // 边界检查
    
38.     return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD;  // 组合数公式
    
39. }
    
40. 
    
41. int main() {
    
42.     ios::sync_with_stdio(false);
    
43.     cin.tie(nullptr);
    
44.    
    
45.     int T;
    
46.     cin >> T;
    
47.    
    
48.     // 预处理阶乘表，最大可能N是1e5
    
49.     init_fact(1e5 + 5);
    
50.    
    
51.     while (T--) {
    
52.         int N, M;
    
53.         cin >> N >> M;
    
54.         vector<int> a(M);
    
55.         int sum = 0;
    
56.         for (int i = 0; i < M; ++i) {
    
57.             cin >> a[i];
    
58.             sum += a[i];
    
59.         }
    
60.         
    
61.         long long ans = 1;
    
62.         if (sum == N) {
    
63.             // 刚好分配完的情况
    
64.             ans = fact[N];
    
65.             for (int i = 0; i < M; ++i) {
    
66.                 ans = ans * inv_fact[a[i]] % MOD;  // 除以各人数的阶乘逆元
    
67.             }
    
68.         } else {
    
69.             // 剩余1个奖品的情况
    
70.             ans = 0;
    
71.             for (int i = 0; i < M; ++i) {
    
72.                 if (a[i] > 0) {
    
73.                     // 计算剩余奖品是第i种的情况
    
74.                     long long temp = fact[N];
    
75.                     for (int j = 0; j < M; ++j) {
    
76.                         int cnt = (j == i)? (a[j] - 1) : a[j];
    
77.                         temp = temp * inv_fact[cnt] % MOD;
    
78.                     }
    
79.                     ans = (ans + temp) % MOD;  // 累加所有可能情况
    
80.                 }
    
81.             }
    
82.         }
    
83.         cout << ans << endl;
    
84.     }
    
85.     return 0;
    
86. }

复制代码

五、总结

1. 关键技巧：组合数学问题的预处理优化（阶乘表+快速幂）是解决大数模运算的核心，需熟练掌握。

2. 边界分析：区分“刚好分配完”与“剩余1个奖品”的情况，避免漏解或重复计算。

3. 算法复杂度：预处理O(N)，单次查询O(M)，总时间复杂度O(N+T×M)，满足题目要求。

4. 实战价值：该解法适用于竞赛中常见的组合计数问题，可扩展至更复杂的分配场景。

来源：【GESP八级真题解析】奖品分配问题：组合数学与预处理优化（洛谷P10112）