Énoncé du problème

On dispose d'une grille rectangulaire de taille N par M. Des bombes sont placées sur K cellules distinctes (avec K ≤ 20). Le but est de déterminer le nombre total de sous-rectangles (définis par leurs coordonnnées supérieure gauche et inférieure droite) qui ne contiennent aucune bombe.

Approche par principe d'inclusion-exclusion

Le nombre total de sous-rectangles dans une grille de N×M est donné par la formule :

total = N*(N+1)/2 * M*(M+1)/2

On souhaite soustraire de ce total le nombre de sous-rectangles qui contiennent au moins une bombe. Pour cela, on utilise le principe d'inclusion-exclusion sur les ensembles de bombes.

Pour un sous-ensemble non vide de bombes, on calcule le rectangle minimal qui les contient toutes (en trouvant les coordonnées extrêmes). Le nombre de sous-rectangles qui contiennent au moins cet ensemble de bombes est égal au nombre de choix pour placer le coin supérieur gauche (limité par la bombe la plus en haut à gauche) et le coin inférieur droit (limité par la bombe la plus en bas à droite).

Soit pour un ensemble de bombes :

• minX = la plus petite coordonnée x parmi les bombes.
• minY = la plus petite coordonnée y.
• maxX = la plus grande coordonnée x.
• maxY = la plus grande coordonnée y.

Le nombre de sous-rectengles qui contiennent toutes ces bombes est :

rectangles_incluant_ensemble = minX * minY * (N - maxX + 1) * (M - maxY + 1)

Le principe d'inclusion-exclusion stipule que pour obtenir le nombre de sous-rectangles contenant au moins une bombe, on somme ces quantités pour tous les sous-ensembles non vides, en alternant les signes selon la parité de la taille de l'ensemble : on soustrait pour les ensembles de taille impaire, on ajoute pour les ensembles de taille paire.

Ainsi, le résultat final est :

résultat = total - Σ ( (-1)^(taille+1) * rectangles_incluant_ensemble )
         pour tout sous-ensemble non vide de bombes.

Implémentation efficace

Comme K ≤ 20, on peut énumérer les 2^K - 1 sous-ensembles non vides de bombes en utilisant un masque binaire (de 1 à (1<<k>). Pour chaque masque, on détermine les coordonnées extrêmes des bombes sélectionnées et on calcule la contribution au principe d'inclusion-exclusion.</k>

Exemple de code en C++

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

struct Point {
    long long x, y;
};

int main() {
    int nbTests;
    cin >> nbTests;
    while (nbTests--) {
        long long N, M;
        int K;
        cin >> N >> M >> K;

        Point bombes[25];
        for (int i = 0; i < K; i++) {
            cin >> bombes[i].x >> bombes[i].y;
        }

        long long total = N * (N + 1) / 2 * M * (M + 1) / 2;

        for (int masque = 1; masque < (1 << K); masque++) {
            long long xMin = LLONG_MAX, yMin = LLONG_MAX;
            long long xMax = 0, yMax = 0;
            int bits = 0;

            for (int j = 0; j < K; j++) {
                if (masque & (1 << j)) {
                    bits++;
                    xMin = min(xMin, bombes[j].x);
                    yMin = min(yMin, bombes[j].y);
                    xMax = max(xMax, bombes[j].x);
                    yMax = max(yMax, bombes[j].y);
                }
            }

            long long combinaisons = xMin * yMin * (N - xMax + 1) * (M - yMax + 1);
            if (bits % 2 == 1) {
                total -= combinaisons;
            } else {
                total += combinaisons;
            }
        }

        cout << total << "\n";
    }
    return 0;
}

Complexité et contraintes

• Complexité : O(T * 2^K * K), ce qui est faisable car K ≤ 20.
• Les valeurs de N et M peuvent aller jusqu'à 10⁴, les calculs intermédiaires doivent utiliser des entiers 64-bit (long long).