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

一、问题背景

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

1. 刚好分配完所有奖品

2. 恰好剩余1个奖品未分配

二、算法核心思想

1. 阶乘预处理：预先计算阶乘和逆阶乘数组

2. 快速幂优化：使用快速幂计算模逆元

3. 多项式系数：利用组合数公式计算分配方案

4. 模运算处理：确保大数运算在模数范围内

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

#include <iostream>
#include <vector>
using namespACe std;

const int MOD = 1e9 + 7;  // 标准模数

// 预计算阶乘和逆阶乘数组
vector<long long> fact, inv_fact;

// 快速幂计算（用于求模逆元）
long long pow_mod(long long x, long long n) {
    long long res = 1;
    while (n > 0) {
        if (n % 2 == 1) res = (res * x) % MOD;
        x = (x * x) % MOD;
        n /= 2;
    }
    return res;
}

// 初始化阶乘表（O(n)预处理）
void init_fact(int max_n) {
    fact.resize(max_n + 1);
    inv_fact.resize(max_n + 1);
    fact[0] = 1;
    for (int i = 1; i <= max_n; ++i) {
        fact[i] = (fact[i-1] * i) % MOD;  // 计算i! mod MOD
    }
    // 费马小定理求逆元
    inv_fact[max_n] = pow_mod(fact[max_n], MOD-2);
    // 递推计算逆阶乘
    for (int i = max_n-1; i >= 0; --i) {
        inv_fact[i] = (inv_fact[i+1] * (i+1)) % MOD;
    }
}

// 计算组合数C(n,k) mod MOD
long long comb(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD;
}

int main() {
    ios::sync_with_stdio(false);  // 加速IO
    cin.tie(nullptr);
    
    int T;  // 测试用例数
    cin >> T;
    
    // 预处理阶乘表（最大支持1e5+5）
    init_fact(1e5 + 5);
    
    while (T--) {
        int N, M;  // 奖品总数和团队数
        cin >> N >> M;
        vector<int> a(M);  // 各团队需求
        int sum = 0;
        for (int i = 0; i < M; ++i) {
            cin >> a[i];
            sum += a[i];
        }
        
        long long ans = 1;
        if (sum == N) {
            // 情况1：刚好分配完
            ans = fact[N];  // N! / (a1!a2!...am!)
            for (int i = 0; i < M; ++i) {
                ans = ans * inv_fact[a[i]] % MOD;
            }
        } else {
            // 情况2：剩余1个奖品
            ans = 0;
            for (int i = 0; i < M; ++i) {
                if (a[i] > 0) {
                    // 假设剩余的是第i种奖品
                    long long temp = fact[N];
                    for (int j = 0; j < M; ++j) {
                        int cnt = (j == i) ? (a[j] - 1) : a[j];
                        temp = temp * inv_fact[cnt] % MOD;
                    }
                    ans = (ans + temp) % MOD;
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

四、关键知识点详解

1. 模逆元计算：使用费马小定理和快速幂

2. 多项式系数：多重集的排列数公式

3. 预处理技巧：O(n)时间预处理阶乘和逆阶乘

4. 边界处理：剩余奖品情况的分类讨论

五、复杂度分析

• 预处理：O(max_n)

• 每个测试用例：O(M)

• 总复杂度：O(max_n + T*M)

六、实际应用场景

1. 资源分配问题

2. 排列组合计算

3. 概率统计中的分布计算

4. 密码学中的大数运算

七、学习建议

1. 掌握快速幂算法的实现

2. 理解模逆元的数学原理

3. 熟练运用组合数学公式

4. 练习类似的分配问题变种