Fişierul intrare/ieşire:mexitate.in, mexitate.outSursăONI 2018, clasa a 9-a, ziua 1
AutorEugenie Daniel PosdarascuAdăugată deoldatlantianSerban Cercelescu oldatlantian
Timp execuţie pe test2.5 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/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.inmexitate.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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?