== include(page="template/taskheader" task_id="entanglement") ==
Poveste şi cerinţă...
Fie două şiruri $A$ şi $B$ de lungimi $N$ şi $M$ cu numere naturale mai mici sau egale decât $K$. Un entanglement al celor două şiruri este o matrice $C$ de dimensiuni $N x M$ unde pentru toate perechile $(i,j)$ valoarea $C[i][j]$ este egală fie cu $A[i]$ fie cu $B[j]$.
Dându-se o matrice $C$, câte perechi de şiruri $(A,B)$ există pentru care $C$ este un entanglement al celor două şiruri?
h2. Cerinţă
Să se scrie un program care, pentru $N, M, K$ şi matricea $C$ cunoscute, determină:
* dacă matricea $C$ poate fi un entanglement a două şiruri;
* numărul de perechi de şiruri $(A,B)$ pentru care matricea $C$ reprezintă un entanglement.
h2. Date de intrare
Fişierul de intrare $entanglement.in$ ...
Fişierul de intrare $entanglement.in$ conţine pe prima linie numerele $T, N, M$ şi $K$, iar pe următoarele $N$ linii câte $M$ numere naturale reprezentând elementele din matricea $C$.
Dacă $T=1$ atunci se va stabili dacă matricea $C$ poate fi un entanglement, iar dacă $T=2$ atunci se va determina numărul de perechi de şiruri $(A,B)$ pentru care $C$ reprezintă un entanglement.
h2. Date de ieşire
În fişierul de ieşire $entanglement.out$ ...
Dacă $T=1$ fişierul de ieşire $entanglement.out$ va conţine cuvântul $“DA”$ dacă $C$ poate fi un entanglement sau cuvântul $“NU”$ în caz contrar.
Dacă $T=2$ fişierul de ieşire $entanglement.out$ va conţine un singur număr reprezentând restul $modulo 1000000007$ al numărului de perechi de şiruri pentru care matricea C reprezintă un entanglement.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N, M ≤ 300$
* $1 ≤ K ≤ N * M$
* Pentru teste în valoare de $32$ de puncte $T = 1$.
* Pentru teste în valoare de $32$ de puncte $T = 2$ şi $N, M <= 60$.
* Pentru restul testelor, în valoare de $36$ de puncte, $T = 2$.
h2. Exemplu
table(example). |_. entanglement.in |_. entanglement.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
table(example). |_. entanglement.in |_. entanglement.out |_. Explicatie |
| 1 2 2 2
1 1
1 2
| DA
| O posibilă soluţie este A = {1, 1} şi B = {1, 2}.
|
|2 2 2 2
1 1
1 2
|5
|Cele 5 soluţii sunt:
(A = {1, 1}, B = {1, 2})
(A = {1, 1}, B = {2, 2})
(A = {1, 2}, B = {1, 1})
(A = {2, 2}, B = {1, 1})
(A = {1, 2}, B = {1, 2})
|
...
== include(page="template/taskfooter" task_id="entanglement") ==
