企业官网建设流程全解析

山东网站优化,做一手房用什么网站,北京 网站建设600,wordpress 表单校验2023年12月GESP真题及题解(C八级): 奖品分配 题目描述 班上有 N N N 名同学#xff0c;学号从 0 0 0 到 N − 1 N-1 N−1。有 M M M 种奖品要分给这些同学#xff0c;其中#xff0c;第 i i i 种奖品总共有 a i a_i ai​ 个 #xff08; i 0 , 1 , ⋯ , M − 1 i0,…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 i0,1, \cdots ,M-1i0,1,⋯,M−1。巧合的是奖品的数量不多不少每位同学都可以恰好分到一个奖品且最后剩余的奖品不超过1 11个即N ≤ a 0 a 1 ⋯ a M − 1 ≤ N 1 N\le a_0a_1 \cdots a_{M-1}\le N1N≤a0​a1​⋯aM−1​≤N1。现在请你求出每个班级礼物分配的方案数所谓方案指的是为每位同学都分配一个种类的奖品。只要有一位同学获得了不同种类的奖品即视为不同的方案。方便起见你只需要输出方案数对10 9 7 10^{9}71097取模后的结果即可。共有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_0a_1\cdotsa_{M-1} \le N1 $。输出格式输出T TT行每行一个整数表示该班级分配奖品的方案数对10 9 7 10^{9}71097取模的结果。输入输出样例 1输入 13 3 2 1 2 3 2 1 3 5 3 1 3 1输出 13 4 20输入输出样例 2输入 25 100 1 100 100 1 101 20 2 12 8 123 4 80 20 21 3 999 5 101 234 499 66 99输出 21 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×420。数据范围对于30 % 30\%30%的测试点保证N ≤ 10 N \le 10N≤10。对于另外30 % 30\%30%的测试点保证M 2 M2M2。对于所有测试点保证N ≤ 1000 N \le 1000N≤1000保证T ≤ 1000 T \le 1000T≤1000保证M ≤ 1001 M \le 1001M≤1001。思路分析这道题的关键在于发现总奖品数S与人数N的关系从而简化计算。当SN时必须全部分配方案数为N!除以各奖品数量的阶乘当SN1时有一种奖品少分一个方案数为(N1)!除以各奖品数量的阶乘。由于模数为质数可以用预处理阶乘和阶乘逆元来快速计算。代码实现#includebits/stdc.h// 万能头usingnamespacestd;typedeflonglongll;constintMOD1e97;// 模数constintMAXF1001;// 最大阶乘数因为N最大1000N1最大1001ll fac[MAXF5];// 阶乘数组ll invfac[MAXF5];// 阶乘逆元数组// 快速幂取模llpow_mod(ll a,ll b){ll res1;while(b){if(b1)resres*a%MOD;aa*a%MOD;b1;}returnres;}// 预处理阶乘和阶乘逆元voidinit(){fac[0]1;for(inti1;iMAXF;i){fac[i]fac[i-1]*i%MOD;}// 费马小定理求最大阶乘的逆元invfac[MAXF]pow_mod(fac[MAXF],MOD-2);// 递推求其他阶乘逆元for(intiMAXF;i1;i--){invfac[i-1]invfac[i]*i%MOD;}}intmain(){init();// 预处理intT;cinT;while(T--){intN,M;cinNM;ll d1;// 保存分母的逆元乘积即所有invfac[a_i]的积intS0;for(inti0;iM;i){inta;cina;Sa;dd*invfac[a]%MOD;// 乘以当前a_i阶乘的逆元}ll ans;if(SN){ansfac[N]*d%MOD;// SN时分子为N!}else{// S N1ansfac[N1]*d%MOD;// SN1时分子为(N1)!}coutansendl;}return0;}功能分析预处理阶乘和逆元预先计算0到1001的阶乘及其逆元便于后续O(1)查询。快速幂取模用于计算阶乘的逆元费马小定理。主逻辑对于每个测试用例读入N、M和每种奖品的数量a_i。计算总奖品数S。计算分母的逆元乘积所有invfac[a_i]的乘积。根据S与N的关系选择分子N!或(N1)!与分母逆元相乘取模得到答案。复杂度时间复杂度预处理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更多csp信奥赛C学习资料汇总1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html4、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转CSP信奥赛C一等奖通关刷题题单及题解持续更新https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}