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

6小时前比赛题解12

一、问题背景

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

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

二、算法核心思想

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

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

#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;
}