当前位置：首页 > GESP > 【GESP八级真题解析】奖品分配问题：组合数学与预处理优化（洛谷P10112）

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

5个月前 (06-28)

一、题目解读

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[i]的阶乘逆元。

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

四、代码与注释

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

// 初始化阶乘表
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;  // 计算阶乘
    }
    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)
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);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    
    // 预处理阶乘表，最大可能N是1e5
    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) {
            // 刚好分配完的情况
            ans = fact[N];
            for (int i = 0; i < M; ++i) {
                ans = ans * inv_fact[a[i]] % MOD;  // 除以各人数的阶乘逆元
            }
        } else {
            // 剩余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 << endl;
    }
    return 0;
}