# PBinfo #3661 – dinamica05 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Cerința
Se dau numerele naturale n și p. Să se determine:
a) numărul cuvintelor de lungime n formate doar din litere mari și mici și cu proprietatea că aceste cuvinte nu pot avea două litere alăturate identice, indiferent că sunt mari sau mici (cuvintele baArda sau fEEric au două litere alăturate identice).
b) numărul cuvintelor de lungime n formate doar din litere mari și mici și cu proprietatea că nu pot apărea două litere mari pe poziții alăturate.
c) numărul cuvintelor de lungime n formate doar din litere mici și cu proprietatea că au cel mult p vocale (vocalele fiind: a, e, i, o, u)

Date de intrare
Programul citește de la tastatură numerele n și p.

Date de ieșire
Programul va afișa pe ecran trei numere: X, Y și Z, separate prin spațiu, care vor reprezenta răspunsurile la cele trei cerințe. Pentru că aceste numere pot fi foarte mari, se vor determina modulo 123457

Restricții și precizări

1 ≤ p < n ≤ 1.000

Exemplu:
Intrare

2 1
Ieșire

2600 2028 651

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
#define MOD 123457
using namespace std;
int a[1003], n, p;
int A[1003];
int dp[1003][1003];
int main()
{
    int i, j, x;
    cin >> n >> p;
    /// a. dp[1]=52, dp[i] = 50 * dp[i - 1], i=2..n
    /// deci numarul este 52 * 50^(n-1)
    x = 52;
    for (i = 2; i <= n; i++)
        x = 50 * x % MOD;
    cout << x << " ";
    /** b.
    a[i] = numarul cuvintelor de lungime i care se termina cu litera mica
    A[i] = numarul cuvintelor de lungime i care se termina cu litera mare
    a[1] = A[1] = 26
    a[i] = 26 * (a[i-1] + A[i-1])
    A[i] = 26 * a[i-1]
    solutia este a[n] + A[n]
    */
    a[1] = A[1] = 26;
    for (i = 2; i <= n; i++)
    {
        a[i] = 26 * (a[i-1] + A[i-1]) % MOD;
        A[i] = 26 * a[i-1] % MOD;
    }
    x = (a[n] + A[n]) % MOD;
    cout << x << " ";
    /// c.
    dp[1][1] = 5;
    x = 21;
    for (i = 1; i <= n; i++)
    {
        dp[i][0] = x;
        x = x * 21 % MOD;
    }
    for (i = 2; i <= n; i++)
        for (j = 1; j <= i; j++)
            dp[i][j] = (21 * dp[i-1][j] + 5 * dp[i-1][j-1]) % MOD;
    x = 0;
    for (i = 0; i <= p; i++)
        x = (x + dp[n][i]) % MOD;
    cout << x << "\n";
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3661)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3661/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3661/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)