NeFut Logo NeFut
中 Admin Login

In-Depth Understanding of the Inclusion-Exclusion Principle and Its Application in Algorithms

Published at: 2026-05-27 09:17 Last updated: 2026-06-10 09:20
#algorithm #Math #Combinatorics

Core Logic and Mathematical Principles

The Inclusion-Exclusion Principle is a core tool in combinatorial mathematics for handling the size of unions of non-mutually exclusive sets. The central idea is: when calculating the size of the union of multiple overlapping sets, we first add the sizes of all sets without any reservations, and then alternately add and subtract the sizes of the intersections of overlapping parts to accurately correct the contributions of elements that were counted multiple times.

Mathematical Formula Derivation

Let $A_1, A_2, \dots, A_n$ be finite sets, the formula for the size of their union is:

$$\left| \bigcup_{i=1}^n A_i \right| = \sum_{i=1}^n |A_i| - \sum_{1 \le i < j \le n} |A_i \cap A_j| + \sum_{1 \le i < j < k \le n} |A_i \cap A_j \cap A_k| - \dots + (-1)^{n-1} |A_1 \cap A_2 \cap \dots \cap A_n|$$

This can be compactly expressed using symbols as:

$$\left| \bigcup_{i=1}^n A_i \right| = \sum_{S \subseteq \{1, 2, \dots, n\}, S \neq \emptyset} (-1)^{|S|-1} \left| \bigcap_{i \in S} A_i \right|$$

Proof Logic (Contribution Analysis): Assume that an element $x$ belongs exactly to $k$ sets ($1 \le k \le n$), the actual contribution count of this element in the left side union should be exactly $1$.

Count the number of times the right side formula counts this element:

The total contribution count of $x$ on the right side is:

$$\sum_{m=1}^k (-1)^{m-1} C_k^m$$

Using the binomial theorem, we know:

$$(1 - 1)^k = \sum_{m=0}^k (-1)^m C_k^m = C_k^0 + \sum_{m=1}^k (-1)^m C_k^m = 1 - \sum_{m=1}^k (-1)^{m-1} C_k^m$$

Since $(1 - 1)^k = 0$ (when $k \ge 1$), rearranging gives:

$$\sum_{m=1}^k (-1)^{m-1} C_k^m = 1$$

Any element included in at least one set has a net contribution weight of $1$ in the right side algebraic sum. The mathematical logic is perfectly coherent.

State Design and Algorithm Derivation

In cases where the number of sets $n$ is small (usually $n \le 20$), we can utilize the idea of state compression to compress the selection states of sets into a binary integer mask.

Binary State Design

The total size of the union is the algebraic sum of contributions from all mask states.

C++ Standard Source Code

#include <iostream>
#include <vector>

// Calculate greatest common divisor for least common multiple service
long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

// Calculate least common multiple, preventing overflow during multiplication
long long lcm(long long a, long long b) {
    if (a == 0 || b == 0) return 0;
    long long g = gcd(a, b);
    // Divide first then multiply, maximizing the capacity of long long
    return (a / g) * b; 
}

// Inclusion-Exclusion Principle Counting: Count the number of multiples of at least one number in primes array from 1 to N
long long count_multiples(long long N, const std::vector<long long> &primes) {
    int n = primes.size();
    long long total_union = 0;
    int max_states = 1 << n; // 2^n possible state combinations

    // Start looping from 1, skipping the empty set state 0000...
    for (int mask = 1; mask < max_states; ++mask) {
        int bits_count = 0;
        long long current_lcm = 1;
        bool overflow = false;

        for (int i = 0; i < n; ++i) {
            if ((mask >> i) & 1) { // Capture state bit
                bits_count++;
                current_lcm = lcm(current_lcm, primes[i]);
                // Defensive check: if current least common multiple exceeds N, its multiples in 1~N must be 0
                if (current_lcm > N || current_lcm <= 0) { 
                    overflow = true;
                    break;
                }
            }
        }

        if (overflow) continue; // Directly zero out the intersection size exceeding the upper limit, not counted

        long long count = N / current_lcm; // Calculate the size of the current intersection set

        // Odd add, even subtract core logic
        if (bits_count & 1) {
            total_union += count;
        } else {
            total_union -= count;
        }
    }

    return total_union;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    long long N;
    int n;
    if (std::cin >> N >> n) {
        std::vector<long long> primes(n);
        for (int i = 0; i < n; ++i) {
            std::cin >> primes[i];
        }
        std::cout << count_multiples(N, primes) << "\n";
    }
    return 0;
}

NOIP Practical Pitfall Guide

  1. Multiplication explosion during intersection leading to infinite loops or negative truncation When calculating the least common multiple of multiple numbers (as in the lcm multiplication in the above code), the product of multiple numbers can explode geometrically. Even using long long, it can easily overflow to a negative value after multiplying four or five non-prime numbers. If defensive checks for current_lcm > N are not performed, N / current_lcm could yield an incorrect large value, completely destroying the balance of addition and subtraction in inclusion-exclusion.
  2. Low-level mistakes in bitwise operation precedence When checking binary bits, many competitors mistakenly write if (mask >> i & 1 == 1). Note: In C++, the precedence of the bitwise shift operator >> and the bitwise AND operator & is lower than that of the equality operator ==. This code is equivalent to mask >> (i & (1 == 1)) from the compiler's perspective, distorting the logic. Strict parentheses must be used: if ((mask >> i) & 1).

Classic NOIP/Luogu Problems

1. Luogu P1450 [HAOI2008] Coin Shopping

2. Luogu P2567 [SCOI2010] Lucky Numbers

Original Source: local://20.1
[h] Back to Home
© 2026 Nefut. | About Us | Contact Us | Privacy Policy | RSS