首页 > 笔记 > 容斥总结

容斥总结

很优美的计算方法。

引入

首先看个小学数学题

班主任在班会上问:“谁做完了语文作业?请举手”有37人举手,又问:“谁做完了数学作业?请举手”有42人举手,最后问:“谁语文、数学作业都做完了?请举手”有25人举手。求这个班语文、数学作业至少有一个做完的人数是多少个?

小学写啥作业。。这就是一道容斥原理的题。我们可以通过画图或者直接看出答案是$37+42-25$

定义

我们可以试着转换一下。这个问题可以转化为知道一个有限集合$U$,还知道两种条件$P_1,P_2$,定义两个集合$S_1,S_2$为$U$的子集,分别是满足$P_1,P_2$的元素,现在知道分别满足两种性质的元素个数$|S_1|,|S_2|$和同时满足两种条件的元素个数$|S_1 \cap S_2|$,求出至少满足一种的元素个数$|S_1 \cup S_2|$

那么公式就是

$$|S_1 \cup S_2|=|S_1|+|S_2|-|S_1 \cap S_2|$$

通过画图啥的可以推广出三种条件的公式

$$|S_1 \cup S_2 \cup S_3|=|S_1|+|S_2|+|S_3|-|S_1 \cap S_2|-|S_1 \cap S_3|-|S_2 \cap S_3|+|S_1 \cap S_2 \cap S_3|$$

这样我们可以得出容斥原理的一个通式

设$U$中有$n$种不同的条件$P_i$,满足每种条件的子集为$S_i$,则满足最少一个条件的元素个数为

\begin{aligned}
|S_1 \cup S_2 \cup \cdots \cup S_n| & = \sum_{i}|S_i| -\sum_{i< j}|S_i \cap S_j|+\sum_{i< j< k}|S_i \cap S_j \cap S_k|-\cdots \\
& \cdots +(-1)^{n-1}|S_1 \cap S_2 \cap \cdots \cap S_n|
\end{aligned}

下面就证明一下这个结论。

考虑某个元素$i$,它属于的$m$个集合为$T_1,T_2 \cdots T_m$。我们考虑式子右边它算了多少次。。

$$times=C_m^1-C_m^2+\cdots (-1)^{m-1}C_m^m$$

上图吧

就是计算了它在每个条件里的贡献。

$$times=-((\sum_{i=0}^m(-1)^iC_m^i)-C_m^0)$$

二项式定理化一下

$$times=-((1-1)^m-1)$$

这样也就是说,只要$m>0$就是计算了1次,所以只要它满足一个条件,它就只会计算一次,也就是至少满足一个条件。

这里我们是拿交集求出并集,那如何反向求呢?

那就用补集转换。。

公式

$$|S_1 \cap S_2 \cap \cdots \cap S_n|=|U|-|S_1 \cup S_2 \cup \cdots \cup S_n|$$

例题

下面就看点例题吧

uva11806

题意:给一个nxm的棋盘,往里面放k个棋子,且第一行,第一列,最后一行,最后一列至少有一个棋子。问方案数。

题解

总的集合是所有子都随便放的方案数,四个条件是满足分别第一行,第一列,最后一行,最后一列满足。

我们先补集转化一下,再套公式就好了。

hdu4135

题意:求出a-b中间和n互质的数字个数。$a< b< 10^{15} n< 10^9$

题解

补集转化成a-b之间和它不互质的数字个数。就把n分解质因数,作为条件。计算小于b和小于a-1的,减一下。

luogu1450 [HAOI2008]硬币购物

题目描述

硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西,去了tot次。每次带di枚ci硬币,买si的价值的东西。请问每次有多少种付款方法。

输入输出格式

输入格式:
第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s

输出格式:
每次的方法数

输入输出样例

输入样例#1:
1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900
输出样例#1:
4
27

说明

di,s<=100000

tot<=1000

题解

