容斥原理 引入 入门例题 假设班里有 个学生喜欢数学, 个学生喜欢语文, 个学生喜欢编程,班里至少喜欢一门学科的有多少个学生呢?
是 个吗?不是的,因为有些学生可能同时喜欢数学和语文,或者语文和编程,甚至还有可能三者都喜欢。
为了叙述方便,我们把喜欢语文、数学、编程的学生集合分别用 表示,则学生总数等于 。刚才已经讲过,如果把这三个集合的元素个数 直接加起来,会有一些元素重复统计了,因此需要扣掉 ,但这样一来,又有一小部分多扣了,需要加回来,即 。即
把上述问题推广到一般情况,就是我们熟知的容斥原理。
定义 设 U 中元素有 n 种不同的属性,而第 i 种属性称为 ,拥有属性 的元素构成集合 ,那么
即
证明 对于每个元素使用二项式定理计算其出现的次数。对于元素 x,假设它出现在 的集合中,那么它的出现次数为
于是每个元素出现的次数为 1,那么合并起来就是并集。证毕。
补集 对于全集 U 下的 集合的并 可以使用容斥原理计算,而集合的交则用全集减去 补集的并集 求得:
右边使用容斥即可。
可能接触过容斥的读者都清楚上述内容,而更关心的是容斥的应用。
那么接下来我们给出 3 个层次不同的例题来为大家展示容斥原理的应用。
不定方程非负整数解计数 不定方程非负整数解计数 给出不定方程 和 个限制条件 ,其中 . 求方程的非负整数解的个数。
没有限制时 如果没有 的限制,那么不定方程 的非负整数解的数目为 .
略证:插板法。
相当于你有 个球要分给 个盒子,允许某个盒子是空的。这个问题不能直接用组合数解决。
于是我们再加入 个球,于是问题就变成了在一个长度为 的球序列中选择 个球,然后这个 个球把这个序列隔成了 份,恰好可以一一对应放到 个盒子中。那么在 个球中选择 个球的方案数就是 。
容斥模型 接着我们尝试抽象出容斥原理的模型:
全集 U:不定方程 的非负整数解 元素:变量 . 属性: 的属性即 满足的条件,即 的条件 目标:所有变量满足对应属性时集合的大小,即 .
这个东西可以用 求解。 可以用组合数计算,后半部分自然使用容斥原理展开。
那么问题变成,对于一些 的交集求大小。考虑 的含义,表示 的解的数目。而交集表示同时满足这些条件。因此这个交集对应的不定方程中,有些变量有 下界限制 ,而有些则没有限制。
能否消除这些下界限制呢?既然要求的是非负整数解,而有些变量的下界又大于 ,那么我们直接 把这个下界减掉 ,就可以使得这些变量的下界变成 ,即没有下界啦。因此对于
的不定方程形式为
于是这个也可以组合数计算啦。这个长度为 的 数组相当于在枚举子集。
HAOI2008 硬币购物 HAOI2008 硬币购物 4 种面值的硬币,第 i 种的面值是 。 次询问,每次询问给出每种硬币的数量 和一个价格 ,问付款方式。
.
如果用背包做的话复杂度是 ,无法承受。这道题最明显的特点就是硬币一共只有四种。抽象模型,其实就是让我们求方程 的非负整数解的个数。
采用同样的容斥方式, 的属性为 . 套用容斥原理的公式,最后我们要求解
也就是无限背包问题。这个问题可以预处理,算上询问,总复杂度 。
代码实现 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 玩游戏,对于 阶 完全图 。他们定义一个估价函数 ,其中 S 是边集, . 的值是对图 用 种颜色染色的总方案数。他们的另一个规则是,如果 是奇数,那么 A 的得分增加 ,否则 B 的得分增加 . 问 A 和 B 的得分差值。
数学形式 一看这道题的算法趋向并不明显,因此对于棘手的题目首先抽象出数学形式。得分差即为奇偶对称差,可以用 -1 的幂次来作为系数。我们求的是
容斥模型 相邻结点染同一种颜色,我们把它当作属性。在这里我们先不遵守染色的规则,假定我们用 m 种颜色直接对图染色。对于图 ,我们把它当作 元素 。属性 的含义是结点 i,j 染同色(注意,并未要求 i,j 之间有连边)。
而属性 对应的 集合 定义为 ,其含义是所有满足该属性的图 的染色方案,集合的大小就是满足该属性的染色方案数,集合内的元素相当于所有满足该属性的图 的染色图。
回到题目,「相邻的结点必须染同一种颜色」,可以理解为若干个 集合的交集。因此可以写出
上述式子右边的含义就是说对于 S 内的每一条边 都满足 的染色方案数,也就是 .
是不是很有容斥的味道了?由于容斥原理本身没有二元组的形式,因此我们把 所有 的边 映射到 个整数上,假设将 映射为 ,同时 映射为 . 那么属性 则定义为 .
同时 S 可以表示为若干个 k 组成的集合,即 .(也就是说我们在边集与数集间建立了等价关系)。
而 E 对应集合 . 于是乎
逆向分析 那么要求的式子展开
于是就出现了容斥原理的展开形式,因此对这个式子逆向推导
再考虑等式右边的含义,只要满足 任一条件即可,也就是存在两个点同色(不一定相邻)的染色方案数!而我们知道染色方案的全集是 ,显然 . 而转化为补集,就是求两两异色的染色方案数,即 . 因此
解决这道题,我们首先抽象出题目数学形式,然后从题目中信息量最大的条件, 函数的定义入手,将其转化为集合的交并补。然后将式子转化为容斥原理的形式,并 逆向推导 出最终的结果。这道题体现的正是容斥原理的逆用。
数论中的容斥 使用容斥原理能够巧妙地求解一些数论问题。
容斥原理求最大公约数为 k 的数对个数 考虑下面的问题:
求最大公约数为 的数对个数 设 , 表示最大公约数为 的有序数对 的个数,求 到 的值。
这道题固然可以用欧拉函数或莫比乌斯反演的方法来做,但是都不如用容斥原理来的简单。
由容斥原理可以得知,先找到所有以 为 公约数 的数对,再从中剔除所有以 的倍数为 公约数 的数对,余下的数对就是以 为 最大公约数 的数对。即 以 为 公约数 的数对个数 以 的倍数为 公约数 的数对个数。
进一步可发现,以 的倍数为 公约数 的数对个数等于所有以 的倍数为 最大公约数 的数对个数之和。于是,可以写出如下表达式:
由于当 时,我们可以直接算出 ,因此我们可以倒过来,从 算到 就可以了。于是,我们使用容斥原理完成了本题。
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 ];
}
上述方法的时间复杂度为 。
附赠三倍经验供大家练手。
容斥原理推导欧拉函数 考虑下面的问题:
欧拉函数公式 求欧拉函数 。其中 。
直接计算是 的,用线性筛是 的,杜教筛是 的(话说一道数论入门题用容斥做为什么还要扯到杜教筛上),接下来考虑用容斥推出欧拉函数的公式
判断两个数是否互质,首先分解质因数
那么就要求对于任意 , 都不是 的倍数,即 . 把它当作属性,对应的集合为 ,因此有
全集大小 ,而 表示的是 构成的集合,显然 ,并由此推出
因此可得
这就是欧拉函数的数学表示啦
容斥原理一般化 容斥原理常用于集合的计数问题,而对于两个集合的函数 ,若
那么就有
证明 接下来我们简单证明一下。我们从等式的右边开始推:
我们发现后半部分的求和与 无关,因此把后半部分的 剔除:
记关于集合 的函数 ,并化简这个函数:
因此原来的式子的值是
分析发现,仅当 时有 ,这时 ,对答案的贡献就是 ,其他时侯 ,则对答案无贡献。于是得到
综上所述,得证。
推论 该形式还有这样一个推论。在全集 下,对于函数 ,如果
那么
这个推论其实就是补集形式,证法类似。
DAG 计数 DAG 计数 对 个点带标号的有向无环图进行计数,对 取模。 。
直接 DP 考虑 DP,定义 表示 个点的 DAG,有 点个入度为 的图的个数。假设去掉这 个点后,有 个点入度为 ,那么在去掉前这 个点至少与这 个点中的某几个有连边,即 种情况;而这 个点除了与 个点连边,还可以与剩下的点任意连边,有 种情况。因此方程如下:
计算上式的复杂度是 的。
放宽限制 上述 DP 的定义是恰好 个点入度为 , 太过于严格,可以放宽为至少 个点入度为 。直接定义 表示 个点的 DAG 个数。可以直接容斥。考虑选出的 个点,这 个点可以和剩下的 个点有任意的连边,即 种情况:
计算上式的复杂度是 的。
Min-max 容斥 对于满足 全序 关系并且其中元素满足可加减性的序列 ,设其长度为 ,并设 ,则有:
证明: 考虑做一个到一般容斥原理的映射。对于 ,假设 是第 大的元素。那么我们定义一个映射 。显然这是一个双射。
那么容易发现,对于 , , 。因此我们得到:
然后再把 映射回 ,而 是类似的。
证毕
但是你可能觉得这个式子非常蠢,最大值明明可以直接求。之所以 min-max 容斥这么重要,是因为它在期望上也是成立的,即:
证明: 我们考虑计算期望的一种方法:
其中 是一个长度为 的序列。
我们对后面的 使用之前的式子:
调换求和顺序:
是类似的。
证毕
还有更强的:
规定若 ,则 。
证明: 不妨设 。则有:
又因为有组合恒等式: ,所以有:
当 时:
否则:
所以:
剩下三个是类似的。
证毕
根据 min-max 容斥,我们还可以得到下面的式子:
因为 分别相当于 ,就是说相当于对于指数做了一个 min-max 容斥,自然就是对的了
PKUWC2018 随机游走 PKUWC2018 随机游走 给定一棵 个点的树,你从 出发,每次等概率随机选择一条与所在点相邻的边走过去。
有 次询问。每次询问给出一个集合 ,求如果从 出发一直随机游走,直到点集 中的点都至少经过一次的话,期望游走几步。
特别地,点 (即起点)视为一开始就被经过了一次。
对 取模。
。
期望游走的步数也就是游走的时间。那么设随机变量 表示第一次走到结点 的时间。那么我们要求的就是
使用 min-max 容斥可以得到
对于一个集合 ,考虑求出 。
考虑 的含义,是第一次走到 中某一个点的期望时间。不妨设 表示从结点 出发,第一次走到 中某个结点的期望时间。
如果直接高斯消元,复杂度 。那么我们对每个 都计算 的总复杂度就是 ,不能接受。我们使用树上消元的技巧。
不妨设根结点是 ,结点 的父亲是 。对于叶子结点 , 只会和 的父亲有关(也可能 ,那样更好)。因此我们可以把 表示成 的形式,其中 可以快速计算。
对于非叶结点 ,考虑它的儿子序列 。由于 。因此可以得到
那么变换一下可以得到
于是我们把 也写成了 的形式。这样可以一直倒推到根结点。而根结点没有父亲。也就是说
解一下这个方程我们就得到了 ,再从上往下推一次就得到了每个点的 。那么 。时间复杂度 。
这样,我们可以对于每一个 计算出 ,时间复杂度 。
回到容斥的部分,我们知道 。
不妨设 ,那么进一步得到 。因此可以使用 FMT(也叫子集前缀和,或者 FWT 或变换)在 的时间内对每个 计算出 ,这样就可以 回答询问了。
习题 参考文献 王迪《容斥原理》,2013 年信息学奥林匹克中国国家队候选队员论文集
Cyhlnj《有标号的 DAG 计数系列问题》
Wikipedia - 全序关系
本页面最近更新:2024/4/29 08:59:48 ,更新历史 发现错误?想一起完善? 在 GitHub 上编辑此页! 本页面贡献者:CCXXXI , ComeIntoCalm , dkz051 , Enter-tainer , Great-designer , hsfzLZH1 , iamtwz , Ir1d , Jiangkangping , kenlig , lychees , megakite , MegaOwIer , ouuan , Peanut-Tang , sbofgayschool , ShizuhaAki , sshwy , StableAgOH , tder6 , Tiphereth-A , Xeonacid 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用