容斥原理证明及应用

普通的容斥原理

例题

给定平面上n个多边形，请求出其覆盖的总面积。
$n\le 10,边数\le 50,000$

解决方案1——自适应辛普森积分

该方法适应于大部分求覆盖面积的问题，但是由于精度问题，不易于实现。

解决方案2——按点坐标离散化

该方法实现较为复杂，在多边形数量多的时候占优势，但是边数很多的情况下就显得力不从心了（但是似乎也是可以做到$O(nm+mlogm)$的）。

解决方案3——容斥原理

考虑如果我们直接把所有多边形面积求出来然后求和，会多算一些重复覆盖的地方。于是我们可以考虑把它们全部去掉。但是如果直接枚举两个多边形求交，又会多减去一些东西，于是考虑再把它加回来……
这样就可以得到容斥原理的公式了——
$$ans=\sum _{A\subseteq S}(-1{)}^{|A|-1}\cdot Area(A)$$
其中$S$为所有多边形的集合，$Area(x)$函数表示集合$x$中所有多边形的交的面积。
说人话就是暴力枚举选出一些多边形，计算它们交的面积。如果选出了奇数个多边形，就拿答案加上它，否则减去它。
这样就得到了一个非常难以理性感知的容斥原理，为了能够深入理解它，我们需要证明。

证明

考虑原来那么多多边形将平面分成了很多部分，每个部分是一个小多边形，这些小多边形互不相交（除了边）。我们最后需要求出的面积实际上就是每个小多边形的面积。考虑小多边形$x$在容斥原理中被如何处理，它被统计的面积是：
$$\sum _{x\in AandA\subseteq S}(-1{)}^{|A|-1}Area(x)$$
换一种表示方案，假设它被包含在了$k$的原来的多边形中，那么它会被统计的次数是：
$$\sum _{i=1}^k\left(\genfrac{}{}{0ex}{}{k}{i}\right)(-1{)}^{i-1}=-\sum _{i=0}^k(\genfrac{}{}{0ex}{}{k}{i})(-1{)}^i+1=1-0^k=1$$
也就是说每个小多边形都恰好被统计了一次！于是这样算出来的答案就是正确的了。
什么？你说求多边形的交很难？那不是半平面交的板子嘛……

例题

给定一个n个点，m条边的无向图，每条边都有一个从$1$到$n-1$编号的颜色。求它所有的生成树，满足树中任意两条边颜色不同。
（$n\le 15，颜色数\le 15$）

解决方案

显然每种颜色必须出现且仅出现一次。
考虑如果没有颜色不同的限制，实际上这是一个裸的矩阵树定理。但是这题有了限制，我们就考虑暴力枚举哪种颜色的边没有出现，然后对于剩下来的边求一遍生成树计数，于是就直接容斥就好了，复杂度$O(2^n(n-1{)}^3)$。

普通容斥原理的推广

例题

给定平面上的n个矩形，如果一个区域被奇数个矩形覆盖，那么该区域为黑色，否则为白色。求所有被黑色格子覆盖的矩形面积。（$n\le 20$）

解决方案

数据量很小肯定可以考虑容斥。但是上面普通的容斥只能够计算覆盖的面积，而对于这种特殊情况就不能处理。我们可以考虑反推，也就是说从每个小矩形需要被计算的次数反推容斥系数。
不妨假定大小为$i$的集合容斥系数为$f(i)$。则——
$$\sum _{i=1}^k\left(\genfrac{}{}{0ex}{}{k}{i}\right)f(i)=[kmod2=1]$$
显然这是一个二项式反演的形式，于是就可以推出来$f$了（二项式反演链接）
$$f(k)=\sum _{i=1}^k(-1{)}^{k-i}(\genfrac{}{}{0ex}{}{k}{i})\cdot [imod2=1]=(-1{)}^{k-1}\cdot 2^{k-1}$$
这里用到了组合数奇数项求和等于偶数项求和的定理（当然数据量这么小暴算也没问题）。于是这道题直接就用容斥在$O(2^n)$的时间内解决了。

例题

给定平面上的n个矩形，计算被且仅被一个矩形覆盖的面积大小。

解决方案

套路是一样的，一个块恰好被一个矩形覆盖则为1，否则为0.那么：
$$\sum _{i=1}^k\left(\genfrac{}{}{0ex}{}{k}{i}\right)f(i)=[k=1]，f(k)=\sum _{i=1}^k(-1{)}^{k-i}(\genfrac{}{}{0ex}{}{k}{i})[i=1]=(-1{)}^{k-1}k$$
于是容斥系数就算出来了，接下来直接容斥就行。

最后

以上就是甜美柠檬为你收集整理的容斥原理证明及应用的全部内容，希望文章能够帮你解决容斥原理证明及应用所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。