欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总帖：GESP认证C++编程真题解析 | 汇总
【题目来源】
洛谷：[P10112 GESP202312 八级] 奖品分配 - 洛谷
【题目描述】
班上有N NN名同学，学号从0 00到N − 1 N-1N−1。有M MM种奖品要分给这些同学，其中，第i ii种奖品总共有a i a_iai个 （i = 0 , 1 , ⋯ , M − 1 i=0,1, \cdots ,M-1i=0,1,⋯,M−1）。
巧合的是，奖品的数量不多不少，每位同学都可以恰好分到一个奖品，且最后剩余的奖品不超过1 11个（即：N ≤ a 0 + a 1 + ⋯ + a M − 1 ≤ N + 1 N\le a_0+a_1+ \cdots +a_{M-1}\le N+1N≤a0+a1+⋯+aM−1≤N+1）。
现在，请你求出每个班级礼物分配的方案数，所谓方案，指的是为每位同学都分配一个种类的奖品。
只要有一位同学获得了不同种类的奖品，即视为不同的方案。方便起见，你只需要输出方案数对1 0 9 + 7 10^{9}+7109+7取模后的结果即可。
共有T TT个班级都面临着奖品分配的问题，你需要依次为他们解答。
【输入】
第一行一个整数T TT，表示班级数量。
接下来T TT行，每行若干用单个空格隔开的正整数。首先是两个正整数N , M N,MN,M，接着是M MM个正整数a 0 , a 1 . . . a M − 1 a_0,a_1...a_{M-1}a0,a1...aM−1。保证 $N \le a_0+a_1+\cdots+a_{M-1} \le N+1 $。
【输出】
输出T TT行，每行一个整数，表示该班级分配奖品的方案数对1 0 9 + 7 10^{9}+7109+7取模的结果。
【输入样例】
3 3 2 1 2 3 2 1 3 5 3 1 3 1【输出样例】
3 4 20【算法标签】
《洛谷 P10112 奖品分配》 #数学# #组合数学# #排列组合# #GESP# #2023#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 将int重定义为long longconstintN=1005;// 最大数组大小constintmod=1e9+7;// 模数intT,n,m;// T: 测试用例数, n: 总位置数, m: 颜色种类数inta[N];// a[i]: 第i种颜色的数量intc[N][N];// 组合数C[n][m]intans,sum;// ans: 答案, sum: 所有颜色的总数// 初始化组合数表（杨辉三角）voidinit(){for(inti=0;i<N;i++){for(intj=0;j<=i;j++){if(j==0){c[i][j]=1;// C(i,0)=1}else{// 组合数递推公式：C(i,j)=C(i-1,j)+C(i-1,j-1)c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;}}}}signedmain()// 因为#define int long long，所以用signed main{// 预处理组合数init();// 输入测试用例数cin>>T;while(T--){// 输入总位置数n和颜色种类数mcin>>n>>m;// 初始化总和sum=0;// 输入每种颜色的数量for(inti=1;i<=m;i++){cin>>a[i];sum+=a[i];// 计算颜色总数}// 初始化答案为1ans=1;intt;// 可用位置数// 计算初始可用位置数if(sum>n){t=n+1;// 如果颜色总数超过n，则t=n+1}else{t=n;// 否则t=n}// 计算排列方案数for(inti=1;i<=m;i++){// 调试输出// cout << "t a[i] " << t << ' ' << a[i] << endl;// 从t个位置中选择a[i]个位置放第i种颜色ans=(ans*c[t][a[i]])%mod;// 减少可用位置数t-=a[i];}// 输出结果cout<<ans<<endl;}return0;}【运行结果】
3 3 2 1 2 3 3 2 1 3 4 5 3 1 3 1 20
