The Inclusion-Exclusion Principle

The Inclusion-Exclusion Principle is a fundamental concept in combinatorics that provides a method for calculating the size of the union of multiple sets. It addresses the problem of avoiding overcounting elements that belong to multiple sets by systematically accounting for intersections.

Codeforces 547C: Mike and Foam

Problem Statement: We have a sequence of numbers and need to process a series of operations. Each operation toggles the presence of a number in our collection. After each operation, we need to determine how many pairs of selected numbers are coprime (their greatest common divisor is 1).

Approach: Since all numbers are less than or equal to 10^5 and the product of the first 7 primes exceeds this limit, each number can have at most 6 distinct prime factors. We can leverage this property to apply the Inclusion-Exclusion Principle.

For each number in our collection, we'll maintain a frequency array that counts how many selected numbers are multiples of each possible divisor. When toggling a number, we'll update this frequency array by considering all combinations of its prime factors.

To find the count of numbers coprime with a given number x, we calculate the count of numbers NOT sharing any prime factors with x using the principle:

Δanswer = cnt[1] - Σcnt[p_i] + Σcnt[p_i*p_j] - Σcnt[p_i*p_j*p_k] + ...

Where p_i are the prime factors of x.

#include 
using namespace std;
const int MAX_VAL = 500010;
const int MAX_N = 200010;
typedef long long ll;

vector<int> primeFactors[MAX_VAL];
ll frequency[MAX_VAL];
bool selected[MAX_N];
ll totalPairs;
int n, q;

void initializePrimeFactors() {
    for (int i = 2; i < MAX_VAL; i++) {
        if (primeFactors[i].empty()) {
            for (int j = i; j < MAX_VAL; j += i) {
                primeFactors[j].push_back(i);
            }
        }
    }
}

void updateNumber(int num, int delta) {
    int factorCount = primeFactors[num].size();
    for (int mask = 1; mask < (1 << factorCount); mask++) {
        int product = 1;
        for (int j = 0; j < factorCount; j++) {
            if (mask & (1 << j)) {
                product *= primeFactors[num][j];
            }
        }
        frequency[product] += delta;
    }
}

ll calculateCoprimePairs(int num) {
    ll result = 0;
    int factorCount = primeFactors[num].size();
    for (int mask = 1; mask < (1 << factorCount); mask++) {
        int sign = -1;
        int product = 1;
        for (int j = 0; j < factorCount; j++) {
            if (mask & (1 << j)) {
                product *= primeFactors[num][j];
                sign *= -1;
            }
        }
        result += sign * frequency[product];
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    initializePrimeFactors();
    
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> primeFactors[0][i];
    }
    
    while (q--) {
        int index;
        cin >> index;
        
        if (!selected[index]) {
            selected[index] = true;
            ll coprimeCount = calculateCoprimePairs(primeFactors[0][index]);
            totalPairs += (frequency[1] - coprimeCount);
            updateNumber(primeFactors[0][index], 1);
        } else {
            selected[index] = false;
            updateNumber(primeFactors[0][index], -1);
            ll coprimeCount = calculateCoprimePairs(primeFactors[0][index]);
            totalPairs -= (frequency[1] - coprimeCount);
        }
        
        cout << totalPairs << '\n';
    }
    
    return 0;
}

Codeforces 449D: Jzzhu and Numbers

Problem Statement: Given a sequence of numbers, we need to count the number of ways to select a subset such that the bitwise AND of all selected numbers equals zero.

Approach: Instead of directly counting valid subsets, we'll use complementary counting with the Inclusion-Exclusion Principle. First, we'll count subsets that have a non-zero bitwise AND, then subtract this from the total possible subsets.

We'll use a technique called "high-dimensional prefix sums" to efficiently compute the frequency of numbers that have specific bits set. Then, applying the Inclusion-Exclusion Principle, we'll count subsets where the bitwise AND has at least one bit set.

The final answer is calculated as:

answer = (2^(total numbers) - 1) - Σ[(-1)^(k+1) × 2^(count of numbers with bits in mask set)]

Where the sum is over all non-zero bit masks.

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

typedef long long ll;
const int MOD = 1000000007;
const int MAX_BITS = 20;
const int MAX_MASK = (1 << MAX_BITS);

ll countNumbers[MAX_MASK];
ll powerOfTwo[MAX_MASK];
ll result;

ll fastExponentiation(ll base, ll exponent) {
    ll result = 1;
    while (exponent > 0) {
        if (exponent & 1) {
            result = (result * base) % MOD;
        }
        base = (base * base) % MOD;
        exponent >>= 1;
    }
    return result;
}

int countSetBits(int mask) {
    int bits = 0;
    while (mask) {
        if (mask & 1) bits++;
        mask >>= 1;
    }
    return bits;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    // Read input and count frequencies
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        countNumbers[num]++;
    }
    
    // Precompute powers of 2
    for (int i = 0; i < MAX_MASK; i++) {
        powerOfTwo[i] = fastExponentiation(2, countNumbers[i]);
    }
    
    // High-dimensional prefix sum
    for (int bit = 0; bit < MAX_BITS; bit++) {
        for (int mask = MAX_MASK - 1; mask >= 0; mask--) {
            if (!(mask >> bit) & 1) {
                countNumbers[mask] = (countNumbers[mask] + countNumbers[mask | (1 << bit)]) % MOD;
                powerOfTwo[mask] = (powerOfTwo[mask] + powerOfTwo[mask | (1 << bit)]) % MOD;
            }
        }
    }
    
    // Apply inclusion-exclusion principle
    for (int mask = 1; mask < MAX_MASK; mask++) {
        ll sign = (countSetBits(mask) % 2 == 1) ? 1 : -1;
        result = (result + sign * (powerOfTwo[mask] - 1)) % MOD;
    }
    
    // Calculate total subsets and subtract invalid ones
    ll totalSubsets = (fastExponentiation(2, n) - 1 + MOD) % MOD;
    result = (totalSubsets - result + MOD) % MOD;
    
    cout << result << endl;
    
    return 0;
}