跳转至

# 容斥原理

## 引入

入门例题

假设班里有 1 0 10 个学生喜欢数学，1 5 15 个学生喜欢语文，2 1 21 个学生喜欢编程，班里至少喜欢一门学科的有多少个学生呢？

是 1 0 +1 5 +2 1 =4 6 10+15+21=46 个吗？不是的，因为有些学生可能同时喜欢数学和语文，或者语文和编程，甚至还有可能三者都喜欢．

为了叙述方便，我们把喜欢语文、数学、编程的学生集合分别用 𝐴,𝐵,𝐶 A,B,C 表示，则学生总数等于 |𝐴 ∪𝐵 ∪𝐶||A∪B∪C|．刚才已经讲过，如果把这三个集合的元素个数 |𝐴|,|𝐵|,|𝐶||A|,|B|,|C| 直接加起来，会有一些元素重复统计了，因此需要扣掉 |𝐴 ∩𝐵|,|𝐵 ∩𝐶|,|𝐶 ∩𝐴||A∩B|,|B∩C|,|C∩A|，但这样一来，又有一小部分多扣了，需要加回来，即 |𝐴 ∩𝐵 ∩𝐶||A∩B∩C|．即

|𝐴∪𝐵∪𝐶|=|𝐴|+|𝐵|+|𝐶|−|𝐴∩𝐵|−|𝐵∩𝐶|−|𝐶∩𝐴|+|𝐴∩𝐵∩𝐶||A∪B∪C|=|A|+|B|+|C|−|A∩B|−|B∩C|−|C∩A|+|A∩B∩C|

把上述问题推广到一般情况，就是我们熟知的容斥原理．

## 定义

设 U 中元素有 n 种不同的属性，而第 i 种属性称为 𝑃 𝑖 P i，拥有属性 𝑃 𝑖 P i 的元素构成集合 𝑆 𝑖 S i，那么

∣𝑛⋃𝑖=1 𝑆 𝑖∣=∑𝑖|𝑆 𝑖|−∑𝑖<𝑗|𝑆 𝑖∩𝑆 𝑗|+∑𝑖<𝑗<𝑘|𝑆 𝑖∩𝑆 𝑗∩𝑆 𝑘|−⋯+(−1)𝑚−1∑𝑎 𝑖<𝑎 𝑖+1∣𝑚⋂𝑖=1 𝑆 𝑎 𝑖∣+⋯+(−1)𝑛−1|𝑆 1∩⋯∩𝑆 𝑛||⋃i=1 n S i|=∑i|S i|−∑i<j|S i∩S j|+∑i<j<k|S i∩S j∩S k|−⋯+(−1)m−1∑a i<a i+1|⋂i=1 m S a i|+⋯+(−1)n−1|S 1∩⋯∩S n|

即

∣𝑛⋃𝑖=1 𝑆 𝑖∣=𝑛∑𝑚=1(−1)𝑚−1∑𝑎 𝑖<𝑎 𝑖+1∣𝑚⋂𝑖=1 𝑆 𝑎 𝑖∣|⋃i=1 n S i|=∑m=1 n(−1)m−1∑a i<a i+1|⋂i=1 m S a i|

### 证明

对于每个元素使用二项式定理计算其出现的次数．对于元素 x，假设它出现在 𝑇 1,𝑇 2,⋯,𝑇 𝑚 T 1,T 2,⋯,T m 的集合中，那么它的出现次数为

𝐶 𝑛 𝑡=|{𝑇 𝑖}|−|{𝑇 𝑖∩𝑇 𝑗|𝑖<𝑗}|+⋯+(−1)𝑘−1∣{𝑘⋂𝑖=1 𝑇 𝑎 𝑖|𝑎 𝑖<𝑎 𝑖+1}∣+⋯+(−1)𝑚−1|{𝑇 1∩⋯∩𝑇 𝑚}|=(𝑚 1)−(𝑚 2)+⋯+(−1)𝑚−1(𝑚 𝑚)=(𝑚 0)−𝑚∑𝑖=0(−1)𝑖(𝑚 𝑖)=1−(1−1)𝑚=1 C n t=|{T i}|−|{T i∩T j|i<j}|+⋯+(−1)k−1|{⋂i=1 k T a i|a i<a i+1}|+⋯+(−1)m−1|{T 1∩⋯∩T m}|=(m 1)−(m 2)+⋯+(−1)m−1(m m)=(m 0)−∑i=0 m(−1)i(m i)=1−(1−1)m=1

于是每个元素出现的次数为 1，那么合并起来就是并集．证毕．

### 补集

对于全集 U 下的 集合的并 可以使用容斥原理计算，而集合的交则用全集减去 补集的并集 求得：

∣𝑛⋂𝑖=1 𝑆 𝑖∣=|𝑈|−∣𝑛⋃𝑖=1――𝑆 𝑖∣|⋂i=1 n S i|=|U|−|⋃i=1 n S i―|

右边使用容斥即可．

可能接触过容斥的读者都清楚上述内容，而更关心的是容斥的应用．

那么接下来我们给出 3 个层次不同的例题来为大家展示容斥原理的应用．

## 不定方程非负整数解计数

不定方程非负整数解计数

给出不定方程 ∑𝑛 𝑖=1 𝑥 𝑖 =𝑚∑i=1 n x i=m 和 𝑛 n 个限制条件 𝑥 𝑖 ≤𝑏 𝑖 x i≤b i，其中 𝑚,𝑏 𝑖 ∈ℕ m,b i∈N. 求方程的非负整数解的个数．

### 没有限制时

如果没有 𝑥 𝑖 ≤𝑏 𝑖 x i≤b i 的限制，那么不定方程 ∑𝑛 𝑖=1 𝑥 𝑖 =𝑚∑i=1 n x i=m 的非负整数解的数目为 (𝑚+𝑛−1 𝑛−1)(m+n−1 n−1).

略证：插板法．

相当于你有 𝑚 m 个球要分给 𝑛 n 个盒子，允许某个盒子是空的．这个问题不能直接用组合数解决．

