锐客网

  1. 首页 > it技术 > >

容斥原理证明及应用

数论

普通的容斥原理 例题 给定平面上n个多边形，请求出其覆盖的总面积。
n ≤ 10 ,边 数 ≤ 50 , 000 n\le 10,~边数\le 50,000 n≤10, 边数≤50,000
解决方案1——自适应辛普森积分 该方法适应于大部分求覆盖面积的问题，但是由于精度问题，不易于实现。
解决方案2——按点坐标离散化 该方法实现较为复杂，在多边形数量多的时候占优势，但是边数很多的情况下就显得力不从心了（但是似乎也是可以做到 O ( n m + m l o g m ) O(nm+mlogm) O(nm+mlogm)的）。
解决方案3——容斥原理 考虑如果我们直接把所有多边形面积求出来然后求和，会多算一些重复覆盖的地方。于是我们可以考虑把它们全部去掉。但是如果直接枚举两个多边形求交，又会多减去一些东西，于是考虑再把它加回来……
这样就可以得到容斥原理的公式了——
a n s = ∑ A ? S ( ? 1 ) ∣ A ∣ ? 1 ? A r e a ( A ) ans=\sum_{A\subseteq S}(-1)^{|A|-1}·Area(A) ans=A?S∑?(?1)∣A∣?1?Area(A)
其中 S S S为所有多边形的集合， A r e a ( x ) Area(x) Area(x)函数表示集合 x x x中所有多边形的交的面积。
说人话就是暴力枚举选出一些多边形，计算它们交的面积。如果选出了奇数个多边形，就拿答案加上它，否则减去它。
这样就得到了一个非常难以理性感知的容斥原理，为了能够深入理解它，我们需要证明。
证明 考虑原来那么多多边形将平面分成了很多部分，每个部分是一个小多边形，这些小多边形互不相交（除了边）。我们最后需要求出的面积实际上就是每个小多边形的面积。考虑小多边形 x x x在容斥原理中被如何处理，它被统计的面积是：
∑ x ∈ Aa n dA ? S ( ? 1 ) ∣ A ∣ ? 1 A r e a ( x ) \sum_{x\in A~and~A\subseteq S}(-1)^{|A|-1}Area(x) x∈A and A?S∑?(?1)∣A∣?1Area(x)
换一种表示方案，假设它被包含在了 k k k的原来的多边形中，那么它会被统计的次数是：
∑ i = 1 k ( k i ) ( ? 1 ) i ? 1 = ? ∑ i = 0 k ( k i ) ( ? 1 ) i + 1 = 1 ? 0 k = 1 \sum_{i=1}^k\binom ki(-1)^{i-1}=-\sum_{i=0}^k\binom ki(-1)^i+1=1-0^k=1 i=1∑k?(ik?)(?1)i?1=?i=0∑k?(ik?)(?1)i+1=1?0k=1
也就是说每个小多边形都恰好被统计了一次！于是这样算出来的答案就是正确的了。
什么？你说求多边形的交很难？那不是半平面交的板子嘛……
例题 给定一个n个点，m条边的无向图，每条边都有一个从 1 1 1到 n ? 1 n-1 n?1编号的颜色。求它所有的生成树，满足树中任意两条边颜色不同。
（ n ≤ 15 ， 颜 色 数 ≤ 15 n\le 15，颜色数\le 15 n≤15，颜色数≤15）
解决方案 显然每种颜色必须出现且仅出现一次。
考虑如果没有颜色不同的限制，实际上这是一个裸的矩阵树定理。但是这题有了限制，我们就考虑暴力枚举哪种颜色的边没有出现，然后对于剩下来的边求一遍生成树计数，于是就直接容斥就好了，复杂度 O ( 2 n ( n ? 1 ) 3 ) O(2^n(n-1)^3) O(2n(n?1)3)。
普通容斥原理的推广 例题 给定平面上的n个矩形，如果一个区域被奇数个矩形覆盖，那么该区域为黑色，否则为白色。求所有被黑色格子覆盖的矩形面积。（ n ≤ 20 n\le 20 n≤20）
解决方案 数据量很小肯定可以考虑容斥。但是上面普通的容斥只能够计算覆盖的面积，而对于这种特殊情况就不能处理。我们可以考虑反推，也就是说从每个小矩形需要被计算的次数反推容斥系数。
不妨假定大小为 i i i的集合容斥系数为 f ( i ) f(i) f(i)。则——
∑ i = 1 k ( k i ) f ( i ) = [ km o d2 = 1 ] \sum_{i=1}^k\binom kif(i)=[k~mod~2=1] i=1∑k?(ik?)f(i)=[k mod 2=1]
显然这是一个二项式反演的形式，于是就可以推出来 f f f了（二项式反演链接）
f ( k ) = ∑ i = 1 k ( ? 1 ) k ? i ( k i ) ? [ im o d2 = 1 ] = ( ? 1 ) k ? 1 ? 2 k ? 1 f(k)=\sum_{i=1}^k(-1)^{k-i}\binom ki·[i~mod~2=1]=(-1)^{k-1}·2^{k-1} f(k)=i=1∑k?(?1)k?i(ik?)?[i mod 2=1]=(?1)k?1?2k?1
这里用到了组合数奇数项求和等于偶数项求和的定理（当然数据量这么小暴算也没问题）。于是这道题直接就用容斥在 O ( 2 n ) O(2^n) O(2n)的时间内解决了。
例题 给定平面上的n个矩形，计算被且仅被一个矩形覆盖的面积大小。
解决方案 【容斥原理证明及应用】套路是一样的，一个块恰好被一个矩形覆盖则为1，否则为0.那么：
∑ i = 1 k ( k i ) f ( i ) = [ k = 1 ] ， f ( k ) = ∑ i = 1 k ( ? 1 ) k ? i ( k i ) [ i = 1 ] = ( ? 1 ) k ? 1 k \sum_{i=1}^k\binom kif(i)=[k=1]，f(k)=\sum_{i=1}^k(-1)^{k-i}\binom ki[i=1]=(-1)^{k-1}k i=1∑k?(ik?)f(i)=[k=1]，f(k)=i=1∑k?(?1)k?i(ik?)[i=1]=(?1)k?1k
于是容斥系数就算出来了，接下来直接容斥就行。

    推荐阅读


    上一篇：C++之STL算法

    下一篇：解决VUE中document.documentElement.scrollTop为0