反演入门学习笔记

考虑怎么求方案数，首先对 a,b 排序，便于找出存在多少个 b_j

g_{i,j}=g_{i-1,j}+(c_i-(j-1))g_{i-1,j-1}

解释：

前面的 g_{i-1,j} 不用乘是因为在最后进行二项式反演时才会乘上 (n-j)!。

最后有 a>b 对数应该是 tot=\frac{k+n}{2}，注意判一下无解。式子：

ans=\sum_{i=tot}^n(-1)^{i-tot}{i\choose tot}\cdot (n-i)!\cdot g_{n,i}

子集反演

理论

子集反演和二项式反演

子集反演其实与二项式有着很大的联系：例如证明过程相似，都是处理恰好与至少至多的关系等等。可以看作是集合角度的二项式反演。

假如题目给你 n 个元素（或是转换为 n 个条件等形式），让你求 f(S) 表示恰好选择 S 中的点的方案数，参照前面的思想，如果当 f(S) 求解困难时，可以记 g(S) 表示至多选 S 中这些点的方案数。

如果钦定 T 是满足条件的那个，显然有 g(S)=\sum_{T\subseteq S}f(T)。那么直接给出反演式子：

\boxed{f(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}g(T)}

可以看出这个式子同样具有优美的对称性。可以感性理解成一个容斥的过程，证明可以看补充资料：

子集反演学习笔记 - Pbri

【推导】子集反演的形式化推导 - 王学逸

当然，与二项式类似，其还有至少与恰好的转换形式：

\boxed{f(T)=\sum_{T\subseteq S}(-1)^{|S|-|T|}g(S)}

那么我们直接开始例题。

例题

一个规律是，由于子集反演需要枚举子集，其较高的时间复杂度使得一般题目的数据范围都较小。

子集反演经常与 dp 和生成树、矩阵等有关，所以有些题先咕着。

莫比乌斯反演

理论

从狄利克雷卷积开始

注：初学可能较为困难，仅作为理解。可以跳过（直接到例子处）。

(f\ast g)(x)=\sum_{d|x}f(d)g\left(\frac{n}{d}\right)\Leftrightarrow \sum_{ij=x}f(i)g(j)

}

\tiny\uparrow其实不用完全理解上面的式子\uparrow

其中后面的式子是对称形式，较为便于理解。

感性理解一下，狄利克雷卷积是有关于因数的卷积：

卷：对于每一对乘积等于 x 的 f 和 g，将其分别相乘。

积：所有因数对的答案之和。

例子

为了便于推出莫比乌斯函数与反演，我们举个例子：

假设有：

g=f\times c

如果知道了 g，怎么求 f？

f=g\times\frac{1}{c}

从原来的 c 变为 \frac{1}{c}，其实就是将其变为倒数。

在 f 不好求的情况下，我们只需求出 g 和 c 便可以逆推出 f，这就是反演的思想。

狄利克雷卷积的律

狄利克雷卷积满足交换律、结合律、分配律（证明：狄利克雷卷积和莫比乌斯反演 by 秋钧）。

是不是很像我们接触的乘法？「卷积」中的「积」就来源于此。

在狄利克雷卷积中，原来的符号 \times 变为了卷积的式子（上面）。接下来我们开始介绍数论函数：

数论函数全家桶

数论函数

定义域为整数，值域为实数。

即 x\in\mathbb{N},f(x)\in\mathbb{R}。

单位元函数

\boxed{\epsilon(x)=[x=1]}

艾佛森括号

1 & \mathtt{如果\space P\space 成立}\\

0 & \mathtt{otherwise}

\end{cases}

艾佛森括号可以大大简化公式的书写，如上文的 \epsilon(x)，在 x=1 时 \epsilon(1)=1，其他时候均为 0。

根据上面的例子，我们也可以将其类比为狄利克雷卷积中的 1。

单位元函数是一个积性函数。

积性函数

对于所有互质的整数 a,b，都有 f(ab)=f(a)f(b)。

完全积性函数则更进一步，对于任意整数 a,b，都有 f(ab)=f(a)f(b)。

常数函数

\mathbf{1}(x)=1

没错，就这么简单！

引入正题

狄利克雷逆

\boxed{f\ast f^{-1}=\epsilon}