于是我们再加入 𝑛 −1 n−1 个球，于是问题就变成了在一个长度为 𝑚 +𝑛 −1 m+n−1 的球序列中选择 𝑛 −1 n−1 个球，然后这个 𝑛 −1 n−1 个球把这个序列隔成了 𝑛 n 份，恰好可以一一对应放到 𝑛 n 个盒子中．那么在 𝑚 +𝑛 −1 m+n−1 个球中选择 𝑛 −1 n−1 个球的方案数就是 (𝑚+𝑛−1 𝑛−1)(m+n−1 n−1)．

### 容斥模型

接着我们尝试抽象出容斥原理的模型：

1. 全集 U：不定方程 ∑𝑛 𝑖=1 𝑥 𝑖 =𝑚∑i=1 n x i=m 的非负整数解
2. 元素：变量 𝑥 𝑖 x i.
3. 属性：𝑥 𝑖 x i 的属性即 𝑥 𝑖 x i 满足的条件，即 𝑥 𝑖 ≤𝑏 𝑖 x i≤b i 的条件

目标：所有变量满足对应属性时集合的大小，即 |⋂𝑛 𝑖=1 𝑆 𝑖||⋂i=1 n S i|.

这个东西可以用 |⋂𝑛 𝑖=1 𝑆 𝑖| =|𝑈| −∣⋃𝑛 𝑖=1――𝑆 𝑖∣|⋂i=1 n S i|=|U|−|⋃i=1 n S i―| 求解．|𝑈||U| 可以用组合数计算，后半部分自然使用容斥原理展开．

那么问题变成，对于一些 ―――𝑆 𝑎 𝑖 S a i― 的交集求大小．考虑 ―――𝑆 𝑎 𝑖 S a i― 的含义，表示 𝑥 𝑎 𝑖 ≥𝑏 𝑎 𝑖 +1 x a i≥b a i+1 的解的数目．而交集表示同时满足这些条件．因此这个交集对应的不定方程中，有些变量有 下界限制，而有些则没有限制．

能否消除这些下界限制呢？既然要求的是非负整数解，而有些变量的下界又大于 0 0，那么我们直接 把这个下界减掉，就可以使得这些变量的下界变成 0 0，即没有下界啦．因此对于

∣1≤𝑖≤𝑘⋂𝑎 𝑖<𝑎 𝑖+1 𝑆 𝑎 𝑖∣|⋂a i<a i+1 1≤i≤k S a i|

的不定方程形式为

𝑛∑𝑖=1 𝑥 𝑖=𝑚−𝑘∑𝑖=1(𝑏 𝑎 𝑖+1)∑i=1 n x i=m−∑i=1 k(b a i+1)

于是这个也可以组合数计算啦．这个长度为 𝑘 k 的 𝑎 a 数组相当于在枚举子集．

## HAOI2008 硬币购物

HAOI2008 硬币购物

4 种面值的硬币，第 i 种的面值是 𝐶 𝑖 C i．𝑛 n 次询问，每次询问给出每种硬币的数量 𝐷 𝑖 D i 和一个价格 𝑆 S，问付款方式．

𝑛 ≤1 0 3,𝑆 ≤1 0 5 n≤10 3,S≤10 5.

如果用背包做的话复杂度是 𝑂(4 𝑛 𝑆)O(4 n S)，无法承受．这道题最明显的特点就是硬币一共只有四种．抽象模型，其实就是让我们求方程 ∑4 𝑖=1 𝐶 𝑖 𝑥 𝑖 =𝑆,𝑥 𝑖 ≤𝐷 𝑖∑i=1 4 C i x i=S,x i≤D i 的非负整数解的个数．

采用同样的容斥方式，𝑥 𝑖 x i 的属性为 𝑥 𝑖 ≤𝐷 𝑖 x i≤D i. 套用容斥原理的公式，最后我们要求解

4∑𝑖=1 𝐶 𝑖 𝑥 𝑖=𝑆−𝑘∑𝑖=1 𝐶 𝑎 𝑖(𝐷 𝑎 𝑖+1)∑i=1 4 C i x i=S−∑i=1 k C a i(D a i+1)

也就是无限背包问题．这个问题可以预处理，算上询问，总复杂度 𝑂(4 𝑆 +2 4 𝑛)O(4 S+2 4 n)．

代码实现

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    #include <iostream>
    using namespace std;
    constexpr long long S = 1e5 + 5;
    long long c[5], d[5], n, s;
    long long f[S];

    int main() {
      cin.tie(nullptr)->sync_with_stdio(false);
      cin >> c[1] >> c[2] >> c[3] >> c[4] >> n;
      f[0] = 1;
      for (long long j = 1; j <= 4; j++)
        for (long long i = 1; i < S; i++)
          if (i >= c[j]) f[i] += f[i - c[j]];  // f[i]：价格为i时的硬币组成方法数
      for (long long k = 1; k <= n; k++) {
        cin >> d[1] >> d[2] >> d[3] >> d[4] >> s;
        long long ans = 0;
        for (long long i = 1; i < 16;
             i++) {  // 容斥，因为物品一共有4种，所以从1到2^4-1=15循环
          long long m = s, bit = 0;
          for (long long j = 1; j <= 4; j++) {
            if ((i >> (j - 1)) % 2 == 1) {
              m -= (d[j] + 1) * c[j];
              bit++;
            }
          }
          if (m >= 0) ans += (bit % 2 * 2 - 1) * f[m];
        }
        cout << f[s] - ans << '\n';
      }
      return 0;
    }

## 完全图子图染色问题

前面的三道题都是容斥原理的正向运用，这道题则需要用到容斥原理逆向分析．

完全图子图染色问题

A 和 B 喜欢对图（不一定连通）进行染色，而他们的规则是，相邻的结点必须染同一种颜色．今天 A 和 B 玩游戏，对于 𝑛 n 阶 完全图 𝐺 =(𝑉,𝐸)G=(V,E)．他们定义一个估价函数 𝐹(𝑆)F(S)，其中 S 是边集，𝑆 ⊆𝐸 S⊆E.𝐹(𝑆)F(S) 的值是对图 𝐺′ =(𝑉,𝑆)G′=(V,S) 用 𝑚 m 种颜色染色的总方案数．他们的另一个规则是，如果 |𝑆||S| 是奇数，那么 A 的得分增加 𝐹(𝑆)F(S)，否则 B 的得分增加 𝐹(𝑆)F(S). 问 A 和 B 的得分差值．

