2023年GESP八级考题解析：奖品分配的组合数学解法

rhsgfswg

一、问题背景

题目要求将N个奖品分配给M个团队，每个团队有特定的奖品需求a。需要计算两种情况的分配方案数：

• 刚好分配完所有奖品
• 恰好剩余1个奖品未分配
  
  

二、算法核心思想

• 阶乘预处理：预先计算阶乘和逆阶乘数组
• 快速幂优化：使用快速幂计算模逆元
• 多项式系数：利用组合数公式计算分配方案
• 模运算处理：确保大数运算在模数范围内
  
  

三、完整代码解析（带详细注释）

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. // 初始化阶乘表（O(n)预处理）
    
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;  // 计算i! mod MOD
    
28.     }
    
29.     // 费马小定理求逆元
    
30.     inv_fact[max_n] = pow_mod(fact[max_n], MOD-2);
    
31.     // 递推计算逆阶乘
    
32.     for (int i = max_n-1; i >= 0; --i) {
    
33.         inv_fact[i] = (inv_fact[i+1] * (i+1)) % MOD;
    
34.     }
    
35. }
    
36. 
    
37. // 计算组合数C(n,k) mod MOD
    
38. long long comb(int n, int k) {
    
39.     if (k < 0 || k > n) return 0;
    
40.     return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD;
    
41. }
    
42. 
    
43. int main() {
    
44.     ios::sync_with_stdio(false);  // 加速IO
    
45.     cin.tie(nullptr);
    
46.    
    
47.     int T;  // 测试用例数
    
48.     cin >> T;
    
49.    
    
50.     // 预处理阶乘表（**支持1e5+5）
    
51.     init_fact(1e5 + 5);
    
52.    
    
53.     while (T--) {
    
54.         int N, M;  // 奖品总数和团队数
    
55.         cin >> N >> M;
    
56.         vector<int> a(M);  // 各团队需求
    
57.         int sum = 0;
    
58.         for (int i = 0; i < M; ++i) {
    
59.             cin >> a[i];
    
60.             sum += a[i];
    
61.         }
    
62.         
    
63.         long long ans = 1;
    
64.         if (sum == N) {
    
65.             // 情况1：刚好分配完
    
66.             ans = fact[N];  // N! / (a1!a2!...am!)
    
67.             for (int i = 0; i < M; ++i) {
    
68.                 ans = ans * inv_fact[a[i]] % MOD;
    
69.             }
    
70.         } else {
    
71.             // 情况2：剩余1个奖品
    
72.             ans = 0;
    
73.             for (int i = 0; i < M; ++i) {
    
74.                 if (a[i] > 0) {
    
75.                     // 假设剩余的是第i种奖品
    
76.                     long long temp = fact[N];
    
77.                     for (int j = 0; j < M; ++j) {
    
78.                         int cnt = (j == i) ? (a[j] - 1) : a[j];
    
79.                         temp = temp * inv_fact[cnt] % MOD;
    
80.                     }
    
81.                     ans = (ans + temp) % MOD;
    
82.                 }
    
83.             }
    
84.         }
    
85.         cout << ans << '\n';
    
86.     }
    
87.     return 0;
    
88. }

复制代码

四、关键知识点详解

• 模逆元计算：使用费马小定理和快速幂
• 多项式系数：多重集的排列数公式
• 预处理技巧：O(n)时间预处理阶乘和逆阶乘
• 边界处理：剩余奖品情况的分类讨论
  
  

五、复杂度分析

• 预处理：O(max_n)
• 每个测试用例：O(M)
• 总复杂度：O(max_n + T*M)
  
  

六、实际应用场景

• 资源分配问题
• 排列组合计算
• 概率统计中的分布计算
• 密码学中的大数运算
  
  

七、学习建议

• 掌握快速幂算法的实现
• 理解模逆元的数学原理
• 熟练运用组合数学公式
• 练习类似的分配问题变种
  
  

转自：2023年GESP八级考题解析：奖品分配的组合数学解法