容斥原理

What · 是什么

容斥原理（Inclusion-Exclusion）：对有限集族 {S_i}，|∪S_i|=Σ_{m>=1}(-1)^{m-1}Σ|∩_{选 m 个}S_i|。每个元素恰好被计 1 次（由二项式定理证明）。推论：交集 |∩S_i|=|U|-|∪补集|；一般化：若 f(S)=Σ_{T⊆S}g(T) 则 g(S)=Σ_{T⊆S}(-1)^{|S|-|T|}f(T)（子集反演），其数论版本即莫比乌斯反演。应用：不定方程带上下界计数（插板+容斥）、错排 D_n=n!Σ(-1)^i/i!、数论中 gcd=k 数对计数（倍数容斥，倒推）、欧拉函数公式推导、min-max 容斥（期望版）、染色/排列禁忌位置计数等。

Why · 为什么

How · 实现

伪代码

# 模板: 求满足全部限制的计数
全集 = 无限制的计数方案
def f(mask):  # 对 mask 内限制'放水'后的计数
    ...
ans = sum( (-1)^{|mask|} * f(mask) for mask in range(1<<n) )

# 数论: gcd=k 数对倒推
f[N..1] 从大到小:
    f[k] = (N//k)^2 - sum_{i=2, i*k<=N} f[i*k]

Python 实现

import sys
sys.setrecursionlimit(10000)


def comb_mod(n, k, mod=998244353):
    """O(k) 计算组合数 C(n,k) mod p (n 可能很大, k 小)。"""
    if k < 0 or k > n:
        return 0
    num, den = 1, 1
    for i in range(k):
        num = num * ((n - i) % mod) % mod
        den = den * (i + 1) % mod
    return num * pow(den, mod - 2, mod) % mod


def solve_linear_diophantine_count(m, b):
    """容斥: 不定方程 sum x_i = m, 0<=x_i<=b_i 的非负整数解数.
    全集(无上界)方案数 C(m+n-1, n-1), 容斥枚举违反上界的子集. O(2^n)."""
    n = len(b)
    total = 0
    for mask in range(1 << n):
        s = m
        bits = 0
        for i in range(n):
            if mask >> i & 1:
                s -= b[i] + 1
                bits += 1
        if s < 0:
            continue
        ways = comb_mod(s + n - 1, n - 1)
        if bits & 1:
            total -= ways
        else:
            total += ways
    return total % 998244353


def brute_equation(m, b):
    """暴力枚举验证。"""
    n = len(b)

    def rec(i, rem):
        if i == n:
            return 1 if rem == 0 else 0
        c = 0
        for x in range(0, min(b[i], rem) + 1):
            c += rec(i + 1, rem - x)
        return c

    return rec(0, m)


def derangements(n, mod=998244353):
    """错排数 D_n = n! sum_{i=0}^n (-1)^i / i! (容斥)."""
    fact = 1
    for i in range(2, n + 1):
        fact = fact * i % mod
    invs = [1] * (n + 1)
    for i in range(1, n + 1):
        invs[i] = pow(i, mod - 2, mod)
    # 容斥公式
    res = 0
    for i in range(n + 1):
        t = fact * pow(invs[i], 1, mod) % mod
        # 简化: D_n = n! * sum (-1)^i / i!
        sign = -1 if i & 1 else 1
        # 用分数形式
    # 直接递推 D_n = (n-1)(D_{n-1}+D_{n-2}) 作为参考
    D = [1, 0]
    for i in range(2, n + 1):
        D.append((i - 1) * (D[i - 1] + D[i - 2]) % mod)
    # 容斥形式
    factn = fact
    res2 = 0
    for i in range(n + 1):
        c = comb_mod(n, i) * factn % mod * pow(pow(i, mod - 2, mod) if i else 1, 1, mod) % mod
        # C(n,i)*(n-i)! = n!/i!
        res2 = res2 + (-1 if i & 1 else 1) * (factn * pow(i, mod - 2, mod) % mod if i else factn)
    res2 = res2 % mod
    return D[n], res2


def gcd_pair_count(N):
    """容斥: 数对 (x,y), 1<=x,y<=N, gcd 恰为 k 的个数 f(k), 从 N 倒推. O(N log N)."""
    f = [0] * (N + 1)
    for k in range(N, 0, -1):
        f[k] = (N // k) * (N // k)
        for i in range(2 * k, N + 1, k):
            f[k] -= f[i]
    return f


if __name__ == "__main__":
    import random
    # 不定方程计数对拍
    for _ in range(100):
        n = random.randint(1, 5)
        m = random.randint(0, 8)
        b = [random.randint(0, 5) for _ in range(n)]
        a = solve_linear_diophantine_count(m, b)
        bb = brute_equation(m, b)
        assert a == bb, (m, b, a, bb)
    # 错排 D_n
    D, R = derangements(6)
    assert D == 265, D  # D_6 = 265
    # gcd 数对: f(1) 即互质有序对数 = 1 + 2*sum_{i=2}^N phi(i)
    f = gcd_pair_count(10)
    assert f[1] == 63, f[1]  # 有序互质对 (1<=x,y<=10, gcd=1)
    # 手工: 集合容斥 3 个集合
    # |A∪B∪C| = |A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC|
    print("inclusion-exclusion tests passed")

易错点

• 交集与并集公式搞反(并集容斥 vs 交集取补)
• 符号 (-1)^{m-1} 或 (-1)^{|mask|} 用错
• 数论容斥倒推顺序错误(应从大到小, f 用 f[i*k])
• 模意义组合数忘预计算逆元/阶乘
• min-max 容斥只在期望线性时可用(依赖线性期望), 忘记条件

例题

信源

• OI Wiki✓ https://oi-wiki.org/math/combinatorics/inclusion-exclusion-principle/
• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/math/combinatorics/inclusion-exclusion-principle.md
• CP-Algorithms✓ https://cp-algorithms.com/combinatorics/inclusion-exclusion.html
• 书籍✓ https://cses.fi/book/book.pdf