### 数学形式

一看这道题的算法趋向并不明显，因此对于棘手的题目首先抽象出数学形式．得分差即为奇偶对称差，可以用 -1 的幂次来作为系数．我们求的是

𝐴 𝑛 𝑠=∑𝑆⊆𝐸(−1)|𝑆|−1 𝐹(𝑆)A n s=∑S⊆E(−1)|S|−1 F(S)

### 容斥模型

相邻结点染同一种颜色，我们把它当作属性．在这里我们先不遵守染色的规则，假定我们用 m 种颜色直接对图染色．对于图 𝐺′ =(𝑉,𝑆)G′=(V,S)，我们把它当作 元素．属性 𝑥 𝑖 =𝑥 𝑗 x i=x j 的含义是结点 i,j 染同色（注意，并未要求 i,j 之间有连边）．

而属性 𝑥 𝑖 =𝑥 𝑗 x i=x j 对应的 集合 定义为 𝑄 𝑖,𝑗 Q i,j，其含义是所有满足该属性的图 𝐺′G′ 的染色方案，集合的大小就是满足该属性的染色方案数，集合内的元素相当于所有满足该属性的图 𝐺′G′ 的染色图．

回到题目，「相邻的结点必须染同一种颜色」，可以理解为若干个 𝑄 Q 集合的交集．因此可以写出

𝐹(𝑆)=∣⋂(𝑖,𝑗)∈𝑆 𝑄 𝑖,𝑗∣F(S)=|⋂(i,j)∈S Q i,j|

上述式子右边的含义就是说对于 S 内的每一条边 (𝑖,𝑗)(i,j) 都满足 𝑥 𝑖 =𝑥 𝑗 x i=x j 的染色方案数，也就是 𝐹(𝑆)F(S).

是不是很有容斥的味道了？由于容斥原理本身没有二元组的形式，因此我们把 所有 的边 (𝑖,𝑗)(i,j) 映射到 𝑇 =𝑛(𝑛+1)2 T=n(n+1)2 个整数上，假设将 (𝑖,𝑗)(i,j) 映射为 𝑘,1 ≤𝑘 ≤𝑇 k,1≤k≤T，同时 𝑄 𝑖,𝑗 Q i,j 映射为 𝑄 𝑘 Q k. 那么属性 𝑥 𝑖 =𝑥 𝑗 x i=x j 则定义为 𝑃 𝑘 P k.

同时 S 可以表示为若干个 k 组成的集合，即 𝑆 ⟺ 𝐾 ={𝑘 1,𝑘 2,⋯,𝑘 𝑚}S⟺K={k 1,k 2,⋯,k m}.（也就是说我们在边集与数集间建立了等价关系）．

而 E 对应集合 𝑀 ={1,2,⋯,𝑛(𝑛+1)2}M={1,2,⋯,n(n+1)2}. 于是乎

𝐹(𝑆)⟺𝐹({𝑘 𝑖})=∣⋂𝑘 𝑖 𝑄 𝑘 𝑖∣F(S)⟺F({k i})=|⋂k i Q k i|

### 逆向分析

那么要求的式子展开

𝐴 𝑛 𝑠=∑𝐾⊆𝑀(−1)|𝐾|−1∣⋂𝑘 𝑖∈𝐾 𝑄 𝑘 𝑖∣=∑𝑖|𝑄 𝑖|−∑𝑖<𝑗|𝑄 𝑖∩𝑄 𝑗|+∑𝑖<𝑗<𝑘|𝑄 𝑖∩𝑄 𝑗∩𝑄 𝑘|−⋯+(−1)𝑇−1∣𝑇⋂𝑖=1 𝑄 𝑖∣A n s=∑K⊆M(−1)|K|−1|⋂k i∈K Q k i|=∑i|Q i|−∑i<j|Q i∩Q j|+∑i<j<k|Q i∩Q j∩Q k|−⋯+(−1)T−1|⋂i=1 T Q i|

于是就出现了容斥原理的展开形式，因此对这个式子逆向推导

𝐴 𝑛 𝑠=∣𝑇⋃𝑖=1 𝑄 𝑖∣A n s=|⋃i=1 T Q i|

再考虑等式右边的含义，只要满足 1 ∼𝑇 1∼T 任一条件即可，也就是存在两个点同色（不一定相邻）的染色方案数！而我们知道染色方案的全集是 𝑈 U，显然 |𝑈| =𝑚 𝑛|U|=m n. 而转化为补集，就是求两两异色的染色方案数，即 𝐴 𝑛 𝑚 =𝑚!(𝑚−𝑛)!A m n=m!(m−n)!. 因此

𝐴 𝑛 𝑠=𝑚 𝑛−𝐴 𝑛 𝑚 A n s=m n−A m n

解决这道题，我们首先抽象出题目数学形式，然后从题目中信息量最大的条件，𝐹(𝑆)F(S) 函数的定义入手，将其转化为集合的交并补．然后将式子转化为容斥原理的形式，并 逆向推导 出最终的结果．这道题体现的正是容斥原理的逆用．

## 数论中的容斥

使用容斥原理能够巧妙地求解一些数论问题．

### 容斥原理求最大公约数为 k 的数对个数

考虑下面的问题：

求最大公约数为 𝑘 k 的数对个数

设 1 ≤𝑥,𝑦 ≤𝑁 1≤x,y≤N，𝑓(𝑘)f(k) 表示最大公约数为 𝑘 k 的有序数对 (𝑥,𝑦)(x,y) 的个数，求 𝑓(1)f(1) 到 𝑓(𝑁)f(N) 的值．

这道题固然可以用欧拉函数或莫比乌斯反演的方法来做，但是都不如用容斥原理来的简单．