限于篇幅，关于 $f^{-1}$ 的具体狄利克雷逆展开，推荐[狄利克雷卷积和莫比乌斯反演 by Xecades](https://zhuanlan.zhihu.com/p/390895860)。

---

#### 莫比乌斯函数与常数函数

莫比乌斯函数的定义其实是这样的：

$$\boxed{\mu=\mathbf{1}^{-1}}$$

即其是**常数函数**的逆元。

展开后就成了：

$$\boxed{\mu(x)=\begin{cases}

1 & x=1\\

0 & \exists p\in\mathbb{N}^+,p^2|x &\mathtt{即\space} x\mathtt{\space 含有平方因子}\\

(-1)^k & \mathtt{otherwise} & k\mathtt{\space 是\space} x \mathtt{\space 的素因子个数}

\end{cases}}$$

还记得一开始的例子吗？

若 $g(x)=f(x)\ast\mathbf{1}$，则 $f(x)=g(x)\ast\mu

将其全部展开狄利克雷卷积后：

g(x)=\sum_{d|n}f(d)\Leftrightarrow f(x)=\sum_{d|n}\mu\left(\frac{n}{d}\right)g(d)

}

注：为了对称，\sum_{d|n}\mu\left(\frac{n}{d}\right)g(d) 可以写成 \sum_{ij=n}\mu(i)g(j)。

另一个特殊的性质：

\sum_{d|n}\mu(d)=[n=1]

把 n 换成 \gcd(i,j)：

\sum_{d|\gcd(i,j)}\mu(d)=[\gcd(i,j)=1]

}

我们将在例题中详细讲述其应用。

线性筛

不过好在其是**积性函数**，直接上代码（线性筛基本可以求所有的积性函数）：

```cpp

void initmu() {

mu[1] = 1;

for (int i = 2; i <= n; ++i) {

if (!flg[i]) p[++tot] = i, mu[i] = -1; // 定义

for (int j = 1; j <= tot && i * p[j] <= n; ++j) {

flg[i * p[j]] = 1;

if (i % p[j] == 0) {

mu[i * p[j]] = 0; // 平方因子

break;

}

mu[i * p[j]] = -mu[i]; // 多一个因子

}

}

}

```

## 例题

### [P2522 [HAOI2011] Problem b](https://www.luogu.com.cn/problem/P2522)

> 求：

> $$\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k]$$

注：以下默认 $n

> 还记得吗？

> $$\sum_{d|\gcd(i,j)}\mu(d)=[\gcd(i,j)=1]$$

要将其转换为上面这个格式，只需要把 $k$ 变为 $1$（可以思考一下为什么能这么转换）：

$$\sum_{i=1}^{\lfloor \frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{k}\rfloor}[\gcd(i,j)=1]$$

大力上莫比乌斯：

$$\sum_{i=1}^{\lfloor \frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{k}\rfloor}\sum_{d|\gcd(i,j)}\mu(d)$$

换个角度，先枚举 $d$ 再找满足 $d|\gcd(i,j)$ 的 $i$ 和 $j$：

$$\sum_{d=1}^n\mu(d)\sum_{i=1}^{\lfloor \frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{k}\rfloor}[d|\gcd(i,j)]$$

发现满足 $d|\gcd(i,j)$ 的 $i,j$ 可以直接算：

$$\sum_{d=1}^n\mu(d)\sum_{i=1}^{\lfloor \frac{n}{kd}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{kd}\rfloor}1$$

$$\sum_{d=1}^n\mu(d)\lfloor \frac{n}{kd}\rfloor\lfloor \frac{m}{kd}\rfloor$$

$O(n)$ 算，解决！

总结一下：

一开始求的是 $\sum[1=\gcd(i,j)]$，运用**恰好难算包含好算**的思想，化为 $\sum[d|\gcd(i,j)]$，此时就去掉了枚举的 $\sum$，这是这样一类问题的经典套路。

### [P1829 [国家集训队] Crash的数字表格 / JZPTAB](https://www.luogu.com.cn/problem/P1829)

> 求：

> $$f(n,m)=\sum_{i=1}^n\sum_{j=1}^m\operatorname{lcm}(i,j)$$

>

~~$\operatorname{lcm}$ 看起来不顺眼~~。我们知道，$\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}$，~~读者自证不难~~。

于是把它换成 $\gcd$：

$$f(n,m)=\sum_{i=1}^n\sum_{j=1}^m\frac{ij}{\gcd(i,j)}$$

这一步非常关键，**由于 $\gcd$ 在分母不好处理，我们设法将其拎出来**。

