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 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 de ieșire mexitate.out 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
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

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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema mexitate:

/* Eugenie Daniel Posdarascu
    100 de puncte
*/
#include<stdio.h>
#include<vector>
#include<stdlib.h>
#include<time.h>
using namespace std;

#define MOD 1000000007
#define NMAX 400005

int n, m, k, l, f[NMAX], fb[NMAX];
int bucket = 100, indexB[NMAX];
long long answer = 1;
long long ans = 0;
vector<int> matrix[NMAX], matrix2[NMAX];

void deleteElements(int a, int b, int c, int d) {
    for(int i = a; i <= c; i++)
        for(int j = b; j <= d; j++) {
            int value = matrix[i][j];
            f[value]--;
            if(!f[value])
                fb[indexB[value]]--;

        }
}

void addElements(int a, int b, int c, int d) {
    for(int i = a; i <= c; i++)
        for(int j = b; j <= d; j++) {
            int value = matrix[i][j];
            f[value]++;
            if(f[value] == 1)
                fb[indexB[value]]++;
        }
}

void query() {
    for(int buc = 1; ; buc++) {
        if(fb[buc] == bucket)
            continue;
        for(int i = (buc - 1) * bucket + 1; ; i++) {
            if(!f[i]) {
                answer *= i;
                ans += i;
                if(answer >= MOD)
                    answer %= MOD;
                break;
            }
        }
        break;
    }
}

void initializeaza() {
    addElements(1,1,k,l);
    query();
}

int main () {
    int value, sign;

    srand(time(0));
    freopen("mexitate.in","r",stdin);
    freopen("mexitate.out","w",stdout);

    scanf("%d%d%d%d",&n,&m,&k,&l);
    for(int i = 1; i <= n; i++) {
        matrix2[i].push_back(0);
        for(int j = 1; j <= m; j++) {
            scanf("%d",&value);
            matrix2[i].push_back(value);
        }
    }
    if(k > l) { // linia devine coloana // m linia 1 m - 1 2
        for(int i = 1; i <= m; i++)
            for(int j = 0; j <= n; j++)
                matrix[i].push_back(0);
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                matrix[m - j + 1][i] = matrix2[i][j];
        int aux = n;
        n = m;
        m = aux;

        aux = l;
        l = k;
        k = aux;
    }
    else {
        for(int i = 1; i <= n; i++) {
            matrix[i].push_back(0);
            for(int j = 1; j <= m; j++) {
                matrix[i].push_back(matrix2[i][j]);
            }
        }
    }

    int last = 1;
    for(int i = 1; i <= n * m; i++) {
        indexB[i] = last;
        if(i % bucket == 0)
            last++;
    }

    initializeaza();
    for(int i = 1; i <= n - k + 1; i++) {
        sign = ((i&1) ? +1 : -1);
        if(sign == 1) {
            for(int j = 2; j <= m - l + 1; j++) {
                deleteElements(i, j - 1, i + k - 1, j - 1);
                addElements(i, j + l - 1, i + k - 1, j + l - 1);
                query();
            }
            if(i <= n - k) {
                deleteElements(i, m - l + 1, i, m);
                addElements(i + k, m - l + 1, i + k, m);
                query();
            }
        }
        else {
            for(int j = m - l; j >= 1; j--) {
                deleteElements(i, j + l, i + k - 1, j + l);
                addElements(i, j, i + k - 1, j);
                query();
            }
            if(i <= n - k) {
                deleteElements(i, 1, i, l);
                addElements(i + k, 1, i + k, l);
                query();
            }
        }
    }

    printf("%lld\n", answer);

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2451 mexitate

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2451 mexitate de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2451 mexitate