Cálculo de Números Combinatorios

Los números combinatorois, denotados como C(n, k), se pueden calcular mediante diferentes algoritmos optimizados según las restricciones del problema.

1. Preprocesamiento por Recurrencia

Para valores de n hasta 2000, se puede usar una tabla de programación dinámica con complejidad O(n²). El código siguiente precalcula todos los C(i, j) para i y j hasta un límite.

#include <iostream>
#include <vector>
using namespace std;

const int LIMITE = 2001;
const int MODULO = 1e9 + 7;
vector<vector<int>> tabla_comb(LIMITE, vector<int>(LIMITE, 0));

void precalcular_combinaciones() {
    for (int fila = 0; fila < LIMITE; ++fila) {
        tabla_comb[fila][0] = 1;
        for (int col = 1; col <= fila; ++col) {
            tabla_comb[fila][col] = (tabla_comb[fila-1][col] + tabla_comb[fila-1][col-1]) % MODULO;
        }
    }
}

int main() {
    precalcular_combinaciones();
    int consultas;
    cin >> consultas;
    while (consultas--) {
        int n, k;
        cin >> n >> k;
        cout << tabla_comb[n][k] << endl;
    }
    return 0;
}

2. Preprocesamiento con Factoriales e Inversos

Para n hasta 10^5, se precalculan factoriales y sus inversos modulares usando exponenciación rápida. La fórmula es C(n, k) = fact[n] * inv_fact[k] * inv_fact[n-k] % MODULO.

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;
const int MAX_N = 100001;
const int MOD = 1e9 + 7;
vector<ll> fac(MAX_N, 1), inv_fac(MAX_N, 1);

ll exponenciar_mod(ll base, ll exp, ll mod) {
    ll resultado = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) resultado = (resultado * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return resultado;
}

void preprocesar_factoriales() {
    for (int i = 1; i < MAX_N; ++i) {
        fac[i] = (fac[i-1] * i) % MOD;
    }
    inv_fac[MAX_N-1] = exponenciar_mod(fac[MAX_N-1], MOD-2, MOD);
    for (int i = MAX_N-2; i >= 1; --i) {
        inv_fac[i] = (inv_fac[i+1] * (i+1)) % MOD;
    }
}

int main() {
    preprocesar_factoriales();
    int consultas;
    cin >> consultas;
    while (consultas--) {
        int n, k;
        cin >> n >> k;
        ll combinacion = (((fac[n] * inv_fac[k]) % MOD) * inv_fac[n-k]) % MOD;
        cout << combinacion << endl;
    }
    return 0;
}

3. Teorema de Lucas para Grandes Modulos

Cuando n y k son grandes (hasta 10^18) pero el módulo p es primo y pequeño (hasta 10^5), el teorema de Lucas descompone el prolbema en subproblemas menores usando la representación en base p.

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

