GESP 八级

P10112 [GESP202312 八级] 奖品分配

本题解由陈奕涵提供

N个同学，M种奖品，第i种奖品有ai个
每位同学都可以分到一个奖品，最多剩一个
求出方案数对1e9 + 7取模的结果

思路

因为奖品最多剩余一个，所以分类讨论

当剩余0个奖品时：

\(C^{a_1}_n+C^{a_2}_{n-a_1}+...+C^{a_n}_{n-a_1-a_2-...-a_{n-1}}\)

当剩余1个奖品时：

\(C^{a_1}_{n+1}+C^{a_2}_{(n+1)-{a_1}}+...+C^{a_n}_{(n+1)-{a_1}-{a_2}-...-{a_{n-1}}}\)

所以设奖品总数为sum

最后答案是\(C^{a_1}_{sum}+C^{a_2}_{sum-{a_1}}+...+C^{a_n}_{sum-a_1-a_2-...a_{n-1}}\)

代码

#include<bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
int a[1010], C[1010][1010];

void init() {
    for (int i = 0; i < 1010; i++) { 
        for (int j = 0; j <= i; j++) {
            if (j == 0 || j == i) C[i][j] = 1;
            else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
        }
    }
}

int main(){
    init();
    int t;
    cin >> t;
    while(t--){
        int n, m;
        cin >> n >> m;
        long long sum = 0, ans = 1;
        for(int i = 1; i <= m; i++){
            cin >> a[i];
            sum += a[i];
        }
        for(int i = 1; i <= m; i++){
            ans = (ans * C[sum][a[i]]) % mod;
            sum -= a[i];
        }


        cout << ans << '\n';
    }

    return 0;
}