在组合数学中，容斥是常常被用到的，我们总用容斥求解一些带有条件的组合数。
- 容斥原理：具有性质A和性质B的元素个数等同于具有性质A的个数和具有性质B的个数的和再减去同时具有性质A和性质B的元素的个数。
数学公式表示为 |A∪B|=|A|+|B|-|A∩B|。
图形表示为
其中黄色区域就是我们所求。
同样以此类推对于三个性质来说其数学公式为|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|
为什么要加上最后那个呢？因为在减的过程中多减了一个。 - 对于容斥原理来说比较常用的方法为递归法和二进制枚举法，二进制枚举的方法最大的好处是枚举出所有元素的子集。假设一个集合的元素有m个，则对于m长的二进制数来说就有m个1或0的位置，对于每一个1
-就对应一个元素，整个二进制枚举完就是所有子集，从0到2^m就行。 - 递归法则是利用dfs的思想进行搜索，检索每一种方案进行容斥。由于每一种题都有不同的搜索方法，没用统一的模板，就不弄代码了。
- 在这其中都是奇数个性质加偶数个性质减，而如果所求的性质是相反的性质，则用总数减去。
- 容斥原理开着简单，实际非常复杂，每一道题都用不同的性质容斥，但最终的思想是不变的，多做一些题就会慢慢积累经验最终由一个好的思想。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/233815.html原文链接：https://javaforall.net
