容斥原理入门

摘要

啃论文系列~

考容斥原理本身的题不多,容斥原理常用于某个算法部分的求值。

2019.6.16 编入精选文章。

入门

某班有 a 歌人擅长唱歌,b 个人擅长画画,c 个人既擅长唱歌也擅长画画,问有多少人至少有一种擅长?

发挥你聪明的大脑思考这个问题,你在草稿本上画了一个Vann图,发现,没错答案就是 a+b-c!

这背后体现的一个惊世骇俗的原理叫人闻风丧胆——

容斥原理

设 U 中元素有 n 种不同的属性,而第 i 种属性称为 ,拥有属性 的元素构成集合 ,那么

证明

对于每个元素使用二项式定理计算其出现的次数。对于元素 x,假设它出现在 的集合中,那么它的出现次数为

证毕。

补集

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

右边使用容斥即可。

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

不定方程非负整数解计数

给出不定方程 和 n 个限制条件 ,其中 . 求方程的非负整数解的个数

没有限制时

不定方程 的非负整数解的数目为

略证:插板法。

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

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

容斥模型

尝试抽象出容斥原理的模型

  1. 全集 U:不定方程 的非负整数解。
  2. 元素:变量
  3. 属性: 的属性即 满足的条件,即 的条件。

目标:所有变量满足对应属性时集合的大小,即

这个东西可以用 求解。 可以用组合数计算,后半部分自然使用容斥原理展开。

那么问题变成,对于一些特定的 的交集求大小。考虑 的含义,表示 的解的数目。而交集表示同时满足这些条件。因此这个交集对应的不定方程中,有些变量有下界限制,而有些则没有限制。

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

的不定方程形式为

于是这个也可以组合数计算啦

HAOI2008 硬币购物

4 种面值的硬币,第 i 种的面值是 。n 次询问,每次询问给出每种硬币的数量 和一个价格 ,问付款方式。

.

如果用背包做的话复杂度是 ,无法承受。这道题最明显的特点就是硬币一共只有四种。抽象模型,其实就是让我们求方程 的非负整数解的个数。

采用同样的容斥方式, 的属性为 . 套用容斥原理的公式,最后我们要求解

也就是无限背包问题。这个问题可以预处理,算上询问,总复杂度 .

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int S=1e5+5;
int c[5],d[5],n,s;
int f[S];
signed main(){
    scanf("%lld%lld%lld%lld%lld",&c[1],&c[2],&c[3],&c[4],&n);
    f[0]=1;
    for(int j=1;j<=4;j++) for(int i=1;i<S;i++) if(i>=c[j])f[i]+=f[i-c[j]];
    for(int i=1;i<=n;i++){
        scanf("%lld%lld%lld%lld%lld",&d[1],&d[2],&d[3],&d[4],&s);
        int ans=0;
        for(int i=1;i<16;i++){
            int m=s,bit=0;
            for(int j=1;j<=4;j++) if((i>>(j-1))&1) m-=(d[j]+1)*c[j],bit++;
            if(m>=0)ans+=(bit%2*2-1)*f[m];
        }
        printf("%lld\n",f[s]-ans);
    }
    return 0;
}

错位排列计数

2019.4.27 更新

对于 的排列 如果满足 ,则称 的错位排列。求 的错位排列数。

全集 即为 的排列, ;属性就是 . 套用补集的公式,问题变成求 .

我们知道 的含义是满足 的排列的数量。用容斥原理把问题式子展开,我们需要对若干个特定的集合的交集求大小,即

其中我们省略了 的条件以方便表示。上述 个集合的交集表示有 个变量满足 的排列数,而剩下 个数的位置任意,因此排列数

那么选择 个元素的方案数为 ,因此有

因此 的错位排列数为

完全图子图染色问题

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

来源:王迪《容斥原理》,2013 年信息学奥林匹克中国国家队候选队员论文集

A 和 B 喜欢对图(不一定连通)进行染色,而他们的规则是,相邻的结点必须染同一种颜色。今天 A 和 B 玩游戏,对于 n 阶完全图 。他们定义一个估价函数 ,其中 S 是边集, . 的值是对图 种颜色染色的总方案数。他们的另一个规则是,如果 是奇数,那么 A 的得分增加 ,否则 B 的得分增加 . 问 A 和 B 的得分差值。

