题解

点个赞吧

题目大意

有多名同学和多种奖品，奖品总数刚好等于人数或只多一个，每人分一个奖品，求一共有多少种不同分配方法，结果对 1e9+7 取模

解题思路

先提前打好组合数表格，每次读入数据后，依次从剩余人数里选出对应数量同学发同种奖品，把所有组合数相乘就是总方案数

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int mod=1e9+7,N=1001;
int t;
ll n,m,a[N],c[N][N];
int main(){
    for(int i=0;i<N;i++){
        for(int j=0;j<=i;j++){
            if(j==0) c[i][j]=1;
            else c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
        }
    }
    cin>>t;
    while(t--){
        cin>>n>>m;
        ll ans=1,sum=0;
        for(int i=1;i<=m;i++){
            cin>>a[i];
            sum+=a[i];
        }
        for(int i=1;i<=m;i++){
            ans*=c[sum][a[i]];
            ans%=mod;
            sum-=a[i];
        }
        cout<<ans<<endl;
    }
    return 0;
}

时间复杂度O(1000²)