容斥原理

容斥原理

一、定义

    容斥原理是一种计数方法，其基本思想是先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去。

二、证明

    数学符号：∪为并，A∪B表示A和B的总面积（数量……）      

              ∩为与，A∩B表示A、B的交集部分    

    由韦恩图不难发现，A∪B=A+B-A∩B

    有了这条公式，就可以用数学归纳法推导出普遍规律。

    A ∪ B ∪ C

  =（A ∪ B)∪ C

  = A ∪ B +C -( A ∪ B) ∩C

  = A ∪ B +C -[ (A ∩ C) ∪( B ∩ C) ]

  = A ∪B + C–(A ∩ C + B ∩C - A ∩ B ∩ C)

  = A+B+C-A∩B+C- A ∩ C- B ∩C +A ∩ B ∩C

    由此可以发现一个规律——奇数加，偶数减。即：对于n个相交的块的总数/总面积，每奇数个块的交集部分要加上，每偶数个块的交集部分要减去。证明方法类比上文。

三、习题应用

   SMOJ 1865 矩形相交面积

    SMOJ 2161 棋盘

   （详见解题报告）