Skip to Content
CTRL K

Grid Completion

Explicación

Este problema nos pide contar el número de formas válidas de completar la grilla respetando las restricciones impuestas por los caracteres A y B.

Cada fila puede contener:

  • Ninguna celda marcada,
  • Solo una A,
  • Solo una B,
  • O ambas.

De forma similar, cada columna puede o no contener ya una A o una B.

El objetivo es contar el número de permutaciones válidas de columnas asignadas a filas tales que:

  • Se satisfacen todas las restricciones de A,
  • Se satisfacen todas las restricciones de B,
  • Y no ocurren conflictos.

Observación clave

Un enfoque de conteo directo es difícil porque las restricciones interactúan entre filas y columnas.

En lugar de contar solo permutaciones válidas:

  1. Contamos permutaciones bajo condiciones relajadas,
  2. Restamos configuraciones inválidas,
  3. Corregimos el sobreconteo usando el principio de inclusión-exclusión (PIE).

El sobreconteo ocurre cuando hay una violación.

¿Qué es una violación?

En nuestra construcción, a cada fila se le asigna una columna para A y una columna para B.

Una violación ocurre si estas dos asignaciones coinciden — es decir, tanto A como B terminan en la misma celda de una fila. Tal configuración es inválida.

El principio de inclusión-exclusión cuenta configuraciones en las que se permite que ciertas filas violen esta condición, y luego corrige el sobreconteo usando signos alternados.

Definiciones de categorías

Sea:

  • C0: número de filas que no contienen ni A ni B
  • C1: número de filas que contienen una B en la columna c, donde la columna c no contiene A
  • C2: número de filas que contienen una A en la columna c, donde la columna c no contiene B
  • C3: número de columnas que no contienen ni A ni B
  • C4: número de columnas sin A
  • C5: número de columnas sin B

Estos valores resumen toda la flexibilidad disponible en la grilla.

Aplicar inclusión-exclusión

Iteramos sobre tres parámetros:

  • i: número de filas elegidas de C0
  • j: número elegidas de C1
  • k: número elegidas de C2

Para cada terna (i,j,k)(i, j, k):

  1. Elegir filas:

    • (C0i)\binom{C_0}{i}
    • (C1j)\binom{C_1}{j}
    • (C2k)\binom{C_2}{k}

  2. Elegir columnas coincidentes de las columnas libres:

    • (C3i)\binom{C_3}{i}

  3. Arreglar las columnas libres restantes:

    • (C4−i−j)!(C_4 - i - j)!
    • (C5−i−k)!(C_5 - i - k)!

  4. Emparejar las filas y columnas seleccionadas:

    • i!i!

  5. Aplicar el signo alternado:

(−1)i+j+k (-1)^{i + j + k}

Este signo es el corazón de inclusión-exclusión:

  • Sumar configuraciones con 0 violaciones,
  • Restar las que tienen 1 violación,
  • Volver a sumar las que tienen 2 violaciones,
  • Restar 3 violaciones,
  • Y así sucesivamente.

Fórmula final

La respuesta final es:

∑i,j,k(−1)i+j+k⋅(C0i)(C1j)(C2k)(C3i)⋅i!⋅(C4−i−j)!⋅(C5−i−k)! \sum_{i,j,k} (-1)^{i+j+k} \cdot \binom{C_0}{i} \binom{C_1}{j} \binom{C_2}{k} \binom{C_3}{i} \cdot i! \cdot (C_4-i-j)! \cdot (C_5-i-k)!

Esta fórmula cuenta todas las compleciones válidas mientras corrige el sobreconteo vía el principio de inclusión-exclusión.

Optimización adicional

La implementación directa evalúa todas las ternas (i, j, k), lo que da complejidad temporal O(N3)\mathcal{O}(N^3).

Para mejorar esto, fijamos un valor de i. Después de fijar i, la parte restante de la fórmula se vuelve:

∑j,k(−1)j+k⋅(C1j)(C2k)⋅(C4−i−j)!⋅(C5−i−k)! \sum_{j,k} (-1)^{j+k} \cdot \binom{C_1}{j} \binom{C_2}{k} \cdot (C_4 - i - j)! \cdot (C_5 - i - k)!