由容斥原理可以得知，先找到所有以 𝑘 k 为 公约数 的数对，再从中剔除所有以 𝑘 k 的倍数为 公约数 的数对，余下的数对就是以 𝑘 k 为 最大公约数 的数对．即 𝑓(𝑘) =f(k)= 以 𝑘 k 为 公约数 的数对个数 −− 以 𝑘 k 的倍数为 公约数 的数对个数．

进一步可发现，以 𝑘 k 的倍数为 公约数 的数对个数等于所有以 𝑘 k 的倍数为 最大公约数 的数对个数之和．于是，可以写出如下表达式：

𝑓(𝑘)=⌊(𝑁/𝑘)⌋2−𝑖∗𝑘≤𝑁∑𝑖=2 𝑓(𝑖∗𝑘)f(k)=⌊(N/k)⌋2−∑i=2 i∗k≤N f(i∗k)

由于当 𝑘 >𝑁/2 k>N/2 时，我们可以直接算出 𝑓(𝑘) =⌊(𝑁/𝑘)⌋2 f(k)=⌊(N/k)⌋2，因此我们可以倒过来，从 𝑓(𝑁)f(N) 算到 𝑓(1)f(1) 就可以了．于是，我们使用容斥原理完成了本题．

    1
    2
    3
    4
    for (long long k = N; k >= 1; k--) {
      f[k] = (N / k) * (N / k);
      for (long long i = k + k; i <= N; i += k) f[k] -= f[i];
    }

上述方法的时间复杂度为 𝑂(∑𝑁 𝑖=1 𝑁/𝑖) =𝑂(𝑁∑𝑁 𝑖=1 1/𝑖) =𝑂(𝑁 l o g⁡𝑁)O(∑i=1 N N/i)=O(N∑i=1 N 1/i)=O(N log⁡N)．

附赠三倍经验供大家练手．

- Luogu P2398 GCD SUM
- Luogu P2158[SDOI2008] 仪仗队
- Luogu P1447[NOI2010] 能量采集

### 容斥原理推导欧拉函数

考虑下面的问题：

欧拉函数公式

求欧拉函数 𝜑(𝑛)φ(n)．其中 𝜑(𝑛) =|{1 ≤𝑥 ≤𝑛|g c d(𝑥,𝑛) =1}|φ(n)=|{1≤x≤n|gcd(x,n)=1}|．

直接计算是 𝑂(𝑛 l o g⁡𝑛)O(n log⁡n) 的，用线性筛是 𝑂(𝑛)O(n) 的，杜教筛是 𝑂(𝑛 2 3)O(n 2 3) 的（话说一道数论入门题用容斥做为什么还要扯到杜教筛上），接下来考虑用容斥推出欧拉函数的公式

判断两个数是否互质，首先分解质因数

𝑛=𝑘∏𝑖=1 𝑝 𝑖 𝑐 𝑖 n=∏i=1 k p i c i

那么就要求对于任意 𝑝 𝑖 p i，𝑥 x 都不是 𝑝 𝑖 p i 的倍数，即 𝑝 𝑖 ∤𝑥 p i∤x. 把它当作属性，对应的集合为 𝑆 𝑖 S i，因此有

𝜑(𝑛)=∣𝑘⋂𝑖=1 𝑆 𝑖∣=|𝑈|−∣𝑘⋃𝑖=1――𝑆 𝑖∣φ(n)=|⋂i=1 k S i|=|U|−|⋃i=1 k S i―|

全集大小 |𝑈| =𝑛|U|=n，而 ――𝑆 𝑖 S i― 表示的是 𝑝 𝑖 ∣𝑥 p i∣x 构成的集合，显然 |――𝑆 𝑖| =𝑛 𝑝 𝑖|S i―|=n p i，并由此推出

∣⋂𝑎 𝑖<𝑎 𝑖+1 𝑆 𝑎 𝑖∣=𝑛∏𝑝 𝑎 𝑖|⋂a i<a i+1 S a i|=n∏p a i

因此可得

𝜑(𝑛)=𝑛−∑𝑖 𝑛 𝑝 𝑖+∑𝑖<𝑗 𝑛 𝑝 𝑖 𝑝 𝑗−⋯+(−1)𝑘 𝑛 𝑝 1 𝑝 2⋯𝑝 𝑘=𝑛(1−1 𝑝 1)(1−1 𝑝 2)⋯(1−1 𝑝 𝑘)=𝑛 𝑘∏𝑖=1(1−1 𝑝 𝑖)φ(n)=n−∑i n p i+∑i<j n p i p j−⋯+(−1)k n p 1 p 2⋯p k=n(1−1 p 1)(1−1 p 2)⋯(1−1 p k)=n∏i=1 k(1−1 p i)

这就是欧拉函数的数学表示啦

## 容斥原理一般化

容斥原理常用于集合的计数问题，而对于两个集合的函数 𝑓(𝑆),𝑔(𝑆)f(S),g(S)，若

𝑓(𝑆)=∑𝑇⊆𝑆 𝑔(𝑇)f(S)=∑T⊆S g(T)

那么就有

𝑔(𝑆)=∑𝑇⊆𝑆(−1)|𝑆|−|𝑇|𝑓(𝑇)g(S)=∑T⊆S(−1)|S|−|T|f(T)

### 证明

接下来我们简单证明一下．我们从等式的右边开始推：

∑𝑇⊆𝑆(−1)|𝑆|−|𝑇|𝑓(𝑇)=∑𝑇⊆𝑆(−1)|𝑆|−|𝑇|∑𝑄⊆𝑇 𝑔(𝑄)=∑𝑄 𝑔(𝑄)∑𝑄⊆𝑇⊆𝑆(−1)|𝑆|−|𝑇|∑T⊆S(−1)|S|−|T|f(T)=∑T⊆S(−1)|S|−|T|∑Q⊆T g(Q)=∑Q g(Q)∑Q⊆T⊆S(−1)|S|−|T|

我们发现后半部分的求和与 𝑄 Q 无关，因此把后半部分的 𝑄 Q 剔除：

