G8001 [GESP202312 八级] 奖品分配 题解

知识点：组合数学、阶乘、模逆元、快速幂。

解题思路

奖品总数等于n时，方案数为n!/∏a_i!；若多1个，枚举剩下哪种奖品并合并公式，得到(n+1)n!/∏a_i!。预处理阶乘与模逆元。

为什么正确

没有剩余时是多重集排列；剩一件第i类时分母a_i!变成(a_i-1)!，因此该项多乘a_i，求和变成乘总奖品数n+1。

易错点

同种奖品不区分实物；多一件时不是再简单乘种类数；模数10^9+7为素数，可用费马逆元。

复杂度

设预处理上界U，时间O(U log M+所有m之和)，空间O(U)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    const long long M=1000000007;
    auto pw=[&](long long a,long long b) {
        long long v=1;
        while(b) {
            if(b&1)v=v*a%M;
            a=a*a%M;
            b>>=1;
        }
        return v;
    }
    ;
    vector<long long>f(1002,1),iv(1002,1);
    for(int i=1;i<=1001;i++)f[i]=f[i-1]*i%M;
    for(int i=0;i<=1001;i++)iv[i]=pw(f[i],M-2);
    int t;
    cin>>t;
    while(t--) {
        int n,m,sum=0;
        cin>>n>>m;
        long long ans=f[n];
        for(int i=0;i<m;i++) {
            int x;
            cin>>x;
            sum+=x;
            ans=ans*iv[x]%M;
        }
        if(sum==n+1)ans=ans*sum%M;
        cout<<ans<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用16个自行生成的测试点。