== include(page="template/taskheader" task_id="mexitate") ==
Poveste şi cerinţă...
Se dă o matrice $A$ cu $N$ linii şi $M$ coloane cu elemente numere naturale nu neapărat distincte. Pentru o submatrice definim mex-ul acesteia ca fiind cea mai mică valoare naturală nenulă care nu apare în aceasta.
h2. Cerinţă
Să se calculeze produsul $mex$-urilor tuturor submatricelor având $K$ linii şi $L$ coloane ale matricei $A$.
h2. Date de intrare
Fişierul de intrare $mexitate.in$ ...
Fişierul $mexitate.in$ conţine pe prima linie patru numere naturale $N, M, K$ şi $L$ separate printr-un spaţiu cu semnificaţia din enunţ. Pe fiecare dintre următoarele $N$ linii se află câte $M$ numere naturale nenule, despărţite prin câte un spaţiu, reprezentând valorile matricei.
h2. Date de ieşire
În fişierul de ieşire $mexitate.out$ ...
Fişierul $mexitate.out$ va conţineun singur număr natural reprezentând produsul $mex$-urilor tuturor submatricelor având $K$ linii şi $L$ coloane ale matricei modulo $1000000007$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N*M ≤ 400000$
* $1 ≤ K ≤ N$
* $1 ≤ L ≤ M$
* $1 ≤ A[i][j] ≤ N*M$
* $Pentru 20% din punctajul total există teste cu 1 ≤ N, M ≤ 50$
* $Pentru alte 20% din punctajul total există teste cu 1 ≤ N, M ≤ 630$
h2. Exemplu
table(example). |_. mexitate.in |_. mexitate.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 4 2 3
1 2 3 2
2 3 1 4
1 1 2 6
| 400
|
h3. Explicaţie
...
$N = 3$ şi $M = 4$
$K = 2$ şi $L = 3$
Submatricile cu $2$ linii şi $3$ coloane sunt:
$1 2 3$
$2 3 1$
cu mex-ul $4$
$2 3 2$
$3 1 4$
cu mex-ul $5$
$2 3 1$
$1 1 2$
cu mex-ul $4$
$3 1 4$
$1 2 6$
cu mex-ul $5$
Produsul tuturor mex-urilor este: $4*5*4*5 = 400; 400 % 1000000007 = 400$
== include(page="template/taskfooter" task_id="mexitate") ==
