22 . 爬樓梯 k

Submit
Status
Ranklist
Back to Problems List

User's AC Ratio

86.0% (37/43)

Submission's AC Ratio

56.5% (78/138)

Tags

2020 高階競技程式設計 - Contest #1

Description

喔就是，總是有些人不好好一階一階上樓梯，偏要一次跳兩階對吧

還記得那個窮學生 sakura 嗎？
有人委託他去算從地板(第 0 階)開始，
每次可以只爬 1 階或直接跳 2 階，到第 $N$ 階樓梯有幾種爬法？

rainsn 是講求效率的人，他認為爬樓梯不是一定要快，但也不該總是慢，這樣在時間和體力間才能達到一個平衡
所以他多設下一個條件，在不超過 $k$ 次爬到 $N$ 階有幾種爬法？

Input Format

輸入兩個正整數 $N, k$ $(1 \le k \le N \le 10^ 3)$

Output Format

到第 $N$ 階樓梯且不超過 $k$ 次有幾種爬法
由於計算結果會很龐大，請輸出把結果除以 $10^9 + 9$ 後得到的餘數

Sample Input 1

3 2

Sample Output 1

2

Sample Input 2

4 2

Sample Output 2

1

Sample Input 3

4 3

Sample Output 3

4

Sample Input 4

10 6

Sample Output 4

16

Sample Input 5

777 666

Sample Output 5

101644135

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~36 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1
6 1000 65536 65536 1
7 1000 65536 65536 1
8 1000 65536 65536 1
9 1000 65536 65536 1
10 1000 65536 65536 1
11 1000 65536 65536 1
12 1000 65536 65536 1
13 1000 65536 65536 1
14 1000 65536 65536 1
15 1000 65536 65536 1
16 1000 65536 65536 1
17 1000 65536 65536 1
18 1000 65536 65536 1
19 1000 65536 65536 1
20 1000 65536 65536 1
21 1000 65536 65536 1
22 1000 65536 65536 1
23 1000 65536 65536 1
24 1000 65536 65536 1
25 1000 65536 65536 1
26 1000 65536 65536 1
27 1000 65536 65536 1
28 1000 65536 65536 1
29 1000 65536 65536 1
30 1000 65536 65536 1
31 1000 65536 65536 1
32 1000 65536 65536 1
33 1000 65536 65536 1
34 1000 65536 65536 1
35 1000 65536 65536 1
36 1000 65536 65536 1
Submit
Status
Ranklist
Back to Top