2026年6月GESP真题及题解（C++八级）：堆石子

2026年6月GESP真题及题解C八级堆石子题目描述有m mm堆石子编号为1 , 2 , ⋯ , m 1, 2, \cdots, m1,2,⋯,m其石子数量分别记为a 1 , a 2 , ⋯ , a m a_1, a_2, \cdots, a_ma1​,a2​,⋯,am​。现在要求第1 11堆石子恰有n nn个即a 1 n a_1 na1​n并且此后每堆石子的数量严格小于前一堆即a i a i − 1 a_i a_{i-1}ai​ai−1​(2 ≤ i ≤ m 2 \le i \le m2≤i≤m)。此外每堆至少需要有一个石子即a i ≥ 1 a_i \ge 1ai​≥1(1 ≤ i ≤ m 1 \le i \le m1≤i≤m)。在总石子数量不设限制的情况下给定m ≥ 2 , n ≥ 1 m \ge 2, n \ge 1m≥2,n≥1有多少个满足要求的石子堆放方案两个方案不同当且仅当两个方案中至少有一堆石子数量不同。如果不存在满足要求的方案输出0 00。由于方案数可能很大请输出方案数对10 9 7 10^9 71097取模后的结果。输入格式输入一行两个正整数m mm和n nn。输出格式输出一个整数表示总方案数对10 9 7 10^9 71097取模后的结果。输入输出样例 1输入 13 5输出 16说明/提示样例解释 1有( 5 , 4 , 3 ) (5, 4, 3)(5,4,3)( 5 , 4 , 2 ) (5, 4, 2)(5,4,2)( 5 , 4 , 1 ) (5, 4, 1)(5,4,1)( 5 , 3 , 2 ) (5, 3, 2)(5,3,2)( 5 , 3 , 1 ) (5, 3, 1)(5,3,1)和( 5 , 2 , 1 ) (5, 2, 1)(5,2,1)共计6 66种方案。数据范围数据点编号数据范围特殊性质1 , 2 1,21,22 ≤ m ≤ 100 , 1 ≤ n ≤ 100 2 \le m \le 100, 1 \le n \le 1002≤m≤100,1≤n≤1000 ≤ n − m ≤ 5 0 \le n - m \le 50≤n−m≤53 , 4 , 5 3,4,53,4,52 ≤ m ≤ 100 , 1 ≤ n ≤ 10 8 2 \le m \le 100, 1 \le n \le 10^82≤m≤100,1≤n≤108无6 , 7 , 8 , 9 , 10 6,7,8,9,106,7,8,9,102 ≤ m ≤ 10 5 , 1 ≤ n ≤ 10 8 2 \le m \le 10^5, 1 \le n \le 10^82≤m≤105,1≤n≤108^思路分析题目要求统计满足以下条件的序列数量第一堆石子数固定为 n 之后的每一堆石子数严格小于前一堆即a i a i − 1 a_i a_{i-1}ai​ai−1​每堆至少一个石子即a i ≥ 1 a_i \ge 1ai​≥1。由于第一堆已经确定后 m-1 堆必须是从集合{ 1 , 2 , … , n − 1 } \{1,2,\dots,n-1\}{1,2,…,n−1}中选出的 m-1 个不同的正整数并且按照严格递减的顺序排列因为越往后越小。对于任意选出的 m-1 个不同数降序排列是唯一的所以方案数就是从 n-1 个数中选出 m-1 个数的组合数ans ( n − 1 m − 1 ) \text{ans} \binom{n-1}{m-1}ans(m−1n−1​)当 ( n m ) 时无法选出 ( m-1 ) 个不同的正整数方案数为 0。由于 n 最大可达10 8 10^8108而 m 最大为10 5 10^5105我们不能预处理全部阶乘但组合数的下指标 ( k m-1 ) 很小。组合数可写作( N K ) N ⋅ ( N − 1 ) ⋯ ( N − K 1 ) K ! \binom{N}{K} \frac{N \cdot (N-1) \cdots (N-K1)}{K!}(KN​)K!N⋅(N−1)⋯(N−K1)​其中 N n-1K m-1 。分子只需计算 K 项乘积分母为 K! 均可直接计算并对模10 9 7 10^971097取模最后用费马小定理求分母逆元。时间复杂度O ( m ) O(m)O(m)空间复杂度O ( 1 ) O(1)O(1)完全满足题目要求。代码实现#includebits/stdc.husingnamespacestd;typedeflonglongll;constll MOD1000000007;// 快速幂计算 a^e % MODllqp(ll a,ll e){ll r1;while(e){if(e1)rr*a%MOD;aa*a%MOD;e1;}returnr;}intmain(){ll m,n;cinmn;if(nm){// 无法选出 m-1 个正整数cout0;return0;}ll Km-1;// 组合数的下指标ll Nn-1;// 组合数的上指标ll num1,den1;// 分子分母for(ll i0;iK;i){numnum*((N-i)%MOD)%MOD;// 累乘 N*(N-1)*...denden*((i1)%MOD)%MOD;// 累乘 1*2*...*K}ll ansnum*qp(den,MOD-2)%MOD;// 乘以分母逆元coutans;return0;}功能分析输入处理读取两个正整数 ( m, n )。可行性判断若 ( n m ) 则直接输出 0。组合数计算分子从 ( n-1 ) 开始向下乘 ( m-1 ) 项分母计算 (m-1)! 用快速幂求分母的模逆得到最终组合数。输出结果对10 9 7 10^971097取模。各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转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.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}