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

违规用户名^3Zj=Oha · 2024-02-02 19:11:17 · 题解

一、题目简述

给你 N 个人，以及 N+1 或 N 个物品。让你求出这些物品分给这 N 个人共有多少种不同情况。最后对 10^9 + 7 取模即可。

二、思路分析

本题实际可以简化为一道组合数学，无非就是让你计算出 N+1 个中选择 N 个（有可能有相同），或者 N 个中选择 N 个（有可能有相同），最后减去相同的即可。

三、代码实现

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int N=1e4+5;
long long n,m,a[N],c[N][N],t,sum,ans;
int main(){
    cin>>t;
    c[0][0]=1;
    for(int i=1;i<=1005;i++){
        c[i][0]=c[i][i]=1;
        for(int j=1;j<i;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;//提前取余，否则会爆long long 
    }//预处理组合数 
    while(t--){
        cin>>n>>m;
        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;//记得一边乘一边取余，否则会爆long long
            sum-=a[i];
        }//计算组合数并减去重复 
        cout<<ans<<endl;
    }
    return 0;
}