【题目来源】https://www.luogu.com.cn/problem/P1192【题目描述】有 N 级台阶你一开始在底部每次可以向上迈 1∼K 级台阶问到达第 N 级台阶有多少种不同方式。【输入格式】两个正整数 NK。​​​​​​​【输出格式】一个正整数 ans(mod100003)为到达第 N 级台阶的不同方式数。【输入样例】5 2​​​​​​​【输出样例】8【数据范围】对于 20% 的数据1≤N≤101≤K≤3对于 40% 的数据1≤N≤1000对于 100% 的数据1≤N≤10^51≤K≤100。【算法分析】● f[i] 表示从底部到第 i 级台阶的方案数。● 一维前缀和与差分https://blog.csdn.net/hnjzsyjyj/article/details/145627134● 二维前缀和与差分https://blog.csdn.net/hnjzsyjyj/article/details/145671816【算法代码】#include bits/stdc.h using namespace std; const int MOD1e53; const int N1e55; int f[N],s[N]; int main() { int n,k; cinnk; f[0]1,s[0]1; for(int i1; in; i) { if(ik) f[i]s[i-1]%MOD; else { f[i](s[i-1]-s[i-k-1]MOD)%MOD; } s[i](s[i-1]f[i])%MOD; } coutf[n]endl; return 0; } /* in:5 2 out:8 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/145671816https://blog.csdn.net/hnjzsyjyj/article/details/145627134https://blog.csdn.net/hnjzsyjyj/article/details/142732833https://blog.csdn.net/hnjzsyjyj/article/details/147405964https://blog.csdn.net/hnjzsyjyj/article/details/145290457https://blog.csdn.net/hnjzsyjyj/article/details/112797538https://blog.csdn.net/hnjzsyjyj/article/details/100418268