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==
<syntaxhighlight lang="python3" line="1">
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)
</syntaxhighlight>