== 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.
|
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})
|
h3. Explicaţie