=∑𝑄 𝑔(𝑄)∑𝑇⊆(𝑆∖𝑄)(−1)|𝑆∖𝑄|−|𝑇|=∑Q g(Q)∑T⊆(S∖Q)(−1)|S∖Q|−|T|

记关于集合 𝑃 P 的函数 𝐹(𝑃) =∑𝑇⊆𝑃( −1)|𝑃|−|𝑇|F(P)=∑T⊆P(−1)|P|−|T|，并化简这个函数：

𝐹(𝑃)=∑𝑇⊆𝑃(−1)|𝑃|−|𝑇|=|𝑃|∑𝑖=0(|𝑃|𝑖)(−1)|𝑃|−𝑖=|𝑃|∑𝑖=0(|𝑃|𝑖)1 𝑖(−1)|𝑃|−𝑖=(1−1)|𝑃|=0|𝑃|F(P)=∑T⊆P(−1)|P|−|T|=∑i=0|P|(|P|i)(−1)|P|−i=∑i=0|P|(|P|i)1 i(−1)|P|−i=(1−1)|P|=0|P|

因此原来的式子的值是

∑𝑄 𝑔(𝑄)∑𝑇⊆(𝑆∖𝑄)(−1)|𝑆∖𝑄|−|𝑇|=∑𝑄 𝑔(𝑄)𝐹(𝑆∖𝑄)=∑𝑄 𝑔(𝑄)⋅0|𝑆∖𝑄|∑Q g(Q)∑T⊆(S∖Q)(−1)|S∖Q|−|T|=∑Q g(Q)F(S∖Q)=∑Q g(Q)⋅0|S∖Q|

分析发现，仅当 |𝑆 ∖𝑄| =0|S∖Q|=0 时有 0 0 =1 0 0=1，这时 𝑄 =𝑆 Q=S，对答案的贡献就是 𝑔(𝑆)g(S)，其他时侯 0|𝑆∖𝑄| =0 0|S∖Q|=0，则对答案无贡献．于是得到

∑𝑄 𝑔(𝑄)⋅0|𝑆∖𝑄|=𝑔(𝑆)∑Q g(Q)⋅0|S∖Q|=g(S)

综上所述，得证．

### 推论

该形式还有这样一个推论．在全集 𝑈 U 下，对于函数 𝑓(𝑆),𝑔(𝑆)f(S),g(S)，如果

𝑓(𝑆)=∑𝑆⊆𝑇 𝑔(𝑇)f(S)=∑S⊆T g(T)

那么

𝑔(𝑆)=∑𝑆⊆𝑇(−1)|𝑇|−|𝑆|𝑓(𝑇)g(S)=∑S⊆T(−1)|T|−|S|f(T)

这个推论其实就是补集形式，证法类似．

## DAG 计数

DAG 计数

对 𝑛 n 个点带标号的有向无环图进行计数，对 1 0 9 +7 10 9+7 取模．𝑛 ≤5 ×1 0 3 n≤5×10 3．

### 直接 DP

考虑 DP，定义 𝑓[𝑖,𝑗]f[i,j] 表示 𝑖 i 个点的 DAG，有 𝑗 j 点个入度为 0 0 的图的个数．假设去掉这 𝑗 j 个点后，有 𝑘 k 个点入度为 0 0，那么在去掉前这 𝑘 k 个点至少与这 𝑗 j 个点中的某几个有连边，即 2 𝑗 −1 2 j−1 种情况；而这 𝑗 j 个点除了与 𝑘 k 个点连边，还可以与剩下的点任意连边，有 2 𝑖−𝑗−𝑘 2 i−j−k 种情况．因此方程如下：

𝑓[𝑖,𝑗]=(𝑖 𝑗)𝑖−𝑗∑𝑘=1(2 𝑗−1)𝑘 2(𝑖−𝑗−𝑘)𝑗 𝑓[𝑖−𝑗,𝑘]f[i,j]=(i j)∑k=1 i−j(2 j−1)k 2(i−j−k)j f[i−j,k]

计算上式的复杂度是 𝑂(𝑛 3)O(n 3) 的．

### 放宽限制

上述 DP 的定义是恰好 𝑗 j 个点入度为 0 0, 太过于严格，可以放宽为至少 𝑗 j 个点入度为 0 0．直接定义 𝑓[𝑖]f[i] 表示 𝑖 i 个点的 DAG 个数．可以直接容斥．考虑选出的 𝑗 j 个点，这 𝑗 j 个点可以和剩下的 𝑖 −𝑗 i−j 个点有任意的连边，即 (2 𝑖−𝑗)𝑗 =2(𝑖−𝑗)𝑗(2 i−j)j=2(i−j)j 种情况：

𝑓[𝑖]=𝑖∑𝑗=1(−1)𝑗−1(𝑖 𝑗)2(𝑖−𝑗)𝑗 𝑓[𝑖−𝑗]f[i]=∑j=1 i(−1)j−1(i j)2(i−j)j f[i−j]

计算上式的复杂度是 𝑂(𝑛 2)O(n 2) 的．

## Min-max 容斥

对于满足 全序 关系并且其中元素满足可加减性的序列 {𝑥 𝑖}{x i}，设其长度为 𝑛 n，并设 𝑆 ={1,2,3,⋯,𝑛}S={1,2,3,⋯,n}，则有：

m a x 𝑖∈𝑆 𝑥 𝑖=∑𝑇⊆𝑆(−1)|𝑇|−1 m i n 𝑗∈𝑇 𝑥 𝑗 max i∈S x i=∑T⊆S(−1)|T|−1 min j∈T x j m i n 𝑖∈𝑆 𝑥 𝑖=∑𝑇⊆𝑆(−1)|𝑇|−1 m a x 𝑗∈𝑇 𝑥 𝑗 min i∈S x i=∑T⊆S(−1)|T|−1 max j∈T x j

证明： 考虑做一个到一般容斥原理的映射．对于 𝑥 ∈𝑆 x∈S，假设 𝑥 x 是第 𝑘 k 小的元素．那么我们定义一个映射 𝑓 :𝑥 ↦{1,2,⋯,𝑘}f:x↦{1,2,⋯,k}．显然这是一个双射．

