Inclusion-Exclusion Principle

Quick Revisit

• USE WHEN: counting union of overlapping sets (coprime integers, derangements, bitmask enumeration)
• INVARIANT: |A∪B∪...| = Σ|singles| − Σ|pairs| + Σ|triples| − ... (alternating sign by subset size)
• TIME: O(2^k) for k sets; O(n·2^k) with bitmask enumeration | SPACE: O(2^k)
• CLASSIC BUG: wrong sign — subsets of even size are subtracted, odd size are added (not the reverse)
• PRACTICE: 08-ladder-mixed

AL-11 | The Inclusion-Exclusion Principle (PIE) for competitive programming: counting unions of overlapping sets, coprime integers, derangements, Euler's totient, and bitmask enumeration. Core technique behind Codeforces combinatorics and bitmasks tags at Div 2 C--E.

Difficulty: [Intermediate]Prerequisites: Combinatorics, Bit ManipulationCF Rating Range: 1500--1900

---

Contents

• Intuition
• C++ STL Reference
• Implementation (Contest-Ready)
• Operations Reference
• Problem Patterns & Tricks
• Contest Cheat Sheet
• Gotchas & Debugging
• Self-Test
• Further Reading

---

Intuition

Count the integers from 1 to 30 that are divisible by 2, 3, or 5.

Naive approach -- count multiples of each prime separately:

  Multiples of 2 in [1..30]:  2, 4, 6, ..., 30    -> 15
  Multiples of 3 in [1..30]:  3, 6, 9, ..., 30    -> 10
  Multiples of 5 in [1..30]:  5, 10, 15, ..., 30  ->  6
                                              Sum  =  31

But 31 > 30, so we clearly overcounted. The number 6 was counted by both the "div by 2" set and the "div by 3" set. The number 30 was counted three times -- once for each prime. Subtracting duplicates is not straightforward because pairs overlap with triples.

How do we count a union of overlapping sets without missing or double-counting anything?

"To count a union correctly, add singles, subtract pairs, add triples, subtract quads, ..."

Think of stacking transparent colored sheets on a table. Place a red sheet over region A, blue over B, green over C. Where two sheets overlap, the area is counted twice -- subtract once for each pair. But the center where all three overlap was added 3 times, then subtracted 3 times -- so add it back once for the triple.

For union counting, the sign alternates by intersection size: odd-sized intersections are added, even-sized intersections are subtracted. That is, singles add ($+$), pairs subtract ($-$), triples add ($+$), quads subtract ($-$), and so on. The sign of an intersection of $k$ sets is $(-1{)}^{k+1}$.

This breaks when the sets are not finite or when computing intersection sizes is as hard as the original problem. PIE works best when $|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}|$ has a simple closed form.

Visual Walkthrough

Three sets: $A$ = multiples of 2, $B$ = multiples of 3, $C$ = multiples of 5 in $[1..30]$.

         +---------------------+
         |          A          |
         |  (div 2)   +-------+-------+
         |   |A|=15   |       |       |
         |            | A&B   |       |
         +-------+----+ |A&B| |       |
                 |    |  =5   |  B    |
                 |    +--+----+ (div3)|
                 |  A&C  |A&B&C| |B|=10
                 ||A&C|=3| =1 |  |    |
         +-------+-------+----+--+    |
         |       |  B&C  |       |    |
         |   C   | |B&C|=2      +----+
         | (div5)|       |
         | |C|=6 +-------+
         |       |
         +-------+

Step 1: Add singles.

$|A|+|B|+|C|=15+10+6=31$

Step 2: Subtract pairs. Multiples of both 2 and 3 are multiples of 6. Similarly: lcm(2,5)=10, lcm(3,5)=15.

$|A\cap B|+|A\cap C|+|B\cap C|=\lfloor 30/6\rfloor +\lfloor 30/10\rfloor +\lfloor 30/15\rfloor =5+3+2=10$

Running total: $31-10=21$.

Step 3: Add triples. Multiples of 2, 3, and 5 are multiples of 30.

$|A\cap B\cap C|=\lfloor 30/30\rfloor =1$

Running total: $21+1=22$.

Verification: list integers in $[1..30]$ NOT divisible by 2, 3, or 5: $\{1,7,11,13,17,19,23,29\}$ -- that is 8 numbers. So integers divisible by 2, 3, or 5: $30-8=22$. Matches.

How each "bad" element cancels to exactly 0:

