2023年12月GESP真题及题解(C++八级): 奖品分配-编程阁

2023年12月GESP真题及题解(C++八级): 奖品分配

题目描述

班上有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）。

现在，请你求出每个班级礼物分配的方案数，所谓方案，指的是为每位同学都分配一个种类的奖品。

只要有一位同学获得了不同种类的奖品，即视为不同的方案。方便起见，你只需要输出方案数对10 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行，每行一个整数，表示该班级分配奖品的方案数对10 9 + 7 10^{9}+7109+7取模的结果。

输入输出样例 1

输入 1

3 3 2 1 2 3 2 1 3 5 3 1 3 1

输出 1

3 4 20

输入输出样例 2

输入 2

5 100 1 100 100 1 101 20 2 12 8 123 4 80 20 21 3 999 5 101 234 499 66 99

输出 2

1 1 125970 895031741 307187590

说明/提示

样例解释 1

对于第1 11个班级，学号为0 , 1 , 2 0,1,20,1,2的同学可以依次分别获得奖品0 , 1 , 1 0,1,10,1,1，也可以依次分别获得奖品1 , 0 , 1 1,0,11,0,1，也可以依次分别获得奖品1 , 1 , 0 1,1,01,1,0，因此共有3 33种方案。

对于第2 22个班级，学号为0 , 1 , 2 0,1,20,1,2的同学可以依次分别获得奖品0 , 1 , 1 0,1,10,1,1，也可以依次分别获得奖品1 , 0 , 1 1,0,11,0,1，也可以依次分别获得奖品1 , 1 , 0 1,1,01,1,0，也可以依次分别获得奖品1 , 1 , 1 1,1,11,1,1，因此共有4 44种方案。

对于第3 33个班级，可以把编号为0 00的奖品分配给5 55名同学中的任意一名，共有5 55种方案；再把编号为2 22的奖品分配给剩余4 44名同学中的任意一名，共有4 44种方案；最后给剩余3 33名同学自然获得1 11号奖品。因此，方案数为5 × 4 = 20 5 \times 4 = 205×4=20。

数据范围

对于30 % 30\%30%的测试点，保证N ≤ 10 N \le 10N≤10。

对于另外30 % 30\%30%的测试点，保证M = 2 M=2M=2。

对于所有测试点，保证N ≤ 1000 N \le 1000N≤1000；保证T ≤ 1000 T \le 1000T≤1000；保证M ≤ 1001 M \le 1001M≤1001。

思路分析

这道题的关键在于发现总奖品数S与人数N的关系，从而简化计算。当S=N时，必须全部分配，方案数为N!除以各奖品数量的阶乘；当S=N+1时，有一种奖品少分一个，方案数为(N+1)!除以各奖品数量的阶乘。由于模数为质数，可以用预处理阶乘和阶乘逆元来快速计算。

代码实现

#include<bits/stdc++.h>// 万能头usingnamespacestd;typedeflonglongll;constintMOD=1e9+7;// 模数constintMAXF=1001;// 最大阶乘数，因为N最大1000，N+1最大1001ll fac[MAXF+5];// 阶乘数组ll invfac[MAXF+5];// 阶乘逆元数组// 快速幂取模llpow_mod(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}returnres;}// 预处理阶乘和阶乘逆元voidinit(){fac[0]=1;for(inti=1;i<=MAXF;i++){fac[i]=fac[i-1]*i%MOD;}// 费马小定理求最大阶乘的逆元invfac[MAXF]=pow_mod(fac[MAXF],MOD-2);// 递推求其他阶乘逆元for(inti=MAXF;i>=1;i--){invfac[i-1]=invfac[i]*i%MOD;}}intmain(){init();// 预处理intT;cin>>T;while(T--){intN,M;cin>>N>>M;ll d=1;// 保存分母的逆元乘积，即所有invfac[a_i]的积intS=0;for(inti=0;i<M;i++){inta;cin>>a;S+=a;d=d*invfac[a]%MOD;// 乘以当前a_i阶乘的逆元}ll ans;if(S==N){ans=fac[N]*d%MOD;// S=N时，分子为N!}else{// S == N+1ans=fac[N+1]*d%MOD;// S=N+1时，分子为(N+1)!}cout<<ans<<endl;}return0;}

功能分析

预处理阶乘和逆元：预先计算0到1001的阶乘及其逆元，便于后续O(1)查询。
快速幂取模：用于计算阶乘的逆元（费马小定理）。
主逻辑：对于每个测试用例：
- 读入N、M和每种奖品的数量a_i。
- 计算总奖品数S。
- 计算分母的逆元乘积（所有invfac[a_i]的乘积）。
- 根据S与N的关系选择分子（N!或(N+1)!），与分母逆元相乘取模得到答案。
复杂度：

时间复杂度：预处理O(MAXF log MOD)，每个测试用例O(M)，整体O(T*M)，在数据范围内完全可以接受。
空间复杂度：O(MAXF)，用于存储阶乘和逆元表。

完整GESP C++考级真题题解专栏：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}

2023年12月GESP真题及题解(C++八级): 奖品分配