# PBinfo #3990 – dinamica06 – Rezolvare C++

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

## Enunț

Cerința
Se dă un număr natural nenul n. Să se determine numărul de numere de n cifre din mulțimea {1, 2, 3, 4} care nu au două cifre alăturate egale și care au proprietatea că sunt divizibile cu 2. Pentru că acest număr poate fi foarte mare, se va calcula modulo 123457.

Date de intrare
Programul citește de la tastatură numărul n,.

Date de ieșire
Programul va afișa pe ecran numărul cerut, modulo 123457.

Restricții și precizări

Pentru 80 de puncte, 1 ≤ n ≤ 10.000
Pentru alte 20 de puncte, 100.000.000 ≤ n ≤ 1.000.000.000

Exemplu:
Intrare

2
Ieșire

6
Explicație
Numerele sunt 12, 14, 24, 32, 34, 42.

## Cod sursă C++

```cpp
#include <iostream>
#define MOD 123457
using namespace std;
int dp[5][10002], n;
int main()
{
    int i, c;
    cin >> n;
    for (c = 1; c <= 4; c++)
        dp[c][1] = 1;
    for (i = 2; i <= n; i++)
    {
        for (c = 1; c <= 4; c++)
          dp[c][i] = (dp[1][i-1]+dp[2][i-1]+dp[3][i-1]+dp[4][i-1]-dp[c][i-1]) % MOD;
    }
    cout << (dp[2][n] + dp[4][n]) % MOD;
    return 0;
}
```

## Resurse

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