【博客】反演学习笔记（含非卷积证明法详细证明）

什么是反演：

有函数，令，其中x与s的关系自定，在已知求的过程叫反演。

集合反演：

公式：

推导过程： 核心是容斥。

首先，当那么所有都被加入，我们要把除了之外的都删掉。

我们将与相差的都减去，他们两两之间的交***减两次，还要再加回，那么就变成了容斥的形式。

莫比乌斯反演：

公式：

推导过程：与集合反演类似，但是更加复杂，核心也是容斥。

首先,代表要加入还是删除，类似于集合反演，我们想要找到在与的某种关系下固定的系数，对于集合是，对于莫比乌斯反演，我们选择。我们令，分类讨论：

若，即，我们必须选，于是

若是质数，是变成“子集”的最小单位，我们把他删除，

若是两个不同质数的乘积，那么被这两个质数删了两次要加回，那么。

那么三个质数时呢 ，我们又要减去，现在又变成了容斥的形式，所以当是个不同质数的乘积时。

我们发现整个过程已经完毕，那么其余。

总结-莫比乌斯函数：

一些公式：

(组合数可证)

(左面通分，同去掉分母，根据反演可得）

（反演回去可得）

扩展-莫比乌斯反演的另一种形式（更加常用）：

与原式一样容斥可得到。

应用：
求

设是的数对个数，是的数对个数，那么：

根据扩展：

于是