Cerința

O persoana are de urcat n trepte. Ştiind că de pe treapta i poate trece pe treapta i + 1, i + 2, ..., i + (k - 1) sau i + k, aflaţi în câte moduri poate urca cele n trepte. (inițial se afla treapta 1)

Date de intrare

Programul citește de la tastatură numerele n și k.

Date de ieșire

Programul va afișa pe ecran numărul c, reprezentând numărul de moduri în care poate urca cele n trepte.

Restricții și precizări

• 1 < n ≤ 1.000.000;
• 1 ≤ k ≤ n - 1;
• deoarece numărul va fi prea mare sa va afișa modulo 9001;
• la început, persoana se află pe treapta 1.

Exemplul 1:

Intrare

2 2

Ieșire

1

Explicație

Există o soluție, aceea când sare direct pe treapta 2.

Exemplul 2:

Intrare

4 2

Ieșire

3

Explicație

Prima: 1 -> 2 -> 3 -> 4

Cerința

O persoana are de urcat n trepte. Ştiind că de pe treapta i poate trece pe treapta i + 1, i + 2, ..., i + (k - 1) sau i + k, aflaţi în câte moduri poate urca cele n trepte. (inițial se afla treapta 1)

Date de intrare

Programul citește de la tastatură numerele n și k.

Date de ieșire

Programul va afișa pe ecran numărul c, reprezentând numărul de moduri în care poate urca cele n trepte.

Restricții și precizări

• 1 < n ≤ 1.000.000;
• 1 ≤ k ≤ n - 1;
• deoarece numărul va fi prea mare sa va afișa modulo 9001;
• la început, persoana se află pe treapta 1.

Exemplul 1:

Intrare

2 2

Ieșire

1

Explicație

Există o soluție, aceea când sare direct pe treapta 2.

Exemplul 2:

Intrare

4 2

Ieșire

3

Explicație

Prima: 1 -> 2 -> 3 -> 4
A doua: 1 -> 2 -> 4
A treia: 1 -> 3 -> 4

#include <bits/stdc++.h>
using namespace std;

short a[1000001];

int main()
{
    int n , k;
    cin >> n >> k;
    a[1] = a[2] = 1;
    for(int i = 3 ; i <= k ; i++)
        a[i] = (2 * a[i - 1]) % 9001;

    for(int i = k + 1 ; i <= n ; i++)
        a[i] = (2 * a[i - 1] - a[i - k - 1] + 9001) % 9001;

    cout << a[n];
}