设$f[i]$为不考虑每种硬币的数量限制的情况下,得到面值i的方案数。

dp一下搞出来。$f[i]=\sum_{j=1..4}f[i-c[j]]$

然后就是容斥:得到面值S的超过限制的方案数 – 第1、2、3、4种硬币分别超过限制的方案数 + 第1,2种硬币同时超过限制的方案数 + …… + 第1,2,3,4种硬币全部同时超过限制的方案数。

当第1种硬币超过限制时,只要要用到$d[1]+1$枚硬币,剩余的硬币可以任意分配,所以方案数为 $f[all–(d[1]+1) \times c[1]]$

然后就是容斥了。

luogu2567 [SCOI2010]幸运数字

题目描述

在中国,很多人都把6和8视为是幸运数字!lxhgww也这样认为,于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码,比如68,666,888都是“幸运号码”!但是这种“幸运号码”总是太少了,比如在[1,100]的区间内就只有6个(6,8,66,68,86,88),于是他又定义了一种“近似幸运号码”。lxhgww规定,凡是“幸运号码”的倍数都是“近似幸运号码”,当然,任何的“幸运号码”也都是“近似幸运号码”,比如12,16,666都是“近似幸运号码”。

现在lxhgww想知道在一段闭区间[a, b]内,“近似幸运号码”的个数。

输入输出格式

输入格式:
输入数据是一行,包括2个数字a和b

输出格式:
输出数据是一行,包括1个数字,表示在闭区间[a, b]内“近似幸运号码”的个数

输入输出样例

输入样例#1:
1 10
输出样例#1:
2

说明

对于30%的数据,保证1<=a<=b<=1000000

对于100%的数据,保证1<=a<=b<=10000000000

题解

我们先打表找下范围内的数字,发现有2000+个。

把这些数之间存在倍数关系的都干掉,发现还有900+个。

裸的枚举效率$O(2^{900})$,非常不优越。

发现会有很多组合大于边界,一旦大于就不用继续枚举。写了个剪枝的爆搜过了。

bzoj2393

Description

~Cirno发现了一种baka数,这种数呢~只含有2和⑨两种数字
现在Cirno想知道~一个区间中~ ~有多少个数能被baka数整除~
但是Cirno这么天才的妖精才不屑去数啦
只能依靠聪明的你咯。

Input

一行正整数L R
( 1 < L < R < 10^10)

Output

一个正整数,代表所求的答案

Sample Input

1 100

Sample Output

58

一模一样


这是几个月前写的,现在又加了几道题:

bzoj2669
bzoj4455
bzoj4710
bzoj4569

恰好k个的容斥

有时候做题会有恰好k个的限制,限制很强,通常弱化为先拿出k个,剩下的任意。这时候容斥的形式通常是

$$=\ \ge k个\ -\ \ge k+1个\ +\ \ge k+2个\ …$$

这时候我们在统计$\geq j$也就是$k \leq j \leq n$时,如果依靠了枚举哪j个或者类似的DP,可能会过多的统计,比如一个$k+i$个的方案在这时候会被考虑$k + i \choose k$次,所以需要乘上一个组合数系数$k + i \choose k$

有的问题是恰好没有之类的,这时候$i \choose 0$所以不用考虑这个东西;同理,恰好n个也不用考虑。

证明

我们考虑一个恰好$x:x \geq k$个的方案被统计的次数:

$$
\begin{align}
&= \sum_{i=k}^x (-1)^{i-k}\binom{i}{k} \binom{x}{i} \\
&= \binom{x}{k} \sum_{i=k}^x (-1)^{i-k} \binom{x-k}{x-i}\\
&= \binom{x}{k} \sum_{j=0}^{x-k} \binom{x-k}{j} \\
&= [x==k]
\end{align}
$$

例题

bzoj3622
bzoj2024
bzoj3198
bzoj2839

用莫比乌斯函数做反演系数

bzoj2440
cf547c
bzoj2986


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×