El principio de inclusión-exclusión es una técnica combinatoria esencial para calcular el tamaño de la unión de conjuntos mediante intersecciones. A continuación, se analizan dos problemas aplicados con soluciones en código.

Problema de Codeforces 803F

El objetivo es encontrar el número de secuencias donde el máximo común divisor (MCD) de todos los elementos es 1. Para un valor específico i, las secuencias con MCD igual a i se determinan mediante la fórmula \(dp[i] = 2^k - 1 - \sum dp[j]\), donde k es la cantidad de múltiplos de i en la secuencia, y j representa los múltiplos de i mayores que i. El cálculo se realiza de manera descendente desde el valor máximo.

#include <bits>
#define ll long long
using namespace std;
const int MAXN = 1e6 + 10, MOD = 1e9 + 7;
int frecuencia[MAXN];

ll potencia_modular(ll base, ll exponente) {
    ll resultado = 1;
    while (exponente) {
        if (exponente & 1) resultado = resultado * base % MOD;
        exponente >>= 1;
        base = base * base % MOD;
    }
    return resultado;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, valor_max = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        frecuencia[num]++;
        valor_max = max(valor_max, num);
    }
    vector<ll> dp(valor_max + 1, 0);
    for (int i = valor_max; i >= 1; i--) {
        ll cuenta = 0, resta = 0;
        for (int j = i; j <= valor_max; j += i) {
            cuenta += frecuencia[j];
            resta = (resta + dp[j]) % MOD;
        }
        dp[i] = (potencia_modular(2, cuenta) - 1 - resta + MOD) % MOD;
    }
    cout << dp[1] << endl;
    return 0;
}
</ll></bits>

Problema de Luogu P1450

Este ejercicio implica calcular el número de formas de alcanzar una suma obejtivo con denominaciones de monedas fijas y cantidades limitadas. Se aplica el principio de inclusión-exclusión para corregir las combinaciones que exceden las restricciones. Inicialmente, se usa programación dinámica para calcular el total sin límites, y luego se ajustan las cuentas restando las formas inválidas.

#include <bits>
#define ll long long
using namespace std;
const int SUMA_MAX = 1e6 + 10, MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    vector<int> denominaciones(5);
    for (int i = 1; i <= 4; i++) cin >> denominaciones[i];
    int consultas;
    cin >> consultas;
    vector<ll> formas(SUMA_MAX, 0);
    formas[0] = 1;
    for (int i = 1; i <= 4; i++) {
        for (int j = denominaciones[i]; j < SUMA_MAX; j++) {
            formas[j] = (formas[j] + formas[j - denominaciones[i]]) % MOD;
        }
    }
    while (consultas--) {
        vector<int> limites(5);
        for (int i = 1; i <= 4; i++) cin >> limites[i];
        int objetivo;
        cin >> objetivo;
        ll resultado = formas[objetivo];
        for (int mascara = 1; mascara < (1 << 4); mascara++) {
            int restante = objetivo;
            int signo = -1;
            for (int i = 1; i <= 4; i++) {
                if (mascara & (1 << (i - 1))) {
                    restante -= (limites[i] + 1) * denominaciones[i];
                    signo = -signo;
                }
            }
            if (restante >= 0) {
                resultado = (resultado - signo * formas[restante] + MOD) % MOD;
            }
        }
        cout << resultado << '\n';
    }
    return 0;
}
</int></ll></int></bits>