| Fişierul intrare/ieşire: | mexitate.in, mexitate.out | Sursă | ONI 2018, clasa a 9-a, ziua 1 |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Serban Cercelescu •oldatlantian |
| Timp execuţie pe test | 2.5 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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.
Cerinţă
Să se calculeze produsul mex-urilor tuturor submatricelor având K linii şi L coloane ale matricei A.
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.
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.
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
Exemplu
| mexitate.in | mexitate.out |
|---|---|
| 3 4 2 3 1 2 3 2 2 3 1 4 1 1 2 6 | 400 |
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
