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

C. 台阶问题

  • 传统题
  • 2000ms
  • 256MiB

台阶问题

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

一段楼梯共有 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 赛制,需通过全部测试点。

递推与递归入门

未参加
状态
已结束
规则
XCPC
题目
6
开始于
2026-10-21 18:00
结束于
2026-10-21 23:00
持续时间
5 小时
主持人
参赛人数
17