题解：B4564 [山东省小学组体验营 2026] 小兔子爬楼梯
andrew_201
·
·
题解
题目大意就不多说了，直接讲解题思路。
解题思路
阅读题目我们知道
总方案数（每次跳 1 到 m 级跳完 n 级）- 完全没有逆天一跳的方案数（每次只能跳 1 到 k - 1 级跳完 n 级）= 答案。
那我们就设
答案：(dp[n] − f[n] + MOD) % MOD，加 MOD 防止负数。
转移
dp_i=\sum_{j=1}^m dp_{i-j},\ dp_0=1
f_i=\sum_{j=1}^{k-1} f_{i-j},\ f_0=1
`dp[0]=1` 代表 $0$ 级台阶，$1$ 种方案：什么都不跳。
::::success[AC code]
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MOD=1e9 + 7;
const int MAXN=100005;
long long a[MAXN];
long long b[MAXN];
long long sa[MAXN];
long long sb[MAXN];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m,k;
cin>>n>>m>>k;
a[0]=1;
sa[0]=a[0];
for(int i=1;i<=n;++i)
{
int L=i-m;
if(L<=0)
{
a[i]=sa[i-1];
}
else
{
a[i]=(sa[i-1]-sa[L-1]+MOD)%MOD;
}
sa[i]=(sa[i-1]+a[i])%MOD;
}
int t=k-1;
b[0]=1;
sb[0]=b[0];
for(int i=1;i<=n;++i)
{
if(t==0)
{
b[i]=0;
}
else
{
int L=i-t;
if(L<=0)
{
b[i]=sb[i-1];
}
else
{
b[i]=(sb[i-1]-sb[L-1]+MOD)% MOD;
}
}
sb[i]=(sb[i-1]+b[i])%MOD;
}
long long ans=(a[n]-b[n]+MOD)%MOD;
cout<<ans<<endl;
return 0;
}
```
::::
[AC 记录](https://www.luogu.com.cn/record/290955272)
完结撒花~~