Editing 2260 - Dinamica 02

Se consideră un număr natural nenul N.

==Cerința==
Să se determine numărul de cuvinte de lungime N formate doar din litere mici și cu proprietatea că nu pot exista trei litere alăturate identice. Pentru că acest număr poate fi foarte mare, se va determina modulo 777013.

==Date de intrare==
Programul citește de la tastatură numărul N.

==Date de ieșire==
Programul va afișa pe ecran numărul de cuvinte modulo 777013.

==Restricții și precizări==
1 ≤ N ≤ 1 000 000
Cuvintele baaad și deeeeef au trei litere alăturate egale, pe când abbaa și xxyyxx nu au.
==Exemplu==:
Intrare

2
Ieșire

676

==Rezolvare==
MOD = 777013

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

    # Pentru un singur caracter, avem 26 opțiuni (literele mici de la 'a' la 'z')
    dp[1][0] = 26
    dp[1][1] = 0

    # Calculăm numărul de cuvinte pentru N caractere
    for i in range(2, N + 1):
        dp[i][0] = (dp[i - 1][0] * 25 + dp[i - 1][1]) % MOD
        dp[i][1] = dp[i - 1][0]

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

if __name__ == "__main__":
    N = int(input("Introduceți N: "))
    
    rezultat = numar_cuvinte(N)
    
    print(rezultat)
python numar_cuvinte.py