那么容易发现，对于 𝑥,𝑦 ∈𝑆 x,y∈S，𝑓(m i n(𝑥,𝑦)) =𝑓(𝑥) ∩𝑓(𝑦)f(min(x,y))=f(x)∩f(y)，𝑓(m a x(𝑥,𝑦)) =𝑓(𝑥) ∪𝑓(𝑦)f(max(x,y))=f(x)∪f(y)．因此我们得到：

∣𝑓(m a x 𝑖∈𝑆 𝑥 𝑖)∣=∣⋃𝑖∈𝑆 𝑓(𝑥 𝑖)∣=∑𝑇⊆𝑆(−1)|𝑇|−1∣⋂𝑗∈𝑇 𝑓(𝑥 𝑗)∣=∑𝑇⊆𝑆(−1)|𝑇|−1∣𝑓(m i n 𝑗∈𝑇 𝑥 𝑗)∣|f(max i∈S x i)|=|⋃i∈S f(x i)|=∑T⊆S(−1)|T|−1|⋂j∈T f(x j)|=∑T⊆S(−1)|T|−1|f(min j∈T x j)|

然后再把 |𝑓(m a x 𝑖∈𝑆 𝑥 𝑖)||f(max i∈S x i)| 映射回 m a x 𝑖∈𝑆 𝑥 𝑖 max i∈S x i，而 m i n min 是类似的．

证毕．

但是你可能觉得这个式子非常蠢，最大值明明可以直接求．之所以 min-max 容斥这么重要，是因为它在期望上也是成立的，即：

𝐸(m a x 𝑖∈𝑆 𝑥 𝑖)=∑𝑇⊆𝑆(−1)|𝑇|−1 𝐸(m i n 𝑗∈𝑇 𝑥 𝑗)E(max i∈S x i)=∑T⊆S(−1)|T|−1 E(min j∈T x j)𝐸(m i n 𝑖∈𝑆 𝑥 𝑖)=∑𝑇⊆𝑆(−1)|𝑇|−1 𝐸(m a x 𝑗∈𝑇 𝑥 𝑗)E(min i∈S x i)=∑T⊆S(−1)|T|−1 E(max j∈T x j)

证明： 我们考虑计算期望的一种方法：

𝐸(m a x 𝑖∈𝑆 𝑥 𝑖)=∑𝑦 𝑃(𝑦=𝑥)m a x 𝑗∈𝑆 𝑦 𝑗 E(max i∈S x i)=∑y P(y=x)max j∈S y j

其中 𝑦 y 是一个长度为 𝑛 n 的序列．

我们对后面的 m a x max 使用之前的式子：

𝐸(m a x 𝑖∈𝑆 𝑥 𝑖)=∑𝑦 𝑃(𝑦=𝑥)m a x 𝑗∈𝑆 𝑦 𝑗=∑𝑦 𝑃(𝑦=𝑥)∑𝑇⊆𝑆(−1)|𝑇|−1 m i n 𝑗∈𝑇 𝑦 𝑗 E(max i∈S x i)=∑y P(y=x)max j∈S y j=∑y P(y=x)∑T⊆S(−1)|T|−1 min j∈T y j

调换求和顺序：

𝐸(m a x 𝑖∈𝑆 𝑥 𝑖)=∑𝑦 𝑃(𝑦=𝑥)∑𝑇⊆𝑆(−1)|𝑇|−1 m i n 𝑗∈𝑇 𝑦 𝑗=∑𝑇⊆𝑆(−1)|𝑇|−1∑𝑦 𝑃(𝑦=𝑥)m i n 𝑗∈𝑇 𝑦 𝑗=∑𝑇⊆𝑆(−1)|𝑇|−1 𝐸(m i n 𝑗∈𝑇 𝑦 𝑗)E(max i∈S x i)=∑y P(y=x)∑T⊆S(−1)|T|−1 min j∈T y j=∑T⊆S(−1)|T|−1∑y P(y=x)min j∈T y j=∑T⊆S(−1)|T|−1 E(min j∈T y j)

m i n min 是类似的．

证毕．

还有更强的：

k t h m a x⁡𝑥 𝑖 𝑖∈𝑆=∑𝑇⊆𝑆(−1)|𝑇|−𝑘(|𝑇|−1 𝑘−1)m i n 𝑗∈𝑇 𝑥 𝑗 kthmax⁡x i i∈S=∑T⊆S(−1)|T|−k(|T|−1 k−1)min j∈T x j k t h m i n⁡𝑥 𝑖 𝑖∈𝑆=∑𝑇⊆𝑆(−1)|𝑇|−𝑘(|𝑇|−1 𝑘−1)m a x 𝑗∈𝑇 𝑥 𝑗 kthmin⁡x i i∈S=∑T⊆S(−1)|T|−k(|T|−1 k−1)max j∈T x j 𝐸(k t h m a x⁡𝑥 𝑖 𝑖∈𝑆)=∑𝑇⊆𝑆(−1)|𝑇|−𝑘(|𝑇|−1 𝑘−1)𝐸(m i n 𝑗∈𝑇 𝑥 𝑗)E(kthmax⁡x i i∈S)=∑T⊆S(−1)|T|−k(|T|−1 k−1)E(min j∈T x j)𝐸(k t h m i n⁡𝑥 𝑖 𝑖∈𝑆)=∑𝑇⊆𝑆(−1)|𝑇|−𝑘(|𝑇|−1 𝑘−1)𝐸(m a x 𝑗∈𝑇 𝑥 𝑗)E(kthmin⁡x i i∈S)=∑T⊆S(−1)|T|−k(|T|−1 k−1)E(max j∈T x j)

规定若 𝑛 <𝑚 n<m，则 (𝑛 𝑚) =0(n m)=0．

证明： 不妨设 ∀1 ≤𝑖 <𝑛,𝑥 𝑖 ≤𝑥 𝑖+1∀1≤i<n,x i≤x i+1．则有：

