mexitate

Mexitate

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

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.

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.

Să se calculeze produsul $mex$-urilor tuturor submatricelor având $K$ linii şi $L$ coloane ale matricei $A$.

h2. Date de intrare

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.

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

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.

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 ≤ 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 totalexistăteste cu 1 ≤ N, M ≤ 630$

* $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

$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 = 400400 % 1000000007 = 400

Produsul tuturor mex-urilor este: $4*5*4*5 = 400; 400 % 1000000007 = 400$

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