Ahora observemos:

  • Los términos de j dependen solo de j.
  • Los términos de k dependen solo de k.
  • No hay interacción entre j y k.

Así que la suma doble se factoriza en:

(∑j(−1)j(C1j)(C4−i−j)!)⋅(∑k(−1)k(C2k)(C5−i−k)!) \left( \sum_j (-1)^j \binom{C_1}{j} (C_4 - i - j)! \right) \cdot \left( \sum_k (-1)^k \binom{C_2}{k} (C_5 - i - k)! \right)

Cada una de estas se puede computar en O(N)\mathcal{O}(N).

Implementación

Complejidad temporal: O(N2)\mathcal{O}(N^2)

Complejidad espacial: O(N)\mathcal{O}(N)

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
const ll MOD = 1e9 + 7;
const int MAXN = 505;
 
ll fact[MAXN], invfact[MAXN];
 
// BeginCodeSnip{Binary Exponentiation}
ll binpow(ll a, ll b) {
	ll r = 1;
	while (b) {
		if (b & 1) r = r * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return r;
}
// EndCodeSnip
// BeginCodeSnip{Combination Formula}
ll nCr(int n, int r) {
	if (r < 0 || r > n) return 0;
	return fact[n] * invfact[r] % MOD * invfact[n - r] % MOD;
}
// EndCodeSnip
// BeginCodeSnip{Formula from Editorial}
ll formula(int C0, int C1, int C2, int C3, int C4, int C5) {
	ll ans = 0;
 
	for (int i = 0; i <= min(C0, C3); i++) {
 
		// Compute sum over j
		ll sumJ = 0;
		for (int j = 0; j <= C1; j++) {
			if (C4 - i - j < 0) continue;
 
			ll cur = nCr(C1, j) * fact[C4 - i - j] % MOD;
			if (j & 1) cur = (MOD - cur) % MOD;
 
			sumJ = (sumJ + cur) % MOD;
		}
 
		// Compute sum over k
		ll sumK = 0;
		for (int k = 0; k <= C2; k++) {
			if (C5 - i - k < 0) continue;
 
			ll cur = nCr(C2, k) * fact[C5 - i - k] % MOD;
			if (k & 1) cur = (MOD - cur) % MOD;
 
			sumK = (sumK + cur) % MOD;
		}
 
		ll cur = 1;
		cur = cur * nCr(C0, i) % MOD;
		cur = cur * nCr(C3, i) % MOD;
		cur = cur * fact[i] % MOD;
		cur = cur * sumJ % MOD;
		cur = cur * sumK % MOD;
 
		if (i & 1) cur = (MOD - cur) % MOD;
 
		ans = (ans + cur) % MOD;
	}
 
	return ans;
}
// EndCodeSnip
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int n;
	cin >> n;
 
	// BeginCodeSnip{Pre-Compute}
	fact[0] = 1;
	for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
 
	invfact[n] = binpow(fact[n], MOD - 2);
	for (int i = n; i > 0; i--) invfact[i - 1] = invfact[i] * i % MOD;
	// EndCodeSnip
 
	vector<int> p(n, -1), q(n, -1);
	vector<bool> inA(n, false), inB(n, false);
 
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < n; j++) {
			if (s[j] == 'A') {
				p[i] = j;
				inA[j] = true;
			}
			if (s[j] == 'B') {
				q[i] = j;
				inB[j] = true;
			}
		}
	}
 
	int C0 = 0, C1 = 0, C2 = 0, C3 = 0, C4 = 0, C5 = 0;
 
	for (int i = 0; i < n; i++) {
		if (p[i] == -1 && q[i] == -1) C0++;
		if (p[i] == -1 && q[i] != -1 && !inA[q[i]]) C1++;
		if (p[i] != -1 && q[i] == -1 && !inB[p[i]]) C2++;
	}
 
	for (int i = 0; i < n; i++) {
		if (!inA[i] && !inB[i]) C3++;
		if (!inA[i]) C4++;
		if (!inB[i]) C5++;
	}
 
	cout << formula(C0, C1, C2, C3, C4, C5) << "\n";
}
Fundamentos