[COCI2009-2010#6] XOR
题目描述
坐标系下有若干个等腰直角三角形，且每个等腰直角三角形的直角顶点都在左下方，两腰与坐标轴平行。被奇数个三角形覆盖的面积部分为灰色，被偶数个三角形覆盖的面积部分为白色，如下图所示。
已知 \(N\)个等腰直角三角形的顶点坐标及腰长，求灰色部分面积。
\(1 \leq N \leq 10, 1 \leq X, Y, R \leq 10^6\)
思路点拨
容斥做法
这题的数据范围十分的明显, \(n=10\) ,搜索,状压,容斥什么的。再加上本题的题目配图,很容易往容斥的角度思考问题。本题具体有两种容斥做法:
第一种(不好想但是简单)
我们假设一片区域被 \(m\) 个三角形包含,这 \(m\) 个三角形共同组成了一个集合 \(S\)
有一个结论:
\[[2 \nmid m]=\sum_{T \subseteq S}(-1)^{|T|+1}2^{|T|-1}
\]
这里给出一个简单的证明:
\[\sum_{T \subseteq S}(-1)^{|T|+1}2^{|T|-1} = \sum_{i=1}^{|S|}C_{m}^{i} (-1)^{i+1}2^{i-1}
\]
\((-1)^{i+1}=(-1)^{i-1}\) 本质上是一样的,方便与后面的 \(2^{i-1}\) 同类项。
\[=\sum_{i=1}^{m}C_{m}^{i} (-1)^{i-1}2^{i-1}=\sum_{i=1}^m C_{m}^i (-2)^{i-1}
\]
这个东东有点像 \((-2+1)^m\) 的二项式定理展开式,我们将 \((-2)^{i-1}\) 凑成 \((-2)^{i}\) , 然后二项式定理减去 \(i=0\) 的贡献就可以了。
\[=\dfrac{-1}{2}\sum_{i=1}^m C_{m}^i (-2)^{i}=\dfrac{\sum_{i=0}^m C_{m}^i (-2)^{i}-1}{-2}
\]
\[=\dfrac{1-(-2+1)^{m}}{2} = [2 \nmid m]
\]
OK,我们就获得了一个容斥系数。代码实现比较简单。