信奥赛C++提高组csp-s之组合数学专

题课：容斥原理详解及案例实践

一、数学原理

容斥原理是一种用于计算多个集合并集元素数量的方法。其核心思想是：先不考虑重叠的情况，把所有包含于各个

集合的元素个数加起来，然后再减去重复计算的部分。

对于两个集合A和B，公式为：

对于三个集合A、B、C，公式扩展为：

更一般地，对于n个集合，其原理是：奇数个集合的交集加，偶数个集合的交集减。