Cerința

Se dau două numere naturale N şi K. Determinaţi numărul de şiruri de lungime N formate doar din semnele + şi – şi în care nu apar K semne – pe poziţii consecutive.

Date de intrare

Fișierul de intrare minusk.in conţine pe prima linie 2 numere naturale separate printr-un spaţiu, N şi K, cu semnificaţia din enunţ.

Date de ieșire

Fișierul de ieșire minusk.out va conține pe prima linie un singur număr natural reprezentând valoarea cerută, modulo 2011.

Restricții și precizări

• 1 ≤ K ≤ N ≤ 1000000;
• pentru 30% dintre teste N ≤ 10
• pentru 70% dintre teste N ≤ 1000

Exemplu

minusk.in

4 2

minusk.out

8

Explicație

Cele 8 şiruri sunt: ++++, +++-, ++-+, +-++, -+++, +-+-, -++-, -+-+. În niciunul dintre aceste şiruri nu avem două sau mai mult de două caractere – pe poziţii consecutive.

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

ifstream cin("minusk.in");
ofstream cout("minusk.out");

int n , k , m[1000001] , p[1000001];

int main()
{
    cin >> n >> k;
    p[0] = p[1] = m[1] = 1;
    for(int i = 2 ; i <= n ; i++)
    {
        p[i] = m[i] = (m[i - 1] + p[i - 1]) % 2011;
        if(i >= k)
        {
            if(m[i] > p[i - k]) m[i] = (m[i] - p[i - k]) % 2011;
            else m[i] = (m[i] + 2011 - p[i - k]) % 2011;
        }
    }
    cout << (m[n] + p[n]) % 2011;
    return 0;
}