#P1192. 台阶问题

    ID: 140 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>斐波那契Fibonacci线性递推递推式递推

台阶问题

题目描述

NN 级台阶,你一开始在底部,每次可以向上迈 1K1\sim K 级台阶,问到达第 NN 级台阶有多少种不同方式。

输入格式

两个正整数 N,KN,K

输出格式

一个正整数 ans(mod100003)ans\pmod{100003},为到达第 NN 级台阶的不同方式数。

5 2
8

提示

  • 对于 20%20\% 的数据,1N101\leq N\leq101K31\leq K\leq3
  • 对于 40%40\% 的数据,1N10001\leq N\leq1000
  • 对于 100%100\% 的数据,1N1000001\leq N\leq1000001K1001\leq K\leq100