做旅游网站课程设计报告站长工具平台
目录
- 题目描述
- 输入格式
- 输出格式
- 样例 #1
- 样例输入 #1
- 样例输出 #1
- 提示
- 代码
题目描述
有 N N N 级台阶，你一开始在底部，每次可以向上迈 1 ∼ K 1\sim K 1∼K 级台阶，问到达第 N N N 级台阶有多少种不同方式。
输入格式
两个正整数 N , K N,K N,K。
输出格式
一个正整数 a n s ( m o d 100003 ) ans\pmod{100003} ans(mod100003)，为到达第 N N N 级台阶的不同方式数。
样例 #1
样例输入 #1
5 2
样例输出 #1
8
提示
- 对于 20 % 20\% 20% 的数据， 1 ≤ N ≤ 10 1\leq N\leq10 1≤N≤10， 1 ≤ K ≤ 3 1\leq K\leq3 1≤K≤3；
- 对于 40 % 40\% 40% 的数据， 1 ≤ N ≤ 1000 1\leq N\leq1000 1≤N≤1000；
- 对于 100 % 100\% 100% 的数据， 1 ≤ N ≤ 100000 1\leq N\leq100000 1≤N≤100000， 1 ≤ K ≤ 100 1\leq K\leq100 1≤K≤100。
代码
#include<bits/stdc++.h>
int f[100005]={1,0,0,0,0},n,k;
int main(){std::cin>>n>>k;for(int i=1; i<=n; i++) for(int j=1; j<=std::min(i,k); j++) f[i]=(f[i]+f[i-j])%100003;std::cout<<f[n];
}