Consider element 6 (divisible by 2 and 3, but not 5). It lives in sets $A$ and $B$, so $|T|=2$. Trace its contribution through PIE:

  Element 6: violates {A, B}  (div by 2 and 3)
  ┌─────────────────────────────────────────────────────┐
  │  Step         Subsets containing 6     Contribution │
  │  ──────────── ────────────────────── ────────────── │
  │  +singles     {A}, {B}                    +1  +1    │
  │  -pairs       {A,B}                       -1        │
  │  +triples     (none, not in C)             0        │
  │                                        ──────────── │
  │  Net count of element 6:               +1 +1 -1 = 0 │ X cancelled
  │                                                      │
  │  Element 7: violates {}  (coprime to 2,3,5)          │
  │  Step         Subsets containing 7     Contribution  │
  │  ──────────── ────────────────────── ──────────────  │
  │  ∅ (baseline) always                      +1         │
  │  No other subsets contain 7.                         │
  │  Net count of element 7:                    1        │ OK kept
  └──────────────────────────────────────────────────────┘

  General rule:  Σ_{S ⊆ T} (-1)^|S|  =  { 1 if |T|=0
                                          { 0 if |T|>=1
  Every "bad" element (|T|>=1) sums to 0. Every "good" element stays at 1.

Now do an element that sits in all three sets — that is the case where the +singles / −pairs / +triples interaction really earns its keep:

  Element 30: violates {A, B, C}  (div by 2, 3, AND 5)
  ┌─────────────────────────────────────────────────────────────┐
  │  Step       Subsets containing 30          Contribution     │
  │  ────────── ───────────────────────────── ────────────────  │
  │  +singles   {A}, {B}, {C}                  +1 +1 +1   = +3  │
  │  -pairs     {A,B}, {A,C}, {B,C}            -1 -1 -1   = -3  │
  │  +triples   {A,B,C}                        +1         = +1  │
  │                                                  ─────────  │
  │  Net count of element 30:                   +3 -3 +1 =  +1  │ correctly counted once
  └─────────────────────────────────────────────────────────────┘

The pattern $+3-3+1=1$ is exactly the moment PIE clicks: for an element in all three sets, the singles count it three times (once per set), the pairs subtract those three over-counts, and the single triple adds the one remaining contribution. The same algebra works for any number of sets — the contribution of an element in $|T|$ sets is $\sum _{k=1}^{|T|}(-1{)}^{k+1}(\genfrac{}{}{0ex}{}{|T|}{k})=1$.

The Invariant

Inclusion-Exclusion Principle. For finite sets $A_1,A_2,\dots ,A_m$:

$|A_1\cup A_2\cup \cdots \cup A_m|={\displaystyle \sum _{k=1}^m(-1{)}^{k+1}\sum _{|S|=k}\left|\bigcap _{i\in S}{A}_i\right|}$

Equivalently, to count elements in NONE of the sets (the complement):

$|\overline{A_1}\cap \overline{A_2}\cap \cdots \cap \overline{A_m}|={\displaystyle \sum _{S\subseteq \{1..m\}}(-1{)}^{|S|}\left|\bigcap _{i\in S}{A}_i\right|}$

where the empty intersection $\bigcap _{i\in \mathrm{\varnothing }}{A}_i$ equals the universe $U$.

Why it works: Each element $x$ in the universe is counted $\sum _{S\subseteq T}(-1{)}^{|S|}$ times, where $T$ is the set of conditions $x$ violates. If $|T|\ge 1$, this sum equals 0 by the binomial theorem. If $|T|=0$ (element satisfies none of the "bad" conditions), the sum is 1.

When to Reach for This

Signal in problem statement	PIE variant
"count elements satisfying at least one of $m$ conditions"	Direct PIE over union
"count elements satisfying none of $m$ conditions"	Complement form of PIE
"count coprime pairs" or "coprime to $n$"	PIE over prime factors
"derangements" or "no fixed points"	PIE over positions
"onto / surjective functions"	PIE: subtract non-surjections
"Euler's totient $\phi (n)$"	PIE over prime factors of $n$
$m\le 20$ and "bitmask" in tags	Enumerate $2^m$ subsets

Beyond the basic formula

Identifying "bad properties" is 80% of the problem. The PIE formula is mechanical once you have the properties. The creative step is choosing which sets $A_1,\dots ,A_m$ to define. For coprime counting, they are "divisible by $p_i$." For derangements, "position $i$ is fixed." For surjections, "box $j$ is empty." If you cannot phrase your problem as "count objects violating none of $m$ properties," PIE does not apply.

When $f(S)$ depends only on $|S|$, the exponential loop collapses to linear. If every subset of size $k$ gives the same intersection size $g(k)$, then:

$\text{answer}=\sum _{k=0}^m(-1{)}^k(\genfrac{}{}{0ex}{}{m}{k})g(k)$

This replaces the $O(2^m)$ bitmask loop with an $O(m)$ summation over $k$. Derangements ($g(k)=(n-k)!$) and surjections ($g(k)=(m-k{)}^n$) both exploit this symmetry.

Connection to Möbius inversion. PIE on a set lattice is the special case of Möbius inversion on the Boolean lattice $2^{[m]}$. If your "constraint sets" form a poset richer than subsets (e.g., divisors of $n$), the same alternating-sign idea generalizes via the Möbius function $\mu$ of the poset. Understanding this connection unlocks problems tagged number_theory + combinatorics where PIE over prime divisors is really Möbius inversion on the divisor lattice.

2.7 What the Code Won't Teach You

The bitmask loop won't tell you how to define $f(S)$. The contest template iterates mask = 0..2^m-1 and accumulates sign * f(mask). But every problem requires a different definition of $f(\text{mask})$: floor division for coprime, factorial for derangements, exponentiation for surjections, binomial for stars-and-bars. The code is identical in structure -- the intellectual work is entirely in choosing $f$.

  THE REAL WORK vs. THE TEMPLATE:
  ┌──────────────────────────────────────────────────────┐
  │  TEMPLATE (same every time):                         │
  │    for mask in 0..2^m:                               │
  │        sign = (-1)^popcount(mask)                    │
  │        ans += sign * f(mask)                         │
  │                                                      │
  │  YOUR JOB (different every problem):                 │
  │    ┌──────────────┐  ┌──────────────┐                │
  │    │ What are the │  │ What is      │                │
  │    │ m "bad"      │──│ f(S) for a   │                │
  │    │ properties?  │  │ subset S?    │                │
  │    └──────────────┘  └──────────────┘                │
  │         ▼                   ▼                        │
  │    ┌─────────────────────────────────────┐           │
  │    │ Problem         Properties   f(S)   │           │
  │    │ ─────────────── ──────────── ────── │           │
  │    │ Coprime [1..n]  div by p_i   ⌊n/∏p⌋│           │
  │    │ Derangements    pos i fixed  (n-k)! │           │
  │    │ Surjections     box j empty  (m-k)^n│           │
  │    │ Stars+Bars      x_i > c_i   C(...)  │           │
  │    └─────────────────────────────────────┘           │
  └──────────────────────────────────────────────────────┘

The code won't show you when to use complement form vs. direct form. PIE has two forms: count the union $|A_1\cup \cdots \cup A_m|$ (direct), or count elements in none of the sets (complement). The complement form is more common because "count objects with no bad properties" is a more natural phrasing, and it starts with the total count as the $k=0$ term.

  DIRECT vs. COMPLEMENT:
  ┌───────────────────────────────────────────────┐
  │  DIRECT (count union):                        │
  │    |A₁ ∪ ... ∪ Aₘ| = Σ (-1)^(k+1) Σ |∩Aᵢ|  │
  │    k=1..m                                     │
  │    -> "How many integers divisible by 2,3,5?"  │
  │    -> Sum starts at k=1, sign starts positive  │
  │                                               │
  │  COMPLEMENT (count none):                     │
  │    |Ā₁ ∩ ... ∩ Āₘ| = Σ (-1)^k Σ |∩Aᵢ|       │
  │    k=0..m                                     │
  │    -> "How many integers coprime to 30?"       │
  │    -> Sum starts at k=0 (the +N term)          │
  │                                               │
  │  RELATIONSHIP:                                │
  │    complement = |U| - direct                  │
  │    (They're the same PIE, just different      │
  │     sides of the equation.)                   │
  └───────────────────────────────────────────────┘

---

C++ STL Reference

No dedicated STL container for PIE, but the following primitives appear constantly:

Facility	Header	Usage in PIE
__builtin_popcount(mask)	built-in	Determine sign: even popcount = add, odd = subtract
__builtin_ctzll(x)	built-in	Find lowest set bit (useful in factorization)
bitset<N>	<bitset>	Sieve of Eratosthenes for factorizations
vector<int>	<vector>	Store prime factors or condition list
1LL << m	--	Total number of subsets for bitmask enumeration

---

Implementation (Contest-Ready)

Version 1: Minimal PIE Template (Bitmask Enumeration)

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int MOD = 1e9 + 7;

// Generic PIE over m properties (m <= 20).
// f(mask) = count of elements satisfying ALL properties in mask.
// Returns count of elements satisfying NONE of the properties.
template<typename F>
ll pie(int m, F&& f) {
    ll ans = 0;
    for (int mask = 0; mask < (1 << m); mask++) {
        ll val = f(mask);
        if (__builtin_popcount(mask) & 1)
            ans = (ans - val % MOD + MOD) % MOD;
        else
            ans = (ans + val) % MOD;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Example: count integers in [1..n] coprime to n.
    ll n;
    cin >> n;

    // Factorize n
    vector<ll> primes;
    ll tmp = n;
    for (ll p = 2; p * p <= tmp; p++) {
        if (tmp % p == 0) {
            primes.push_back(p);
            while (tmp % p == 0) tmp /= p;
        }
    }
    if (tmp > 1) primes.push_back(tmp);

    int m = primes.size();
    ll ans = 0;
    for (int mask = 0; mask < (1 << m); mask++) {
        ll prod = 1;
        for (int i = 0; i < m; i++)
            if (mask >> i & 1)
                prod *= primes[i];
        ll cnt = n / prod;
        if (__builtin_popcount(mask) & 1)
            ans -= cnt;
        else
            ans += cnt;
    }
    cout << ans << "\n"; // Euler's totient of n
}

Version 2: Full Toolkit with Comments

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int MOD = 1e9 + 7;
const int MAXN = 2e6 + 5;

ll fac[MAXN], inv_fac[MAXN];

ll power(ll a, ll b, ll mod) {
    ll res = 1;
    a %= mod;
    for (; b > 0; b >>= 1) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}

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

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

// --------------- PIE: Bitmask Template ---------------
// f(mask) returns count of elements satisfying ALL conditions in mask.
// Result = count satisfying NONE of the conditions.
template<typename F>
ll pie(int m, F&& f) {
    ll ans = 0;
    for (int mask = 0; mask < (1 << m); mask++) {
        ll val = f(mask);
        if (__builtin_popcount(mask) & 1)
            ans = (ans - val % MOD + MOD) % MOD;
        else
            ans = (ans + val) % MOD;
    }
    return ans;
}

// --------------- Euler Totient via PIE ---------------
// Count integers in [1..n] coprime to n.
// Factorize n into distinct primes, then PIE over subsets.
ll euler_totient_pie(ll n) {
    vector<ll> primes;
    ll tmp = n;
    for (ll p = 2; p * p <= tmp; p++) {
        if (tmp % p == 0) {
            primes.push_back(p);
            while (tmp % p == 0) tmp /= p;
        }
    }
    if (tmp > 1) primes.push_back(tmp);

    int m = primes.size();
    ll ans = 0;
    for (int mask = 0; mask < (1 << m); mask++) {
        ll prod = 1;
        for (int i = 0; i < m; i++)
            if (mask >> i & 1)
                prod *= primes[i];
        if (__builtin_popcount(mask) & 1)
            ans -= n / prod;
        else
            ans += n / prod;
    }
    return ans;
}

// --------------- Derangements via PIE ---------------
// D(n) = number of permutations with no fixed point.
// D(n) = sum_{k=0}^{n} (-1)^k * C(n,k) * (n-k)!
ll derangements(int n) {
    ll ans = 0;
    for (int k = 0; k <= n; k++) {
        ll term = C(n, k) * fac[n - k] % MOD;
        if (k & 1)
            ans = (ans - term + MOD) % MOD;
        else
            ans = (ans + term) % MOD;
    }
    return ans;
}

// --------------- Surjections via PIE ---------------
// Count surjective functions from set of size n to set of size m.
// S(n, m) = sum_{k=0}^{m} (-1)^k * C(m, k) * (m-k)^n
ll surjections(int n, int m_set) {
    ll ans = 0;
    for (int k = 0; k <= m_set; k++) {
        ll term = C(m_set, k) * power(m_set - k, n, MOD) % MOD;
        if (k & 1)
            ans = (ans - term + MOD) % MOD;
        else
            ans = (ans + term) % MOD;
    }
    return ans;
}

// --------------- Coprime Pairs in Range via PIE ---------------
// Count integers in [1..r] coprime to a given set of primes.
// Used when you need coprime-to-specific-number, not all coprimes.
ll coprime_count(ll r, const vector<ll>& primes) {
    if (r <= 0) return 0;
    int m = primes.size();
    ll ans = 0;
    for (int mask = 0; mask < (1 << m); mask++) {
        ll prod = 1;
        for (int i = 0; i < m; i++)
            if (mask >> i & 1)
                prod *= primes[i];
        if (__builtin_popcount(mask) & 1)
            ans -= r / prod;
        else
            ans += r / prod;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    precompute();

    // --- Demo: Euler's totient ---
    ll n = 30;
    cout << "phi(" << n << ") = " << euler_totient_pie(n) << "\n";
    // Output: phi(30) = 8

    // --- Demo: Derangements ---
    cout << "D(5) = " << derangements(5) << "\n";
    // Output: D(5) = 44

    // --- Demo: Surjections ---
    // Onto functions from 4-element set to 3-element set
    cout << "surjections(4, 3) = " << surjections(4, 3) << "\n";
    // Output: surjections(4, 3) = 36

    // --- Demo: Coprime count ---
    vector<ll> primes_of_30 = {2, 3, 5};
    cout << "coprimes to 30 in [1..30] = "
         << coprime_count(30, primes_of_30) << "\n";
    // Output: coprimes to 30 in [1..30] = 8
}

Version 3: PIE for Counting in a Range [l, r]

Many problems ask "count integers in $[l,r]$ with property $P$." Use prefix sums: $f(l,r)=f(1,r)-f(1,l-1)$.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// Count integers in [1..x] divisible by at least one element of divs.
ll count_divisible(ll x, const vector<ll>& divs) {
    if (x <= 0) return 0;
    int m = divs.size();
    ll ans = 0;
    for (int mask = 1; mask < (1 << m); mask++) {
        ll lcm = 1;
        for (int i = 0; i < m; i++) {
            if (mask >> i & 1) {
                lcm = lcm / __gcd(lcm, divs[i]) * divs[i];
                if (lcm > x) break; // overflow guard
            }
        }
        if (__builtin_popcount(mask) & 1)
            ans += x / lcm;
        else
            ans -= x / lcm;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Count integers in [10..50] divisible by 2, 3, or 7.
    vector<ll> divs = {2, 3, 7};
    ll l = 10, r = 50;
    ll ans = count_divisible(r, divs) - count_divisible(l - 1, divs);
    cout << ans << "\n"; // 31
}

---

Operations Reference

Operation	Time	Space	Notes
PIE over $m$ properties (bitmask)	$O(2^m\cdot f)$	$O(m)$	$f$ = cost per subset. $m\le 20$.
Euler's totient $\phi (n)$ via PIE	$O(2^{\omega (n)}\cdot \omega (n))$	$O(\omega (n))$	$\omega (n)\le 15$ for $n\le {10}^{18}$.
Derangements $D(n)$	$O(n)$	$O(1)$	With precomputed factorials.
Surjections $S(n,m)$	$O(m\log n)$	$O(1)$	$m$ terms, each with $O(\log n)$ exponentiation.
Coprime count in $[1..r]$	$O(2^{\omega (n)})$	$O(\omega (n))$	Per query, after factorization.
Factorize $n$ (trial division)	$O(\sqrt{n})$	$O(\omega (n))$	Sufficient for $n\le {10}^{12}$.
Coprime count in $[l..r]$	$O(2^{\omega (n)})$	$O(\omega (n))$	Two prefix queries.

---

Problem Patterns & Tricks

Pattern 1: Coprime Count / Euler's Totient

"Count integers in $[1..n]$ coprime to $n$" or "count pairs $(a,b)$ with $gcd(a,b)=1$."

Approach: Factorize $n$ into distinct primes $p_1,\dots ,p_k$. Let $A_i$ = multiples of $p_i$ in the range. PIE gives $|A_1\cup \cdots \cup A_k|$; subtract from $n$ to get the coprime count.

// phi(n) via PIE -- see Version 2 above
ll phi = euler_totient_pie(n);

Problems: CF 1139D - Steps to One, CF 803F - Coprime Subsequences

---

Pattern 2: Derangements / Forbidden Positions

"Count permutations where no element stays in its original position" or "assign $n$ items to $n$ slots with forbidden (item, slot) pairs."

Approach: Let $A_i$ = permutations where element $i$ is a fixed point. $|A_{i_1}\cap \cdots \cap A_{i_k}|=(n-k)!$. By PIE: $D(n)=\sum _{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})(n-k)!$.

Recurrence (faster for small $n$): $D(n)=(n-1)(D(n-1)+D(n-2))$ with $D(0)=1$, $D(1)=0$.

ll D = derangements(n);

Problems: CF 888D - Almost Identity Permutations, CF 340E - Iahub and Permutations

---

Pattern 3: Surjective Functions / Distributing Distinct Items

"Distribute $n$ distinct balls into $m$ distinct boxes so every box is non-empty." Equivalent to counting surjections from $[n]$ to $[m]$.

Approach: Total functions = $m^n$. Subtract those missing at least one box via PIE. Missing a specific set $S$ of $k$ boxes: $(m-k{)}^n$ choices.

$S(n,m)=\sum _{k=0}^m(-1{)}^k(\genfrac{}{}{0ex}{}{m}{k})(m-k{)}^n$

Note: $S(n,m)=m!\cdot S_2(n,m)$ where $S_2$ is the Stirling number of the second kind.

ll ans = surjections(n, m);

Problems: CF 932E - Team Work, CF 1342E - Placing Rooks

---

Pattern 4: Stars and Bars with Upper Bounds

"Count non-negative integer solutions to $x_1+\cdots +x_k=n$ where $x_i\le c_i$." Without upper bounds, use Stars and Bars. With upper bounds, PIE subtracts over-allocations.

Approach: Let $A_i$ = solutions where $x_i>c_i$. Substitute $y_i=x_i-c_i-1$ to get unconstrained Stars and Bars for each intersection.

// For each mask of violated constraints:
//   new_n = n - sum of (c_i + 1) for i in mask
//   if new_n >= 0: contribution = C(new_n + k - 1, k - 1)
ll ans = 0;
for (int mask = 0; mask < (1 << k); mask++) {
    ll rem = n;
    for (int i = 0; i < k; i++)
        if (mask >> i & 1)
            rem -= c[i] + 1;
    if (rem < 0) continue;
    ll term = C(rem + k - 1, k - 1);
    if (__builtin_popcount(mask) & 1)
        ans = (ans - term + MOD) % MOD;
    else
        ans = (ans + term) % MOD;
}

Problems: CF 451E - Devu and Flowers, CF 1462D - Add to Neighbour and Remove

---

Pattern 5: Divisibility Count in Range [l, r]

"How many integers in $[l,r]$ are divisible by at least one of $d_1,\dots ,d_m$?" (or the complement: coprime to all of them).

Approach: PIE with $A_i$ = multiples of $d_i$. Intersection sizes use LCM: $|A_{i_1}\cap \cdots \cap A_{i_k}|=\lfloor n/\text{lcm}(d_{i_1},\dots ,d_{i_k})\rfloor$. Use prefix sums for arbitrary ranges.

ll ans = count_divisible(r, divs) - count_divisible(l - 1, divs);

Problems: CF 1295D - Same GCDs, CF 1114D - Flood Fill

---

Pattern 6: Grid Paths Avoiding Forbidden Cells

"Count lattice paths from $(0,0)$ to $(n,m)$ avoiding $k$ forbidden cells."

Approach: Sort forbidden cells by $(x+y)$. Let $f(i)$ = number of valid paths from start to forbidden cell $i$ (no other forbidden cell visited). Apply PIE: subtract paths through exactly one forbidden cell, add back paths through exactly two, etc. This is $O(k^2)$ or $O(k^2\log n)$.

Problems: CF 559C - Gerald and Giant Chess, CF 722E - Research Rover

---

Pattern 7: At-Least-K via PIE + Binomial Sums

"Count elements satisfying at least $k$ of $m$ conditions." Generalizes the standard union ($k=1$).

Approach: Bonferroni / Generalized PIE. Let $S_j=\sum _{|T|=j}|\bigcap _{i\in T}{A}_i|$. Then the count of elements in at least $k$ sets is:

$N_{\ge k}=\sum _{j=k}^m(-1{)}^{j-k}(\genfrac{}{}{0ex}{}{j-1}{k-1})S_j$

Rarely appears directly but underlies some advanced problems.

---

Pattern 8: Chromatic Polynomial / Graph Coloring

"Color a graph with $k$ colors so no two adjacent vertices share a color."

Approach: Let $A_e$ = colorings violating edge $e$. PIE over edges is $O(2^{|E|})$ -- only feasible for $|E|\le 20$. For sparse graphs, use the deletion-contraction recurrence instead.

Problems: CF 1444D - Divisor Coloring

---

Pattern 9: Derangement PIE Structure

When applying PIE to derangements, the symmetry of the permutation group causes every subset of size $k$ to contribute the same intersection size $(n-k)!$. This is the canonical example of the "collapse to $O(m)$" trick.

  DERANGEMENT PIE STRUCTURE (n = 4):
  ┌───────────────────────────────────────────────────────────┐
  │  Properties: A_i = "position i is a fixed point"         │
  │                                                          │
  │  k=0:  C(4,0)*4! = +24    <- total permutations          │
  │  k=1:  C(4,1)*3! = -24    <- fix 1 position, permute 3  │
  │  k=2:  C(4,2)*2! = +12    <- fix 2 positions, permute 2  │
  │  k=3:  C(4,3)*1! =  -4    <- fix 3 positions, permute 1  │
  │  k=4:  C(4,4)*0! =  +1    <- all 4 fixed (identity)      │
  │                    ──────                                 │
  │  D(4) =             9     <- derangements of 4 elements   │
  │                                                          │
  │  Key: f(S) = (4-|S|)! depends ONLY on |S|, so we sum    │
  │  over k = 0..4 instead of enumerating 2^4 = 16 subsets.  │
  └───────────────────────────────────────────────────────────┘

---

Contest Cheat Sheet

+---------------------------------------------------------------+
|           INCLUSION-EXCLUSION CHEAT SHEET                     |
+---------------------------------------------------------------+
| CORE FORMULA (complement form):                               |
|   count(NONE) = sum over S in 2^[m]:                          |
|                   (-1)^|S| * f(S)                             |
|   where f(S) = count satisfying ALL conditions in S           |
+---------------------------------------------------------------+
| BITMASK PIE (m <= 20):                                        |
|   for (int mask = 0; mask < (1<<m); mask++) {                 |
|       int sign = (__builtin_popcount(mask) & 1) ? -1 : +1;   |
|       ans += sign * f(mask);                                  |
|   }                                                           |
+---------------------------------------------------------------+
| COMMON f(mask) VALUES:                                        |
|   Coprime:     n / product_of_primes_in_mask                  |
|   Derange:     C(n,k) * (n-k)!     [k = popcount]            |
|   Surject:     C(m,k) * (m-k)^n    [k = popcount]            |
|   Stars+Bars:  C(rem+k-1, k-1)     [rem = n - sum(c_i+1)]   |
+---------------------------------------------------------------+
| SIGN RULE:                                                    |
|   popcount even -> ADD    popcount odd -> SUBTRACT            |
|   Empty set (mask=0) always contributes +f(0) = +|universe|  |
+---------------------------------------------------------------+
| RANGE TRICK:                                                  |
|   count in [l..r] = count in [1..r] - count in [1..l-1]      |
+---------------------------------------------------------------+
| TOTIENT:                                                      |
|   phi(n) = n * prod(1 - 1/p) for each prime p | n            |
|          = PIE over prime factors of n                        |
+---------------------------------------------------------------+
| DERANGEMENTS:                                                 |
|   D(n) = (n-1)*(D(n-1) + D(n-2)),  D(0)=1, D(1)=0           |
|   D(n) ~ n!/e,  approximation useful for sanity checks       |
+---------------------------------------------------------------+

---

Gotchas & Debugging

• Sign error at mask = 0. The empty set contributes $+f(\mathrm{\varnothing })$, which is the total count without restrictions (e.g., $n$ for coprime counting). If you start your loop at mask = 1 you miss this term.

• Overflow in product of primes. When computing the LCM or product of primes in a bitmask, the product can exceed ${10}^{18}$. Guard with if (prod > n) break; inside the inner loop.

• LCM vs product. For coprime primes (like distinct prime factors of $n$), LCM = product. For general divisors, you must use LCM. Using product when divisors share factors gives wrong answers silently.

• Negative intermediate results. In C++, (a - b) % MOD can be negative. Always use (a - b % MOD + MOD) % MOD.

• Off-by-one in range queries. count_in_range(l, r) = f(r) - f(l - 1), not f(r) - f(l). Triple-check with the example $[1..1]$: should be f(1).

• Factorization misses a prime. Trial division must check up to $\sqrt{n}$ AND handle the remaining factor if $>1$. Forgetting the if (tmp > 1) line loses a prime factor.

• $m>20$ but problem still says "bitmask." If $m$ exceeds 20, $2^m$ subsets are too many. Look for structure: Mobius inversion, DP over divisors, or segmented approaches instead.

• Derangement recurrence base cases. $D(0)=1$ (the empty permutation is a derangement). $D(1)=0$. Getting $D(0)$ wrong propagates through everything.

• Stars and Bars: negative remainder. If rem = n - sum(c_i + 1) < 0, skip that mask (no solutions). Forgetting this check causes negative arguments to $(\genfrac{}{}{0ex}{}{n}{k})$.

• Debugging PIE. Print each mask's contribution. Verify the $m=2$ case by hand: $|A\cup B|=|A|+|B|-|A\cap B|$.

Mental Traps

"PIE is just alternating signs on a sum." The alternating signs are the output of the formula, not the input of the thinking. The real work is identifying what the "bad properties" are, defining $f(S)$ for each subset, and computing $f(S)$ efficiently. The alternating sum is the last step, not the first.

"PIE works for any set of constraints." PIE works when you can compute $f(S)=|\bigcap _{i\in S}{A}_i|$ for any subset $S$. This requires that violating multiple constraints simultaneously has a clean count. If the constraints interact in ways that make $f(S)$ intractable, PIE fails. Many people attempt PIE without verifying this computability.

"I'll apply PIE with $m=n$ properties." PIE with $m$ properties costs $O(2^m)$. With $m=20$ that's $\sim {10}^6$, fine. With $m=30$, it's $\sim {10}^9$, too slow. If $m>25$, look for structure in $f(S)$ that allows collapsing subsets into a smaller computation.

MENTAL TRAP DETECTOR:

  "I know how to apply PIE here"
       |
       v
  +--- Can you define f(S) for EVERY subset S? ---+
  |  YES                                      NO  |
  v                                                v
  +--- Is f(S) computable in O(1) or O(k)? ---+   STOP.
  |  YES                                  NO   |   PIE may not
  v                                            v   apply here.
  +--- Is 2^m feasible (<= ~2^20)? ---+       |
  |  YES                          NO   |       |
  v                                    v       |
  Apply bitmask PIE.            Does f(S)      |
                                depend only     |
                                on |S|?         |
                                  |    |        |
                                 YES   NO       |
                                  |    |        |
                                  v    v        |
                          Use O(m)  Need        |
                          formula   Mobius or    |
                                    other trick  |
  +---------------------------------------------+

"I forgot to count the empty set term." The empty set $S=\mathrm{\varnothing }$ contributes $(-1{)}^0\cdot f(\mathrm{\varnothing })=+|U|$ (the entire universe). This is the baseline count -- the total before any exclusions. If your bitmask loop starts at mask = 1 instead of mask = 0, you silently drop this term, and your answer is off by exactly $|U|$. This is the single most common PIE bug.

"PIE is only for counting." PIE extends beyond cardinalities. It works for probabilities ($P(A_1\cup \cdots \cup A_m)$), expected values ($E[\text{number of violated constraints}]$), and formal power series (via Möbius inversion). Whenever you see an alternating-sign identity over subsets, PIE is lurking -- even in contexts that don't look like "counting."

  PIE BEYOND COUNTING:
  ┌─────────────────────────────────────────────────────────┐
  │  Domain          f(S)                  Result           │
  │  ──────────────  ──────────────────    ───────────────  │
  │  Cardinality     |∩_{i∈S} A_i|        |Ā₁ ∩...∩ Āₘ|   │
  │  Probability     P(∩_{i∈S} A_i)       P(Ā₁ ∩...∩ Āₘ)  │
  │  Expected value  E[indicator of S]     E[# good elts]  │
  │  Möbius inv.     g(S) on lattice       f(S) recovered  │
  │                                                        │
  │  Same formula:  Σ_{S} (-1)^|S| * f(S)                  │
  │  Different interpretations of f and the result.         │
  └─────────────────────────────────────────────────────────┘

---

Common Mistakes

1. Intersection count uses LCM (or product for coprime), not sum. On "count numbers in $[1,N]$ divisible by at least one of $p_1,\dots ,p_k$" (all prime), a bitmask PIE that computes the contribution of subset $\{2,3,5\}$ as $\lfloor N/(2+3+5)\rfloor$ is wrong; the intersection "divisible by 2 AND 3 AND 5" is "divisible by $\mathrm{lcm}(2,3,5)=30$", so the count is $\lfloor N/30\rfloor$. The rule: intersection of divisibility constraints is divisibility by the LCM (which equals the product when the numbers are coprime primes). Sanity-check with a tiny example: numbers in $[1,30]$ divisible by both 2 and 3 should be 5 (the multiples of 6), not $\lfloor 30/5\rfloor =6$.

Debug Drills

Drill 1. Wrong sign in PIE.

long long result = 0;
for (int mask = 1; mask < (1 << k); mask++) {
    long long inter = compute_intersection(mask);
    result += inter;  // What's wrong?
}
answer = total - result;

What's wrong?

PIE requires alternating signs: subsets of odd size are added, subsets of even size are subtracted (when computing |A₁ ∪ ... ∪ Aₖ|). Fix: int bits = __builtin_popcount(mask); result += (bits % 2 == 1 ? 1 : -1) * inter;

Drill 2. Derangement integer overflow.

long long D[N + 1];
D[0] = 1; D[1] = 0;
for (int i = 2; i <= N; i++)
    D[i] = (i - 1) * (D[i-1] + D[i-2]);  // What's wrong?

What's wrong?

When i and D[i-1] are both large, (i-1) * (D[i-1] + D[i-2]) overflows long long. If working mod p: D[i] = (long long)(i-1) % MOD * ((D[i-1] + D[i-2]) % MOD) % MOD. Don't forget to cast and mod at every multiplication.

Drill 3. PIE with wrong intersection formula.

// Count numbers in [1, N] not divisible by any prime in primes[]
long long count = N;
for (int mask = 1; mask < (1 << k); mask++) {
    long long prod = 1;
    for (int i = 0; i < k; i++)
        if (mask & (1 << i)) prod += primes[i];  // What's wrong?
    int bits = __builtin_popcount(mask);
    if (bits % 2 == 1) count -= N / prod;
    else count += N / prod;
}

What's wrong?

prod += primes[i] should be prod *= primes[i]. The intersection of "divisible by p₁ and p₂" is "divisible by p₁*p₂" (their LCM, which equals the product since they're distinct primes). Adding primes gives a meaningless quantity.

---

Self-Test

• [ ] Given $m$ "bad" properties, I can write the complement-form PIE formula from memory and explain why the $k=0$ term is $+|U|$.
• [ ] I can identify the "bad properties" and define $f(S)$ for: coprime counting, derangements, surjections, and stars-and-bars with upper bounds.
• [ ] I can recognize when $f(S)$ depends only on $|S|$ and collapse the $O(2^m)$ loop to $O(m)$ -- and I can name two classic problems where this applies.
• [ ] I can implement bitmask PIE without sign errors: sign = (popcount & 1) ? -1 : +1 for complement form, and I remember (ans + MOD) % MOD after subtraction.
• [ ] I can explain why PIE fails when $m>25$ and name at least one alternative (Möbius inversion on divisors, DP over subsets, or segmented approaches).

---

Practice Problems

Rating	You should be able to...
CF 1200	Compute derangement count D(n) using the recurrence
CF 1500	Apply PIE to count numbers in [1,N] not divisible by any of k given primes
CF 1800	Use bitmask PIE over <= 20 constraints; derive Euler's totient via PIE
CF 2100	Combine PIE with DP; apply Möbius inversion for multiplicative-function problems; compute chromatic polynomials

#	Problem	Source	Difficulty	Key Idea
1	Almost Identity Permutations	CF 888D	Easy (1600)	Derangement / PIE for "at most $k$ non-fixed points"
2	Same GCDs	CF 1295D	Easy (1600)	Euler totient via PIE
3	Placing Rooks	CF 1342E	Medium (1800)	Surjections via PIE + Stirling numbers
4	Coprime Subsequences	CF 803F	Medium (1800)	PIE / Mobius over GCD values
5	Iahub and Permutations	CF 340E	Medium (1800)	Derangement variant with partial restrictions
6	Devu and Flowers	CF 451E	Medium (1900)	Stars and Bars + PIE with upper bounds
7	Gerald and Giant Chess	CF 559C	Medium (1900)	Grid paths + PIE over forbidden cells
8	Team Work	CF 932E	Hard (2000)	Stirling numbers via PIE
9	Steps to One	CF 1139D	Hard (2100)	Expected value + PIE over prime factors
10	The Number of Good Subsets	LC 1994	Hard (2100)	Bitmask PIE over small primes
11	Prime Multiples	CSES	1700	Classic PIE: count numbers divisible by at least one prime
12	Counting Coprime Pairs	CSES	1900	Mobius/PIE to count coprime pairs
13	Christmas Party	CSES	1600	Count derangements (no one gets their own gift)

---

Further Reading

• cp-algorithms: Inclusion-Exclusion Principle -- Comprehensive treatment with Euler totient, derangements, and Mobius connection.
• cp-algorithms: Euler's Totient Function -- PIE derivation of the product formula.
• CF Blog: PIE and Applications (adamant) -- Advanced applications: chromatic polynomial, Stirling numbers.
• CF Blog: Tutorial on Mobius Inversion (TLE) -- Generalizes PIE to the Mobius function on posets.
• Concrete Mathematics (Graham, Knuth, Patashnik), Ch. 8 -- Rigorous combinatorial treatment.

Cross-references in this notebook:

• Combinatorics Basics -- Binomial coefficients, factorial precomputation, and the PIE template used here.
• Number Theory -- Prime factorization, Euler's totient (product formula), Mobius function.
• Bit Manipulation -- Bitmask enumeration, __builtin_popcount.