La Programación Dinámica con Máscaras de Bits (State Compression DP) es una técnica avanzada que permite resolver problemas donde el estado puede representarse como un conjunto de elementos booleanos. Se utiliza frecuentemente cuando el tamaño de la entrada es pequeño (típicamente $N \le 20$), permitiendo que un entero actúe como un conjunto mediante su representación binaria.

Concepto Fundamental: El Problema del Emparejamiento

Imagina que tenemos $N$ personas del grupo A y $N$ personas del grupo B. Queremos formar parejas siguiendo ciertas restricciones de afinidad. Una búsqueda exhaustiva (fuerza bruta) tendría una complejidad de $O(N!)$, lo cual es inviable para $N=20$.

Podemos definir un estado dp(i, mask), donde i es el índice de la persona actual del grupo A y mask es un entero cuyos bits indican qué personas del grupo B ya han sido asignadas. La transición ocurre cuando intentamos emparejar a la persona i con cualquier persona j del grupo B que no esté en la máscara (bit j en 0) y que cumpla la afinidad.

Variación 1: De Factibilidad a Optimización

En problemas como la programación de tareas o visualización de contenido limitado, a veces el objetivo no es solo saber si es posible, sino maximizar el alcance con un conjunto dado.

Consideremos un escenario donde debemos cubrir un tiempo $L$ usando una selección de $N$ películas. Cada película tiene múltiples horarios de inicio. En lugar de verificar si un conjunto de películas cubre $L$, definimos dp[mask] como el tiempo máximo continuo que podemos cubrir desde el inicio usando exactamente el conjunto de películas representado por mask. Si para alguna máscara dp[mask] \ge L, habremos encontrado una solución válida.

Variación 2: Minimización de Recursos (Bin Packing)

Si tenemos objetos con pesos $W_i$ y contenedores con capacidad fija $C$, ¿cuál es el mínimo de contenedores necesarios?

Una aproximaicón ingenua podría llevarnos a una complejidad de $O(3^N)$ al iterar sobre subconjuntos. Sin embargo, podemos optimizarlo a $O(N 2^N)$ manteniendo un estado que almacene un par de valores: (cantidad_de_contenedores, espacio_usado_en_el_ultimo). Al procesar un nuevo objeto para una máscara dada, decidimos si cabe en el último contenedor o si necesitamos abrir uno nuevo.

Variación 3: DP por Filas en Rejillas

En una cuadrícula de $N \times M$, supongamos que queremos contar las configuraciones donde no hay dos celdas adyacentes con valor "1". Las celdas pueden tener valores fijos o ser comodines.

Definimos dp[fila][mask] como el número de formas de completar la cuadrícula hasta la fila actual, donde mask representa la configuración de la fila fila. La transición valida que la mask actual sea compatible internamente (sin bits adyacentes) y compatible con la mask de la fila anterior.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

long long modular_pow(long long base, long long exp) {
    long long res = 1;
    base %= 998244353;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % 998244353;
        base = (base * base) % 998244353;
        exp /= 2;
    }
    return res;
}

long long modInverse(long long n) {
    return modular_pow(n, 998244353 - 2);
}

int main() {
    int rows, cols;
    cin >> rows >> cols;
    vector<string> grid(rows);
    int wildcards = 0;
    for (int i = 0; i < rows; ++i) {
        cin >> grid[i];
        for (char c : grid[i]) if (c == '?') wildcards++;
    }

    vector<vector<int>> memo(rows + 1, vector<int>(1 << cols, 0));
    vector<vector<bool>> valid_mask(rows + 1, vector<bool>(1 << cols, false));

    for (int r = 1; r <= rows; ++r) {
        for (int m = 0; m < (1 << cols); ++m) {
            bool ok = true;
            if (m & (m >> 1)) ok = false;
            for (int j = 0; j < cols; ++j) {
                if (((m >> j) & 1) && grid[r - 1][j] == '0') ok = false;
                if (!((m >> j) & 1) && grid[r - 1][j] == '1') ok = false;
            }
            valid_mask[r][m] = ok;
        }
    }

    memo[0][0] = 1;
    for (int r = 1; r <= rows; ++r) {
        for (int m = 0; m < (1 << cols); ++m) {
            if (!valid_mask[r][m]) continue;
            int complement = ((1 << cols) - 1) ^ m;
            for (int prev_m = complement; ; prev_m = (prev_m - 1) & complement) {
                if (r == 1) {
                    if (prev_m == 0) memo[r][m] = (memo[r][m] + memo[r - 1][0]) % 998244353;
                } else if (valid_mask[r - 1][prev_m]) {
                    memo[r][m] = (memo[r][m] + memo[r - 1][prev_m]) % 998244353;
                }
                if (prev_m == 0) break;
            }
        }
    }

    long long total_ways = 0;
    for (int m = 0; m < (1 << cols); ++m) {
        total_ways = (total_ways + memo[rows][m]) % 998244353;
    }

    long long prob = (total_ways * modInverse(modular_pow(2, wildcards))) % 998244353;
    cout << prob << endl;

    return 0;
}

Variación 4: Máscaras Desplazadas (Ventana Corrediza)

Cuando las restricciones entre elementos dependen de una distancia corta $K$, no necesitamos comprimir todo el estado global, sino solo una "ventana" de tamaño $K$.

Por ejemplo, si queremos emparejar jugadores en una fila tales que sus índices $|i - j| \le K$ y sus fuerzas sean coprimas, podemos procesar los jugadores de uno en uno. La máscara representará el estado de disponibilidad de los últimos $K$ jugadores respecto a la posición actual.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int calcular_mcd(int a, int b) {
    while (b) { a %= b; swap(a, b); }
    return a;
}

int main() {
    int total_n, dist_k;
    cin >> total_n >> dist_k;
    vector<int> fuerza(total_n + 1);
    for (int i = 1; i <= total_n; ++i) cin >> fuerza[i];

    vector<vector<int>> dp_table(total_n + 2, vector<int>(1 << dist_k, 0));

    for (int i = 1; i <= total_n; ++i) {
        for (int m = 0; m < (1 << min(i, dist_k)); ++m) {
            int next_m = (m << 1) & ((1 << dist_k) - 1);
            // Opción 1: No emparejar al jugador i+1
            dp_table[i + 1][next_m] = max(dp_table[i + 1][next_m], dp_table[i][m]);

            // Opción 2: Intentar emparejar i+1 con alguien en la ventana K
            for (int d = 1; d <= min(i, dist_k); ++d) {
                if (!((m >> (d - 1)) & 1) && calcular_mcd(fuerza[i + 1], fuerza[i - d + 1]) == 1) {
                    int mask_with_pair = (next_m | (1 << d) | 1) & ((1 << dist_k) - 1);
                    dp_table[i + 1][mask_with_pair] = max(dp_table[i + 1][mask_with_pair], dp_table[i][m] + 1);
                }
            }
        }
    }

    int resultado = 0;
    for (int m = 0; m < (1 << min(total_n, dist_k)); ++m) {
        resultado = max(resultado, dp_table[total_n][m]);
    }
    cout << resultado << endl;
    return 0;
}