2026年山东省【信息学体验营】复赛真题及题解T2小兔子爬楼梯题目描述森林学校里有一座n nn级的台阶小兔子要跳上去。它每一次跳跃可以选择跳1 11级、2 22级、……、m mm级每次跳的级数必须是整数且在1 11到m mm之间。小兔子体力无限他想尝试各种跳跃方案跳完n nn级台阶的跳跃序列。但是小兔子的老师说“每一种跳跃方案中至少要有一次跳的级数不少于k kkk ≤ m k\le mk≤m级称为‘逆天一跳’才算一种合格的跳跃方案”。比如n 7 n7n7m 5 m5m5k 3 k3k3在以下跳跃方案中跳跃序列1 , 2 , 2 , 2 1,2,2,21,2,2,2不是合格的跳跃方案跳跃序列1 , 3 , 3 1,3,31,3,3是合格的跳跃方案跳跃序列1 , 4 , 2 1,4,21,4,2与1 , 5 , 1 1,5,11,5,1都是合格的跳跃方案。现在小兔子想知道一共有多少种不同的合格的跳跃方案能恰好跳完n nn级台阶。注意跳跃序列顺序不同算不同的跳跃方案。比如1 , 1 , 5 1,1,51,1,5与1 , 5 , 1 1,5,11,5,1是两种不同的跳跃方案。因为合格的跳跃方案可能太多了答案要对10 9 7 10^971097取模。输入格式一行三个整数n , m , k n,m,kn,m,k。输出格式输出一个整数表示符合条件的合格跳跃方案总数对10 9 7 10^971097取模。输入输出样例 1输入 13 3 2输出 13输入输出样例 2输入 24 3 2输出 26输入输出样例 3输入 310000 100 60输出 320640995说明/提示【样例1 11说明】合格的跳跃方案有3 33种2 , 1 2,12,11 , 2 1,21,23 33。【数据范围】所有数据满足1 ≤ n ≤ 100000 1\le n\le 1000001≤n≤1000001 ≤ m ≤ 100 1\le m\le 1001≤m≤1001 ≤ k ≤ m 1\le k\le m1≤k≤m。测试点编号m mmk kk特殊性质1 ∼ 3 1\sim 31∼3 2 22 1 11无4 ∼ 9 4\sim 94∼9≤ 100 \le 100≤100 1 11无10 ∼ 20 10\sim 2010∼20≤ 100 \le 100≤100≤ m \le m≤m无思路分析题目要求计算所有跳跃序列中至少有一次跳跃的级数不少于 (k)的方案数。这等价于总方案数−所有跳跃级数都小于 (k) 的方案数即每次跳 (1\sim k-1) 级。设f[i]跳到第 i 级台阶的总方案数每次可跳1 ∼ m 1\sim m1∼m级。g[i]跳到第 i 级台阶且每一步都小于 k 的方案数每次可跳1 ∼ k − 1 1\sim k-11∼k−1级。递推关系初始f[0]1, g[0]1。对于i ≥ 1 i\ge 1i≥1f [ i ] ∑ j 1 m f [ i − j ] ( i − j ≥ 0 ) f[i]\sum_{j1}^{m} f[i-j]\quad (i-j\ge 0)f[i]∑j1m​f[i−j](i−j≥0)g [ i ] ∑ j 1 k − 1 g [ i − j ] ( i − j ≥ 0 ) g[i]\sum_{j1}^{k-1} g[i-j]\quad (i-j\ge 0)g[i]∑j1k−1​g[i−j](i−j≥0)当 k1 时g[i] 的求和范围为空故 g[i]0i0。答案ans ( f [ n ] − g [ n ] ) m o d ( 10 9 7 ) \text{ans}(f[n]-g[n])\bmod (10^97)ans(f[n]−g[n])mod(1097)复杂度时间复杂度O ( n ⋅ m ) O(n\cdot m)O(n⋅m)最大约10 7 10^7107可接受。空间复杂度O ( n ) O(n)O(n)。代码实现#includebits/stdc.husingnamespacestd;constintMOD1000000007;intn,m,k;intmain(){cinnmk;vectorlonglongf(n1,0),g(n1,0);// 1. 计算总方案数 ff[0]1;for(inti1;in;i){longlongsum0;// 最后一步跳 j 级 (1 j m)for(intj1;jm;j){if(ij){sumf[i-j];// 因为 sum 最多加 m 次每次 MODm 100不会溢出 long long}}f[i]sum%MOD;}// 2. 计算不合格方案数 g每一步都 kg[0]1;for(inti1;in;i){longlongsum0;// 最后一步只能跳 1 ~ k-1 级for(intj1;jk-1;j){if(ij){sumg[i-j];}}g[i]sum%MOD;}// 3. 答案 总方案 - 不合格方案longlongans(f[n]-g[n])%MOD;if(ans0)ansMOD;// 处理负数coutans;return0;}更多内容请关注专栏信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转【秘籍汇总】完整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;}