ll exponenciar_rapida(ll base, ll exp, ll mod) {
    ll res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

ll comb_pequeño(ll n, ll k, ll p) {
    if (k > n) return 0;
    ll numerador = 1, denominador = 1;
    for (int i = 0; i < k; ++i) {
        numerador = (numerador * (n - i)) % p;
        denominador = (denominador * (i + 1)) % p;
    }
    return (numerador * exponenciar_rapida(denominador, p-2, p)) % p;
}

ll teorema_lucas(ll n, ll k, ll p) {
    if (k == 0) return 1;
    return (comb_pequeño(n % p, k % p, p) * teorema_lucas(n / p, k / p, p)) % p;
}

int main() {
    int consultas;
    cin >> consultas;
    while (consultas--) {
        ll n, k, p;
        cin >> n >> k >> p;
        cout << teorema_lucas(n, k, p) << endl;
    }
    return 0;
}

4. Inversos Modulares Lineales

Para calcular inversos modulares de 1 a n en O(n), se usa la recurrencia: inv[i] = MODULO - (MODULO / i) * inv[MODULO % i] % MODULO.

vector<int> inversos(MAX_N, 0);
inversos[1] = 1;
for (int i = 2; i < MAX_N; ++i) {
    inversos[i] = MODULO - (long long)(MODULO / i) * inversos[MODULO % i] % MODULO;
}

Principio de Inclusión-Exclusión

Este principio se utiliza para contar elementos que cumplen al menos una de varias condiciones. Sea U el conjunto universal y S_i el conjunto de elementos que cumplen la condición i. Entonces, el número de elementos en la unión de los S_i se calcula como:

|∪ S_i| = Σ |S_i| - Σ |S_i ∩ S_j| + Σ |S_i ∩ S_j ∩ S_k| - ... + (-1)^{m-1} |∩ S_i|

La implementación típica recorre todos los subconjuntos de condiciones, lo que lleva tiempo O(2^m).

Ejemplo: Conteo con Restricciones

Para calcular cuántos números hasta N son divisibles por al menos uno de un conjunto de primos, se aplica inclusión-exclusión sobre los subconjuntos de primos.

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

int main() {
    ll limite;
    int num_primos;
    cin >> limite >> num_primos;
    vector<ll> primos(num_primos);
    for (int i = 0; i < num_primos; ++i) {
        cin >> primos[i];
    }
    ll total = 0;
    for (int mascara = 1; mascara < (1 << num_primos); ++mascara) {
        ll producto = 1;
        int bits = 0;
        bool desbordamiento = false;
        for (int idx = 0; idx < num_primos; ++idx) {
            if (mascara & (1 << idx)) {
                ++bits;
                if (producto > limite / primos[idx]) {
                    desbordamiento = true;
                    break;
                }
                producto *= primos[idx];
            }
        }
        if (desbordamiento) continue;
        ll contribucion = limite / producto;
        if (bits % 2 == 1) {
            total += contribucion;
        } else {
            total -= contribucion;
        }
    }
    cout << total << endl;
    return 0;
}

Aplicación Combinada

Problemas como asignar objetos a personas con restricciones o colorear tableros con condiciones de filas, columnas y colores se resuelven combinando combinatoria e inclusión-exclusión.

Ejemplo: Asignación con Restricciones

Dado m tipos de productos y n personas, donde cada persona debe recibir al menos un producto de cada tipo, se usa la fórmula de combinación con barras y se ajusta con inclusión-exclusión para garantizarr que todas las personas reciban algo.

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;
const int MOD = 1e9 + 7;
const int MAX_VAL = 5001;

vector<ll> fac(MAX_VAL, 1), inv_fac(MAX_VAL, 1);

ll potencia_mod(ll base, ll exp) {
    ll resultado = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) resultado = (resultado * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return resultado;
}

void inicializar() {
    for (int i = 1; i < MAX_VAL; ++i) {
        fac[i] = (fac[i-1] * i) % MOD;
    }
    inv_fac[MAX_VAL-1] = potencia_mod(fac[MAX_VAL-1], MOD-2);
    for (int i = MAX_VAL-2; i >= 0; --i) {
        inv_fac[i] = (inv_fac[i+1] * (i+1)) % MOD;
    }
}

ll combinatoria(int n, int k) {
    if (k < 0 || k > n) return 0;
    return (((fac[n] * inv_fac[k]) % MOD) * inv_fac[n-k]) % MOD;
}

int main() {
    inicializar();
    int personas, tipos;
    cin >> personas >> tipos;
    vector<int> cantidades(tipos);
    for (int i = 0; i < tipos; ++i) {
        cin >> cantidades[i];
    }
    ll respuesta = 0;
    for (int mascara = 0; mascara <= personas; ++mascara) {
        ll signo = (mascara % 2 == 0) ? 1 : MOD-1;
        ll formas = 1;
        for (int j = 0; j < tipos; ++j) {
            int disponible = cantidades[j] + personas - mascara - 1;
            formas = (formas * combinatoria(disponible, personas - mascara - 1)) % MOD;
        }
        formas = (formas * combinatoria(personas, mascara)) % MOD;
        respuesta = (respuesta + signo * formas) % MOD;
    }
    cout << (respuesta + MOD) % MOD << endl;
    return 0;
}