Editing 0730 - Minus K

==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.
==Rezolvare==
MOD = 2011

def numar_siruri(N, K):
    # Inițializăm matricea dp cu 0-uri
    dp = [[0] * 2 for _ in range(N + 1)]

    # Prima coloană este 1, pentru că există un singur șir de lungime 0, și anume șirul vid
    dp[0][0] = 1

    # Calculăm numărul de șiruri
    for i in range(1, N + 1):
        # Dacă adăugăm + în șirul anterior, nu adăugăm un semn - pe poziția i
        dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD
        # Dacă adăugăm - în șirul anterior, verificăm dacă am adăugat deja K semne - consecutive
        if i >= K:
            dp[i][1] = (dp[i - 1][0] - dp[i - K][1] + MOD) % MOD
        else:
            dp[i][1] = dp[i - 1][0]

    return (dp[N][0] + dp[N][1]) % MOD

if __name__ == "__main__":
    with open("minusk.in", "r") as f:
        N, K = map(int, f.readline().split())

    rezultat = numar_siruri(N, K)

    with open("minusk.out", "w") as g:
        g.write(str(rezultat) + "\n")
python minusk.py