对于容斥原理&反演的思考和总结

前言

我还是太菜了
容斥之类的方法并不能熟练应用
于是这次我就认真学习了一下容斥
你可能会发现，容斥与反演很多时候都会同时出现
那么，这两个东西分别是什么、究竟有什么关系呢？

容斥

我们先从定义说起
什么是容斥？

百度百科·容斥原理： 先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理

贴出最经典的容斥原理的式子
∣A1​∪A2​∪...∪An​∣=i=1∑n​(−1)i−1∣T∣=i,T={x1​...xi​}∑​∣Ax1​​∩Ax2​​∩...∩Axi​​∣
当直接计算左式并不方便的时候，就能转化成右式解决问题了
例题：[bzoj4455]小星星
证明：
对于某个∣T∣=i，T={x1​...xi​}，其对应的集合为∣Ax1​​∩Ax2​​∩...∩Axi​​∣，它应当被计算一次，我们现在来进行证明
它被计算的次数根据组合数可得：
Ans​=j=1∑i​(−1)j−1(ji​)=−(j=1∑i​(−1)j(ji​))+1−1=1−(j=0∑i​(−1)j(ji​))=1−(j=0∑i​(−1)j1i−j(ji​))=1−(1−1)j=1​
中间用到的是二项式定理（百度百科链接），然后证毕

反演

我是分割线，待填坑