∑𝑇⊆𝑆(−1)|𝑇|−𝑘(|𝑇|−1 𝑘−1)m i n 𝑗∈𝑇 𝑥 𝑗=∑𝑖∈𝑆 𝑥 𝑖∑𝑇⊆𝑆(−1)|𝑇|−𝑘(|𝑇|−1 𝑘−1)[𝑥 𝑖=m i n 𝑗∈𝑇 𝑥 𝑗]=∑𝑖∈𝑆 𝑥 𝑖 𝑛∑𝑗=𝑘(𝑛−𝑖 𝑗−1)(𝑗−1 𝑘−1)(−1)𝑗−𝑘∑T⊆S(−1)|T|−k(|T|−1 k−1)min j∈T x j=∑i∈S x i∑T⊆S(−1)|T|−k(|T|−1 k−1)[x i=min j∈T x j]=∑i∈S x i∑j=k n(n−i j−1)(j−1 k−1)(−1)j−k

又因为有组合恒等式：(𝑎 𝑏)(𝑏 𝑐) =(𝑎 𝑐)(𝑎−𝑐 𝑏−𝑐)(a b)(b c)=(a c)(a−c b−c)，所以有：

∑𝑇⊆𝑆(−1)|𝑇|−𝑘(|𝑇|−1 𝑘−1)m i n 𝑗∈𝑇 𝑥 𝑗=∑𝑖∈𝑆 𝑥 𝑖 𝑛∑𝑗=𝑘(𝑛−𝑖 𝑗−1)(𝑗−1 𝑘−1)(−1)𝑗−𝑘=∑𝑖∈𝑆 𝑥 𝑖 𝑛∑𝑗=𝑘(𝑛−𝑖 𝑘−1)(𝑛−𝑖−𝑘+1 𝑗−𝑘)(−1)𝑗−𝑘=∑𝑖∈𝑆(𝑛−𝑖 𝑘−1)𝑥 𝑖 𝑛∑𝑗=𝑘(𝑛−𝑖−𝑘+1 𝑗−𝑘)(−1)𝑗−𝑘=∑𝑖∈𝑆(𝑛−𝑖 𝑘−1)𝑥 𝑖 𝑛−𝑖−𝑘+1∑𝑗=0(𝑛−𝑖−𝑘+1 𝑗)(−1)𝑗∑T⊆S(−1)|T|−k(|T|−1 k−1)min j∈T x j=∑i∈S x i∑j=k n(n−i j−1)(j−1 k−1)(−1)j−k=∑i∈S x i∑j=k n(n−i k−1)(n−i−k+1 j−k)(−1)j−k=∑i∈S(n−i k−1)x i∑j=k n(n−i−k+1 j−k)(−1)j−k=∑i∈S(n−i k−1)x i∑j=0 n−i−k+1(n−i−k+1 j)(−1)j

当 𝑖 =𝑛 −𝑘 +1 i=n−k+1 时：

(𝑛−𝑖 𝑘−1)𝑛−𝑖−𝑘+1∑𝑗=0(𝑛−𝑖−𝑘+1 𝑗)(−1)𝑗=1(n−i k−1)∑j=0 n−i−k+1(n−i−k+1 j)(−1)j=1

否则：

(𝑛−𝑖 𝑘−1)𝑛−𝑖−𝑘+1∑𝑗=0(𝑛−𝑖−𝑘+1 𝑗)(−1)𝑗=0(n−i k−1)∑j=0 n−i−k+1(n−i−k+1 j)(−1)j=0

所以：

∑𝑖∈𝑆(𝑛−𝑖 𝑘−1)𝑥 𝑖 𝑛−𝑖−𝑘+1∑𝑗=0(𝑛−𝑖−𝑘+1 𝑗)(−1)𝑗=k t h m a x 𝑖∈𝑆 𝑥 𝑖∑i∈S(n−i k−1)x i∑j=0 n−i−k+1(n−i−k+1 j)(−1)j=kthmax i∈S x i

剩下三个是类似的．

证毕．

根据 min-max 容斥，我们还可以得到下面的式子：

l c m 𝑖∈𝑆 𝑥 𝑖=∏𝑇⊆𝑆(g c d 𝑗∈𝑇 𝑥 𝑗)(−1)|𝑇|−1 lcm i∈S x i=∏T⊆S(gcd j∈T x j)(−1)|T|−1

因为 l c m,g c d,𝑎 1,𝑎−1 lcm,gcd,a 1,a−1 分别相当于 m a x,m i n, +, −max,min,+,−，就是说相当于对于指数做了一个 min-max 容斥，自然就是对的了

## PKUWC2018 随机游走

PKUWC2018 随机游走

给定一棵 𝑛 n 个点的树，你从 𝑥 x 出发，每次等概率随机选择一条与所在点相邻的边走过去．

有 𝑄 Q 次询问．每次询问给出一个集合 𝑆 S，求如果从 𝑥 x 出发一直随机游走，直到点集 𝑆 S 中的点都至少经过一次的话，期望游走几步．

特别地，点 𝑥 x（即起点）视为一开始就被经过了一次．

对 9 9 8 2 4 4 3 5 3 998244353 取模．

1 ≤𝑛 ≤1 8,1 ≤𝑄 ≤5 0 0 0,1 ≤|𝑆| ≤𝑛 1≤n≤18,1≤Q≤5000,1≤|S|≤n．

期望游走的步数也就是游走的时间．那么设随机变量 𝑥 𝑖 x i 表示第一次走到结点 𝑖 i 的时间．那么我们要求的就是

𝐸(m a x 𝑖∈𝑆 𝑥 𝑖)E(max i∈S x i)

使用 min-max 容斥可以得到

𝐸(m a x 𝑖∈𝑆 𝑥 𝑖)=𝐸(∑𝑇⊆𝑆(−1)|𝑇|−1 m i n 𝑖∈𝑇 𝑥 𝑖)=∑𝑇⊆𝑆(−1)|𝑇|−1 𝐸(m i n 𝑖∈𝑇 𝑥 𝑖)E(max i∈S x i)=E(∑T⊆S(−1)|T|−1 min i∈T x i)=∑T⊆S(−1)|T|−1 E(min i∈T x i)

