2451 - Mexitate

Enunț

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ța

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

Date de intrare

Fișierul de intrare mexitatein.txt 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 de ieșire mexitateout.txt va conține un singur număr natural reprezentând produsul mex-urilor tuturor submatricelor având K linii și L coloane ale matricei modulo 1 000 000 007.

Restricții și precizări

• 1 ⩽ N * M ⩽ 400.000
• 1 ⩽ K ⩽ N
• 1 ⩽ L ⩽ M
• 1 ⩽ A[i][j] ⩽ N * M, 1 ⩽ i ⩽ N, 1 ⩽ J ⩽ M

Exemplul 1

Intrare

mexitatein.txt

3 4 2 3

1 2 3 2

2 3 1 4

1 1 2 6

Ieșire

Datele de intrare corespund restricțiilor impuse

mexitateout.txt

400

Explicație

N = 3, M = 4, K = 2 și L = 3
Submatricile cu două linii și trei coloane sunt:
1 2 3 cu mex-ul 4
2 3 1
2 3 2 cu mex-ul 5
3 1 4
2 3 1 cu mex-ul 4
1 1 2
3 1 4 cu mex-ul 5
1 2 6

Produsul tuturor mex-urilor este: 4 * 5 * 4 * 5 = 400
400 % 1 000 000 007 = 400

Exemplul 2

Intrare

mexitatein.txt

3 4 4 3

1 2 3 2

2 3 1 4

1 1 2 6

Ieșire

Datele de intrare NU corespund restricțiilor impuse

Rezolvare

#2451 - Mexitate

MOD = 1000000007


def validare_date(n, m, nr_linii, nr_coloane, matrice):
    if not (1 <= n * m <= 400000 and 1 <= nr_linii <= n and 1 <= nr_coloane <= m):
        return False
    for i in range(n):
        for j in range(m):
            if not (1 <= matrice[i][j] <= n * m):
                return False
    return True


def mex(n, m, nr_linii, nr_coloane, matrice):
    result = 1
    for i in range(n - nr_linii + 1):
        for j in range(m - nr_coloane + 1):
            submatrice = [linie[j:j+nr_coloane] for linie in matrice[i:i+nr_linii]]
            valori = set()
            for linie in submatrice:
                valori.update(linie)
            mex = 1
            while mex in valori:
                mex += 1
            result = (result * mex) % MOD
    return result


def main():
    with open("mexitatein.txt", "r") as fin:
        n, m, nr_linii, nr_coloane = map(int, fin.readline().split())
        matrice = [list(map(int, fin.readline().split())) for _ in range(n)]

    if validare_date(n, m, nr_linii, nr_coloane, matrice):
        print("Datele de intrare corespund restricțiilor impuse")
        result = mex(n, m, nr_linii, nr_coloane, matrice)
        with open("mexitateout.txt", "w") as fout:
            fout.write(str(result))
    else:
        print("Datele de intrare NU corespund restricțiilor impuse")
        exit(0)


if __name__ == "__main__":
    main()