由 $\gcd$ 的定义引入 $d=\gcd(i,j)$：

$$f(n,m)=\sum_{i=1}^n\sum_{j=1}^m\sum_{d|i,d|j,\gcd(\frac{i}{d},\frac{j}{d})=1}\frac{ij}{d}$$

这一步也很关键，**需要注意的是 $i,j$ 的定义发生了变化**。

$i$ 变成了 $\frac{i}{d}$，这样的话 $\frac{ij}{d}$ 会少算一个 $d$，在前面补上：

$$f(n,m)=\sum_{d=1}^nd\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)=1]\cdot ij$$

$\gcd$ 被成功从分母转换到了外面，可喜可贺。发现后面依托 $\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)=1]\cdot ij$ 是一个新的式子，记：

$$g(n,m)=\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1]\cdot ij$$

那么就有：

$$f(n,m)=\sum_{d=1}^nd\cdot g(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)$$

发现如果可以快速算出 $g(x,y)$，就可以直接上**数论分块**求解。

接下来到了推 $g(n,m)$ 式子的时候：

$$g(n,m)=\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1]\cdot ij$$

这不就是上文说的套路吗，直接把 $\gcd(i,j)$ 展开：

$$g(n,m)=\sum_{i=1}^n\sum_{j=1}^mij\sum_{t|\gcd(i,j)}\mu(t)$$

把 $t$ 提到前面去：

$$g(n,m)=\sum_{t=1}^n\sum_{t|i}^n\sum_{t|j}^m\mu(t)ij$$

注意**这里 $i,j$ 的含义又发生了变化**，和上文类似，$i$ 变成了 $\frac{i}{t}$。

那么 $ij$ **少算了** $t^2$，加到前面去：

$$g(n,m)=\sum_{t=1}^n\mu(t)t^2\sum_{i=1}^{\lfloor\frac{n}{t}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{t}\rfloor}ij$$

前面的 $\sum_{t=1}^n\mu(t)t^2$ 可以预处理，再看后面，记：

$$h(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m}ij$$

这下简单了，直接展开：

$$h(n,m)=\sum_{i=1}^{n}i\cdot\frac{m(m+1)}{2}$$

$h(n,m)$ 可以 $O(1)$ 计算：

$$h(n,m)=\frac{n(n+1)}{2}\cdot\frac{m(m+1)}{2}$$

那么就有：

$$g(n,m)=\sum_{t=1}^n\mu(t)\cdot t^2\cdot h(\lfloor\frac{n}{t}\rfloor,\lfloor\frac{m}{t}\rfloor)$$

再套一个数论分块即可。~~禁止套娃~~，但是时间复杂度比线性预处理快。总体是 $O(n)$ 的。

### 口糊题

> 给你长度为 $n$ 的序列 $a$，选出两个互质的数 $a_i,a_j$ 使得 $a_i+114^{514}a_j$ 的值尽量小。

> $n,a_i\le10^6$。

算是莫反的综合运用吧，不是单纯推柿子了。

非常显然的有我们要尽可能让 $a_j$ 小，可以考虑把数组排序然后对于每一个 $a_i\ (i=1\to n)$ 看看是否有互质的另一个数。

但是你发现遇到了瓶颈：$O(n^2)$ 的优化非常困难。

这个时候你注意到一个神仙性质：如果 $a_i$ 对应有解就可以直接 $O(n)$ 扫一遍 $a_j$ 一个一个试，因为不用再考虑 $i$ 更大的情况了！那么问题就变为了如何快速 check 是否存在 $a_j$ 与 $a_i$ 互质。

此时终于等到主角登场，我们只需要考虑下面这个式子：

$$ans=\sum_{i=1}^n[\gcd(x,a_i)=1]$$

其中 $x$ 就是要 check 的 $a_i$ 的值，如果 $ans\neq0$ 就对完了！继续推：

$$\sum_{i=1}^n[\gcd(x,a_i)=1]=\sum_{i=1}^n\sum_{d|x,d|a_i}\mu(d)=\sum_{d|x}^n\sum_{i=1}^n[d|a_i]\cdot\mu(d)$$

发现对于每个 $d$，$\sum_{i=1}^n[d|a_i]\cdot\mu(d)$ 都是可以快速处理的，只需要枚举倍数即可。这样复杂度是 $O(m\log m)$ 的（$m$ 是值域）。