对于一个集合 𝑇 ∈[𝑛]T∈[n]，考虑求出 𝐹(𝑇) =𝐸(m i n 𝑖∈𝑇 𝑥 𝑖)F(T)=E(min i∈T x i)．

考虑 𝐸(m i n 𝑖∈𝑇 𝑥 𝑖)E(min i∈T x i) 的含义，是第一次走到 𝑇 T 中某一个点的期望时间．不妨设 𝑓(𝑖)f(i) 表示从结点 𝑖 i 出发，第一次走到 𝑇 T 中某个结点的期望时间．

- 对于 𝑖 ∈𝑇 i∈T，有 𝑓(𝑖) =0 f(i)=0．
- 对于 𝑖 ∉𝑇 i∉T，有 𝑓(𝑖) =1 +1 d e g(𝑖)∑(𝑖,𝑗)∈𝐸 𝑓(𝑗)f(i)=1+1 deg(i)∑(i,j)∈E f(j)．

如果直接高斯消元，复杂度 𝑂(𝑛 3)O(n 3)．那么我们对每个 𝑇 T 都计算 𝐹(𝑇)F(T) 的总复杂度就是 𝑂(2 𝑛 𝑛 3)O(2 n n 3)，不能接受．我们使用树上消元的技巧．

不妨设根结点是 1 1，结点 𝑢 u 的父亲是 𝑝 𝑢 p u．对于叶子结点 𝑖 i，𝑓(𝑖)f(i) 只会和 𝑖 i 的父亲有关（也可能 𝑓(𝑖) =0 f(i)=0，那样更好）．因此我们可以把 𝑓(𝑖)f(i) 表示成 𝑓(𝑖) =𝐴 𝑖 +𝐵 𝑖 𝑓(𝑝 𝑖)f(i)=A i+B i f(p i) 的形式，其中 𝐴 𝑖,𝐵 𝑖 A i,B i 可以快速计算．

对于非叶结点 𝑖 i，考虑它的儿子序列 𝑗 1,⋯,𝑗 𝑘 j 1,⋯,j k．由于 𝑓(𝑗 𝑒) =𝐴 𝑗 𝑒 +𝐵 𝑗 𝑒 𝑓(𝑖)f(j e)=A j e+B j e f(i)．因此可以得到

𝑓(𝑖)=1+1 d e g⁡(𝑖)𝑘∑𝑒=1(𝐴 𝑗 𝑒+𝐵 𝑗 𝑒 𝑓(𝑖))+𝑓(𝑝 𝑖)d e g⁡(𝑖)f(i)=1+1 deg⁡(i)∑e=1 k(A j e+B j e f(i))+f(p i)deg⁡(i)

那么变换一下可以得到

𝑓(𝑖)=d e g⁡(𝑖)+∑𝑘 𝑒=1 𝐴 𝑗 𝑒 d e g⁡(𝑖)−∑𝑘 𝑒=1 𝐵 𝑗 𝑒+𝑓(𝑝 𝑖)d e g⁡(𝑖)−∑𝑘 𝑒=1 𝐵 𝑗 𝑒 f(i)=deg⁡(i)+∑e=1 k A j e deg⁡(i)−∑e=1 k B j e+f(p i)deg⁡(i)−∑e=1 k B j e

于是我们把 𝑓(𝑖)f(i) 也写成了 𝐴 𝑖 +𝐵 𝑖 𝑓(𝑝 𝑖)A i+B i f(p i) 的形式．这样可以一直倒推到根结点．而根结点没有父亲．也就是说

𝑓(1)=d e g⁡(1)+∑𝑘 𝑒=1 𝐴 𝑗 𝑒 d e g⁡(1)−∑𝑘 𝑒=1 𝐵 𝑗 𝑒 f(1)=deg⁡(1)+∑e=1 k A j e deg⁡(1)−∑e=1 k B j e

解一下这个方程我们就得到了 𝑓(1)f(1)，再从上往下推一次就得到了每个点的 𝑓(𝑖)f(i)．那么 𝐹(𝑇) =𝑓(𝑥)F(T)=f(x)．时间复杂度 𝑂(𝑛)O(n)．

这样，我们可以对于每一个 𝑇 T 计算出 𝐹(𝑇)F(T)，时间复杂度 𝑂(2 𝑛 𝑛)O(2 n n)．

回到容斥的部分，我们知道 𝐸(m a x 𝑖∈𝑆 𝑥 𝑖) =∑𝑇⊆𝑆( −1)|𝑇|−1 𝐹(𝑇)E(max i∈S x i)=∑T⊆S(−1)|T|−1 F(T)．

不妨设 𝐹′(𝑇) =( −1)|𝑇|−1 𝐹(𝑇)F′(T)=(−1)|T|−1 F(T)，那么进一步得到 𝐸(m a x 𝑖∈𝑆 𝑥 𝑖) =∑𝑇⊆𝑆 𝐹′(𝑇)E(max i∈S x i)=∑T⊆S F′(T)．因此可以使用 FMT（也叫子集前缀和，或者 FWT 或变换）在 𝑂(2 𝑛 𝑛)O(2 n n) 的时间内对每个 𝑆 S 计算出 𝐸(m a x 𝑖∈𝑆 𝑥 𝑖)E(max i∈S x i)，这样就可以 𝑂(1)O(1) 回答询问了．

### 习题

- ABC331- G - Collect Them All
- 洛谷 P4707 重返现世

## 参考文献

浅探容斥原理 - 王迪，2013 年信息学奥林匹克中国国家队候选队员论文集

有标号的 DAG 计数系列问题 - Cyhlnj

全序关系 - Wikipedia

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Ir1d, sshwy, Tiphereth-A, Enter-tainer, Great-designer, MegaOwIer, Peanut-Tang, HeRaNO, Xeonacid, c-forrest, CCXXXI, Chrogeek, ComeIntoCalm, hsfzLZH1, iamtwz, Jerrycyx, Jiangkangping, kenlig, ksyx, Lumos-exe, lychees, megakite, ouuan, sbofgayschool, ShizuhaAki, StableAgOH, StudyingFather, tder6, untitledunrevised, UserUnauthorized, ZYStream
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用