跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#LGP1192. 台阶问题

台阶问题

题目描述

一段楼梯共有 NN 级台阶。你从第 00 级出发,每一步可以向上走 11 到 KK 级,最后恰好到达第 NN 级。

请计算不同走法的数量。只要两种走法的步数不同,或某一步跨越的台阶数不同,就认为它们不同。

答案可能很大,请输出答案对 100003100003 取模的结果。

输入格式

一行两个整数 N,KN,K。

输出格式

一个整数,表示不同走法的数量对 100003100003 取模的结果。

样例

输入:

5 2

输出:

8

数据范围

  • 对于原题 20%20\% 的数据,1≤N≤101\le N\le10,1≤K≤31\le K\le3。
  • 对于原题 40%40\% 的数据,1≤N≤10001\le N\le1000。
  • 对于全部数据,1≤N≤1051\le N\le10^5,1≤K≤1001\le K\le100。

来源与评测说明

洛谷 P1192 台阶问题。

题面按原题规则整理,样例由本站补充。本站测试数据独立构造,保持原题的完整数据范围,不是洛谷官方测试点;本场采用 ACM 赛制,需通过全部测试点。