同样地，知道这个值后还是枚举倍数将答案加到对应的 $x$ 上。

这样我们就惊奇的发现你成功做完了这道题！时间复杂度是 $O(m\log m+n\log m)$ 的。前面是预处理，后面是 check 之后直接暴力扫一遍数组。

### 套路总结

1. 转化成 $\gcd$ 式子的形式。

2. 对 $\gcd$ 上莫反。

3. 推出更可做的形式（如数论分块）。

4. 解决原问题。

# 后记

均按出现顺序排列。

### 参考文献

* [排列组合 - OI-wiki](https://oi-wiki.org/math/combinatorics/combination/)

* [容斥原理 - OI-wiki](https://oi-wiki.org/math/combinatorics/inclusion-exclusion-principle/)

* [正演与反演模拟理解 -

奶茶派](https://blog.csdn.net/lijiwu666/article/details/132556991)

* [二项式反演及其应用 - GXZlegend](https://www.cnblogs.com/GXZlegend/p/11407185.html)

* [【瞎口胡】多步容斥和二项式反演 - Meatherm](https://www.cnblogs.com/Meatherm/p/16640448.html)

* [子集反演学习笔记 - Pbri](https://www.cnblogs.com/Pbriqwq/p/15429971.html)

* [【推导】子集反演的形式化推导 - 王学逸](https://www.cnblogs.com/wxywxywxy/p/15205488.html)

* [莫比乌斯反演 - OI-wiki](https://oi-wiki.org/math/number-theory/mobius/)

* [狄利克雷卷积和莫比乌斯反演 - 秋钧](https://zhuanlan.zhihu.com/p/646539446)

* [狄利克雷卷积和莫比乌斯反演 - Xecades](https://zhuanlan.zhihu.com/p/390895860)

### 公式合集

二项式定理

$$\boxed{(a+b)^n=\sum_{i=0}^n{n\choose i}a^ib^{n-i}}$$

容斥定理

$$\boxed{\left|\bigcup_{i=1}^n A_i\right|=\sum_{i}|A_i|-\sum_{i,j}|A_i\cap A_j|+\cdots+\sum(-1)^{n+1}\left|\bigcap_{i=1}^n A_i\right|}$$

二项式反演形式零

$$\boxed{

g(n)=\sum_{i=0}^n(-1)^i{n\choose i}f(i)\Leftrightarrow

f(n)=\sum_{i=0}^n(-1)^i{n\choose i}g(i)

}$$

二项式反演形式一

$$\boxed{

g(n)=\sum_{i=0}^n{n\choose i}f(i)\Leftrightarrow

f(n)=\sum_{i=0}^n(-1)^{n-i}{n\choose i}g(i)

}$$

二项式反演形式二

$$\boxed{

g(n)=\sum_{i=n}^N{i\choose n}f(i)\Leftrightarrow

f(n)=\sum_{i=n}^N(-1)^{i-n}{i\choose n}g(i)

}$$

子集反演形式一

$$\boxed{f(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}g(T)}$$

子集反演形式二

$$\boxed{f(T)=\sum_{T\subseteq S}(-1)^{|S|-|T|}g(S)}$$

狄利克雷卷积

$$\boxed{

(f\ast g)(x)=\sum_{d|x}f(d)g\left(\frac{n}{d}\right)\Leftrightarrow \sum_{ij=x}f(i)g(j)

}$$

单位元函数

$$\boxed{\epsilon(x)=[x=1]}$$

狄利克雷逆

$$\boxed{f\ast f^{-1}=\epsilon}$$

莫比乌斯函数

$$\boxed{\mu=\mathbf{1}^{-1}}$$

$$\boxed{\mu(x)=\begin{cases}

1 & x=1\\

0 & \exists p\in\mathbb{N}^+,p^2|x &\mathtt{即\space} x\mathtt{\space 含有平方因子}\\

(-1)^k & \mathtt{otherwise} & k\mathtt{\space 是\space} x \mathtt{\space 的素因子个数}

\end{cases}}$$

莫比乌斯反演形式一

$$\boxed{

g(x)=\sum_{d|n}f(d)\Leftrightarrow f(x)=\sum_{d|n}\mu\left(\frac{n}{d}\right)g(d)

}$$

莫比乌斯反演形式二

$$\boxed{

\sum_{d|\gcd(i,j)}\mu(d)=[\gcd(i,j)=1]

}$$