#4699. 台阶问题

    ID: 4699 Type: RemoteJudge 1000ms 125MiB Tried: 22 Accepted: 17 Difficulty: 4 Uploaded By: Tags>递推斐波那契,Fibonacci线性递推,递推式

台阶问题

题目描述

NN级的台阶,你一开始在底部,每次可以向上迈最多KK级台阶(最少11级),问到达第NN级台阶有多少种不同方式。

输入格式

两个正整数N,K。

输出格式

一个正整数,为不同方式数,由于答案可能很大,你需要输出ansmod100003ans \bmod 100003后的结果。

5 2
8

提示

对于20%20\%的数据,有N10,K3N ≤ 10, K ≤ 3;

对于40%40\%的数据,有N1000N ≤ 1000;

对于100%100\%的数据,有N100000,K100N ≤ 100000,K ≤ 100