容斥&反演 学习笔记

反演

以上是神级学习资料。

反演的本质

本质上来说，反演的时候我们一般会遇到形如下面式子的形式：

其中 是我们希望求得的答案， 容易直接计算得出， 是系数。一般来说，我们可能会看到形如这样的描述：设 表示恰好拥有 个属性的方案数， 为不超过/钦定拥有 个属性的方案数。如果我们能够找到一个 ，使得下式成立：

那么我们就可以十分方便地得到 。反演就可以找到这样的一个 。另一个有意思的理解是，反演是一个矩阵求逆的过程。所谓常见的反演，其本质是非常容易求逆的矩阵。

接下来结合一些具体的形式介绍反演。

二项式反演

容易注意到这一式子和上面的形式一致。

接下来推导第一行。由于二项式定理，我们有：

反演的式子中大多都会出现这样一条关键性质，我们可以借此使得式子中变出 。后续我们再结合相关例子进行介绍。那么，我们可以对原式进行如下变换：

是不是很神奇。

对于第二行的推导：

这里还有一步抽象的变形：

所以可以化成：

子集反演

本质和二项式反演一致，甚至可能还更好理解一点。

需要注意到的关键性质是：

事实上这一关键性质与我们刚才使用到的关键性质完全相同，因为 中大小为 的子集个数有 个。

接下来进行推导，以第一行为例。

莫比乌斯反演

直接上关键性质。

这是直接由莫比乌斯函数性质得到的。

接下来进行推导，以第一行为例。

容斥

容斥的本质

已知：

其中 是系数， 表示恰好拥有 个属性的方案数。尝试找到 ，使得：

其中 是容斥系数， 表示不超过/钦定拥有 个属性的方案数（大多数情况下， 是比 好算的）。

容斥系数

所谓容斥系数，其实就是我们通过调整 的系数，使得累积起来产生的 的系数变为我们想要的系数。在很多情况下，容斥系数可以由二项式定理导出，或者 暴力计算导出。

二项式容斥（反演）

接下来我们重新从容斥的角度审视一下二项式反演。

假设我们现在要求 （这相当于），同时，给定 和 的关系：

同时假设 已知。此时，我们设：

代入一式：

因此，我们只需要保证 即可。注意到这和二项式定理的形式完全一致，我们令 。那么：

那么我们就完成了我们的容斥。（感觉好像就是反着来一遍反演）

Min-Max 容斥

施工中。