企业官网建设流程全解析

2026年山东省【信息学体验营】复赛真题及题解T2：小兔子爬楼梯

题目描述

森林学校里有一座n nn级的台阶，小兔子要跳上去。

它每一次跳跃，可以选择跳1 11级、2 22级、……、m mm级（每次跳的级数必须是整数，且在1 11到m mm之间）。

小兔子体力无限，他想尝试各种跳跃方案（跳完n nn级台阶的跳跃序列）。

但是，小兔子的老师说：“每一种跳跃方案中，至少要有一次跳的级数不少于k kk（k ≤ m k\le mk≤m）级（称为‘逆天一跳’），才算一种合格的跳跃方案”。

比如：n = 7 n=7n=7，m = 5 m=5m=5，k = 3 k=3k=3，在以下跳跃方案中：

跳跃序列：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^9+7109+7取模。

输入格式

一行三个整数：n , m , k n,m,kn,m,k。

输出格式

输出一个整数，表示符合条件的合格跳跃方案总数（对10 9 + 7 10^9+7109+7取模）。

输入输出样例 1

输入 1

3 3 2

输出 1

3

输入输出样例 2

输入 2

4 3 2

输出 2

6

输入输出样例 3

输入 3

10000 100 60

输出 3

20640995

说明/提示

【样例1 11说明】

合格的跳跃方案有3 33种：2 , 1 2,12,1；1 , 2 1,21,2；3 33。

【数据范围】

所有数据满足：1 ≤ n ≤ 100000 1\le n\le 1000001≤n≤100000，1 ≤ m ≤ 100 1\le m\le 1001≤m≤100，1 ≤ k ≤ m 1\le k\le m1≤k≤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≥1：
  f [ i ] = ∑ j = 1 m f [ i − j ] ( i − j ≥ 0 ) f[i]=\sum_{j=1}^{m} f[i-j]\quad (i-j\ge 0)f[i]=∑j=1m​f[i−j](i−j≥0)
  g [ i ] = ∑ j = 1 k − 1 g [ i − j ] ( i − j ≥ 0 ) g[i]=\sum_{j=1}^{k-1} g[i-j]\quad (i-j\ge 0)g[i]=∑j=1k−1​g[i−j](i−j≥0)
  当 k=1 时，g[i] 的求和范围为空，故 g[i]=0（i>0）。

• 答案：
  ans = ( f [ n ] − g [ n ] ) m o d ( 10 9 + 7 ) \text{ans}=(f[n]-g[n])\bmod (10^9+7)ans=(f[n]−g[n])mod(109+7)

复杂度

• 时间复杂度：O ( n ⋅ m ) O(n\cdot m)O(n⋅m)，最大约10 7 10^7107，可接受。
• 空间复杂度：O ( n ) O(n)O(n)。

代码实现

#include<bits/stdc++.h>usingnamespacestd;constintMOD=1000000007;intn,m,k;intmain(){cin>>n>>m>>k;vector<longlong>f(n+1,0),g(n+1,0);// 1. 计算总方案数 ff[0]=1;for(inti=1;i<=n;++i){longlongsum=0;// 最后一步跳 j 级 (1 <= j <= m)for(intj=1;j<=m;++j){if(i>=j){sum+=f[i-j];// 因为 sum 最多加 m 次，每次 < MOD，m <= 100，不会溢出 long long}}f[i]=sum%MOD;}// 2. 计算不合格方案数 g：每一步都 < kg[0]=1;for(inti=1;i<=n;++i){longlongsum=0;// 最后一步只能跳 1 ~ k-1 级for(intj=1;j<=k-1;++j){if(i>=j){sum+=g[i-j];}}g[i]=sum%MOD;}// 3. 答案 = 总方案 - 不合格方案longlongans=(f[n]-g[n])%MOD;if(ans<0)ans+=MOD;// 处理负数cout<<ans;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++标准模板库STL：
https://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 点击跳转

· 文末祝福 ·

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