Entanglement

entanglement

== include(page="template/taskheader" task_id="entanglement") ==

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.

Poveste şi cerinţă...

h2. Date de intrare

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.

Fişierul de intrare $entanglement.in$ ...

h2. Date de ieşire

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.

În fişierul de ieşire $entanglement.out$ ...

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 |_. 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})
|

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
...

== include(page="template/taskfooter" task_id="entanglement") ==