数学形式

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

容斥模型

相邻结点染同一种颜色,我们把它当作属性。在这里我们先不遵守染色的规则,假定我们用 m 种颜色直接对图染色。对于图 ,我们把它当作元素属性 的含义是结点 i,j 染同色(注意,并未要求 i,j 之间有连边)。

而属性 对应的集合定义为 ,其含义是所有满足该属性的图 的染色方案,集合的大小就是满足该属性的染色方案数,集合内的元素相当于所有满足该属性的图 的染色图。

回到题目,“相邻的结点必须染同一种颜色”,可以理解为若干个 集合的交集。因此可以写出

上述式子右边的含义就是说对于 S 内的每一条边 都满足 的染色方案数,也就是 .

是不是很有容斥的味道了?由于容斥原理本身没有二元组的形式,因此我们把所有的边 映射到 个整数上,假设将 映射为 ,同时 映射为 . 那么属性 则定义为 .

同时 S 可以表示为若干个 k 组成的集合,即 .(也就是说我们在边集与数集间建立了等价关系)。

而 E 对应集合 . 于是乎

逆向分析

那么要求的式子展开

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

再考虑等式右边的含义,只要满足 任一条件即可,也就是存在两个点同色(不一定相邻)的染色方案数!而我们知道染色方案的全集是 ,显然 . 而转化为补集,就是求两两异色的染色方案数,即 . 因此

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

数论中的容斥

2019.4.28 更新

考虑这样一个经典问题

求欧拉函数 . 其中 .

直接计算是 的,用线性筛是 的,杜教筛是 的(话说一道数论入门题用容斥做为什么还要扯到杜教筛上),接下来考虑用容斥推出欧拉函数的公式

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

那么就要求对于任意 都不是 的倍数,即 . 把它当作属性,对应的集合为 ,因此有

全集大小 ,而 表示的是 构成的集合,显然 ,并由此推出

因此可得

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

容斥原理一般化

容斥原理常用于集合的计数问题,而对于两个集合的函数 ,若

那么就有

证明

接下来我们简单证明一下

我们发现后半部分的求和与 无关,因此

记关于集合 的函数 ,并化简:

因此

而仅当 时有 ,这时 ,对答案的贡献就是 ,因此

综上,得证。

推论

该形式还有这样一个推论。在全集 下,对于函数 ,如果

那么

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

DAG 计数

个点带标号的有向无环图进行计数,对 取模。 .

直接 DP

考虑 DP,定义 表示 i 个点的 DAG,有 j 点个入度为 0 的图的个数。假设去掉这 个点后,有 k 个点入度为 0,那么在去掉前这 k 个点至少与这 j 个点中的某几个有连边,即 种情况;而这 j 个点除了与 k 个点连边,还可以与剩下的点任意连边,有 种情况。因此方程如下

计算上式的复杂度是 的。

放宽限制

上述 DP 的定义是恰好 j 个点入度为 0, 太过于严格,可以放宽为至少 j 个点入度为 0. 直接定义 表示 i 个点的 DAG 个数。可以直接容斥。考虑选出的 j 个点,这 j 个点可以和剩下的 i-j 个点有任意的连边,即 种情况

计算上式的复杂度是

小结

所以容斥是什么?

你发现容斥就是 DP 啊emm

参考文献

王迪《容斥原理》,2013 年信息学奥林匹克中国国家队候选队员论文集

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


  转载请注明: Sshwy's Blog 容斥原理入门

 上一篇
班级规划发展之制度建设 班级规划发展之制度建设
摘要 作为班长,参与了整个班级制度的建设,有许多收获。今应班主任要求,撰写论文 背景初一时,我加入了二四班。在当时对我来说是一个陌生的集体,一方面期待二四制班级的不同,一方面也担心自身在众学霸中的水平。从初二开始,我成为了这个班级的班长
2019.04.26
下一篇 
那年 @ 今日 那年 @ 今日
摘要 纪念现役 2 年 OI 本站 @ 碎碎念一路踏着星光走来,2018 四川省选也结束了,奖学金尘埃落定,看到 Siyuan 大佬一式 40 分,LMOliver 怒切 D1T2,XRY 努力学习文化课。看到 Mr_spade《我亲爱的
2019.04.20
  目录