本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题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 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≤a0a1⋯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 ≤ a 0 a 1 ⋯ a M − 1 ≤ N 1 N \le a_0a_1\cdotsa_{M-1} \le N1N≤a0a1⋯aM−1≤N1。【输出】输出T TT行每行一个整数表示该班级分配奖品的方案数对10 9 7 10^{9}71097取模的结果。【输入样例】3 3 2 1 2 3 2 1 3 5 3 1 3 1【输出样例】3 4 20【核心思想】问题分析给定N NN名同学和M MM种奖品第i ii种奖品有a i a_iai个。每位同学恰好分到一个奖品剩余奖品不超过1 11个即∑ a i N \sum a_i N∑aiN或N 1 N1N1。求分配方案数对10 9 7 10^971097取模。这是一个多重集排列问题核心在于将为每位同学分配奖品种类转化为将N NN个位置分配给M MM种颜色的组合计数。算法选择组合数递推预处理 乘法原理预处理组合数C ( n , k ) C(n,k)C(n,k)然后按顺序为每种奖品选择位置利用乘法原理累乘方案数关键步骤预处理组合数C ( i , j ) C ( i − 1 , j ) C ( i − 1 , j − 1 ) m o d ( 10 9 7 ) C(i,j) C(i-1,j) C(i-1,j-1) \bmod (10^97)C(i,j)C(i−1,j)C(i−1,j−1)mod(1097)处理每个测试用例读入N NN、M MM和a [ 1.. M ] a[1..M]a[1..M]计算总奖品数s u m ∑ a i sum \sum a_isum∑ai确定初始可用位置数t tt若s u m N sum NsumN则t N 1 t N1tN1否则t N t NtN按顺序分配位置i ii从1 11到M MM从t tt个位置中选a i a_iai个放第i ii种奖品a n s ← a n s × C ( t , a i ) m o d ( 10 9 7 ) ans \leftarrow ans \times C(t, a_i) \bmod (10^97)ans←ans×C(t,ai)mod(1097)更新可用位置t ← t − a i t \leftarrow t - a_it←t−ai输出a n s ansans时间/空间复杂度时间复杂度O ( N m a x 2 T ⋅ M ) O(N_{max}^2 T \cdot M)O(Nmax2T⋅M)预处理组合数O ( N m a x 2 ) O(N_{max}^2)O(Nmax2)每个测试用例O ( M ) O(M)O(M)空间复杂度O ( N m a x 2 ) O(N_{max}^2)O(Nmax2)组合数表多重集排列与组合数的核心思想位置选择模型将N NN名同学视为N NN个不同位置分配奖品等价于为每种奖品选择对应数量的位置。第i ii种奖品有a i a_iai个从剩余t tt个位置中选a i a_iai个方案数为C ( t , a i ) C(t, a_i)C(t,ai)乘法原理的适用性各种奖品的位置选择相互独立选定一种奖品的位置后剩余位置给下一种总方案数为各步方案数的乘积剩余奖品的处理当s u m N 1 sum N1sumN1时总奖品比人数多1 11意味着有1 11个奖品不分配。此时初始位置数t N 1 t N1tN1最后会剩余1 11个位置即1 11个奖品不分配自然地处理了剩余不超过1 11的约束组合数的对称性C ( t , a i ) C ( t , t − a i ) C(t, a_i) C(t, t-a_i)C(t,ai)C(t,t−ai)选择a i a_iai个位置放该奖品等价于选择t − a i t-a_it−ai个位置不放该奖品两种视角等价适用于多重集排列、分步计数、组合数应用类问题【解题思路】【算法标签】#普及 #排列组合【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglong// 将int宏定义为long long防止组合数计算溢出constintN1005;// 定义最大数组大小常量N为1005constintmod1e97;// 定义模数mod为1e97intT,n,m;// T为测试用例数n为同学人数总位置数m为奖品种类数inta[N];// a[i]为第i种奖品的数量intc[N][N];// 组合数表c[n][m]即C(n,m)intans,sum;// ans为当前测试用例的答案sum为所有奖品数量的总和// 初始化组合数表杨辉三角法预处理voidinit(){for(inti0;iN;i)// 枚举n从0到N-1{for(intj0;ji;j)// 枚举m从0到n{if(j0){c[i][j]1;// 边界条件C(i,0)1}else{// 组合数递推公式C(i,j)C(i-1,j)C(i-1,j-1)对mod取模c[i][j](c[i-1][j]c[i-1][j-1])%mod;}}}}signedmain()// 使用signed main是因为#define int long long后main返回值类型需要显式声明{// 预处理组合数表init();// 读入测试用例数cinT;while(T--)// 循环处理每个测试用例{// 读入同学人数n和奖品种类数mcinnm;// 初始化奖品总数为0sum0;// 读入每种奖品的数量for(inti1;im;i)// 循环读入m种奖品{cina[i];// 读入第i种奖品的数量a[i]suma[i];// 累加计算所有奖品的总数}// 初始化答案为1乘法单位元ans1;intt;// t为当前剩余可用位置数// 计算初始可用位置数if(sumn){tn1;// 如果奖品总数超过n说明有1个奖品剩余可用位置为n1}else{tn;// 如果奖品总数等于n可用位置恰好为n}// 计算排列方案数依次从剩余位置中为每种奖品选择放置位置for(inti1;im;i)// 枚举每种奖品{// 从t个可用位置中选择a[i]个位置放第i种奖品ans(ans*c[t][a[i]])%mod;// 累乘组合数对mod取模// 减少可用位置数已放置a[i]个奖品t-a[i];}// 输出当前测试用例的方案数coutansendl;}return0;}【运行结果】3 3 2 1 2 3 3 2 1 3 4 5 3 1 3 1 20