反演入门学习笔记
UniGravity
·
2024-09-18 19:01:59
·
算法·理论
前言
非常古老的存货了，怎么现在才想起来交/kk
资料主要来源于网上（oi-wiki、知乎、博客园）。
闲话
本篇文章主要以感性理解为主，大部分补充的证明部分会以链接形式给出（绝对不是笔者不会证明），一些较为容易理解的证明会直接写出。其实个人认为，这一类算法只需要大致理解思想，然后会运用式子就好。
简要目录
Part 1. 二项式反演
反演概述
什么是反演？f 推出 g ，则称之为正演 。那么将其倒过来，用 g 反推出 f 就叫做反演 了。形象生动的解释：正演与反演模拟理解 by
奶茶派。
反演的作用？
\footnotesize\text{答案}\stackrel{正演}\longrightarrow某个式子\stackrel{简单处理}\longleftarrow题目条件
\footnotesize\text{答案}\stackrel{\textbf{反演}}\longleftarrow某个式子\stackrel{简单处理}\longleftarrow题目条件
在 OI 中，反演一般长这样：
g_n=\sum 一堆系数\cdot f_i \longleftrightarrow f_n=\sum 一堆系数\cdot 用于去重的新式子\cdot f_i
可以发现这里的 g 是从一堆 f 加起来的，所以反演时需要进行去重。在二项式反演中，用于去重的就是 (-1)^x ，而在莫反中则变成了莫比乌斯函数 \mu(x) 。
二项式反演
理论
为什么要学二项式反演
二项式反演常用于解决至多 （至少 ）和恰好 之间的转换，常用于统计方案数。恰好 后是能较为容易的推出至多 的，我们这里先写一个式子（看不懂没关系下文有解答）：
g(n)=\sum_{i=0}^n{n\choose i}\cdot f(i)
对柿子的解释
为什么会有 $n\choose i$ 呢？这是因为**任意**的 $i$ 个都能对产生 $f(i)$ 种方案，所以需要乘上 $n$ 中选 $i$ 个的方案数。
在题目中，一般 g 是较为好求的。那么接下来我们就要解决：如何从 g 反推回 f ？
从二项式定理到容斥定理再回到二项式反演
注：下面讲述得出二项式定理的证明过程，可以略过直接跳步到二项式反演全家桶 处。
这里推荐两篇文章，有详细的证明过程：
二项式反演及其应用 by GXZlegend
【瞎口胡】多步容斥和二项式反演 by Meatherm
\boxed{(a+b)^n=\sum_{i=0}^n{n\choose i}a^ib^{n-i}}
证明很妙，简单写一下：
将其拆开：(a+b)^n=(a+b)(a+b)\cdots(a+b) a 或选 b ，这样就一共有 2^n 种可能，每种的贡献是 1 。i 个 a ，一共就有 n\choose i 个选法，也就是这一项的贡献就是 n\choose i ！剩余的只能选择 b ，于是就有 {n\choose i}a^ib^{n-i} 。
将 i 从 0 枚举到 n ，就证完了！
那么它和容斥定理又有什么关系呢？
\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|}
简单来说，就是选 1 个的方案减去任意选 2 个的方案加上选 3 个的方案 \cdots
感性证明？假设一个元素出现在 c 个集合中，那么左侧柿子由于是集合并 起来，所以不管出现几次都只有 1 的贡献。那么我们只需要让右边的贡献也为 1 就全对了！i ，乘上容斥系数 (-1)^{i+1} ，这个时候你发现 i 个的选法就是从 c 中选，那么就有这个柿子：
\sum_{i=1}^c(-1)^{i+1}{c\choose i}=-\sum_{i=1}^c(-1)^i{c\choose i}
发现 i=1 其实不如 i=0 好做，于是你再加入一个：
(-1)^0{c\choose 0}-\sum_{i=0}^c(-1)^i{c\choose i}=1-\sum_{i=0}^c(-1)^i{c\choose i}
这个时候你发现 \sum_{i=0}^c(-1)^i{c\choose i} 的形式特别和上文 \sum_{i=0}^n{n\choose i}a^ib^{n-i} 相似，考虑转化：
1-\sum_{i=0}^c{c\choose i}(-1)^i1^{c-i}=1-(-1+1)^c=1-0=1)
证毕，对完了！
容斥？反演！
沿用一下刚刚证明的公式：
\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|
小学数学告诉我们，补集的交等于并的补集。记 A_i 补集是 B_i ，于是我们改写一下：
\left|\bigcap_{i=1}^nB_i\right|=|U|-\sum_{i}|A_i|+\sum_{i,j}|A_i\cap A_j|-\cdots+\sum(-1)^n\left|\bigcap_{i=1}^n A_i\right|
而补集的补集变成了原集，于是将 B_i 和 A_i 互换有：
\left|\bigcap_{i=1}^nA_i\right|=|U|-\sum_{i}|B_i|+\sum_{i,j}|B_i\cap B_j|-\cdots+\sum(-1)^n\left|\bigcap_{i=1}^n B_i\right|
这两者只是 A,B 定义上的区别，系数完全一样，能不能把它们联系起来呢？f(i) 表示 i 个 A 集合的交集大小，g(i) 表示 i 个 B 集合的交集大小。这里是一种特殊情况：即任意的 i 个集合 A 交起来是的大小相等，但同样也满足上面那个柿子。
g(n)=\sum_{i=0}^n(-1)^i{n\choose i}f(i)
看起来非常的对称。需要注意的是，其中的 f(0)=g(0)=|U| ，这样就能与上述式子相符了。
注意 ：在真正做题的时候，我们只知道 f,g ，而无需考虑上面证明时提到的集合 。换句话说，这只是一种较为简单易懂的证明方式，二项式反演虽然形式上和多步容斥极为相似，但它们并不等价 。
二项式反演全家桶
形式 0（其实并不常用）：
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)
}
形式 1（至多与恰好的转换）：
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)
}
证明：h(i)=(-1)^if(i)
\frac{h(n)}{(-1)^n}=\sum_{i=0}^n(-1)^{n-i}{i\choose n}g(i)
形式 2（至少与恰好的转换，非常常用）：
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)
}
证明先咕着，可以看推荐阅读材料。
值得注意的是，其实式子中的 N 应该被 +\infty 代替，但是题目中一般大于 N 的 g 就没有值了，对答案没有贡献，可以省略。
例题
BZOJ2839 集合计数
一个有 N 个元素的集合有 2^N 个不同子集（包含空集），现在要在这 2^N 个集合中取出若干集合（至少一个），使得它们的交集的元素个数为 K ，求取法的方案数，答案模 10^9+7 。
发现元素个数恰好是 k 很不好做，考虑使用二项式反演转化成至少 k 个 。
假设 g(x) 表示交集至少有 x 个元素的方案数。首先发现的是包含这 x 个元素的集合一共会有 2^{n-x} 个，由于是交集，只需要在这些集合中选出若干个即可，方案数是 2^{2^{n-x}}-1 ，因为如果都不选就不满足至少一个的条件。x 个元素可以从 n 中任意选择 ，所以答案其实是 g(x)={n\choose x}(2^{2^{n-x}}-1) 。
直接上形式二 ：
f(k)=\sum_{i=k}^n(-1)^{i-k}{i\choose n}g(i)
复杂度是 O(n\log n) 的，非常优秀。
但是这样就做完了吗？你会发现你喜提 WA 30pts。2^{2^{n-x}}-1 是要 \bmod P\ (P=10^9+7) 的。此时内部的 2^{n-x} 就不是 \bmod P 而是 \bmod(P-1) 了。
为什么？x^{p-1}\bmod p=1 ，就有 x^c\bmod p=x^{\left\lfloor\frac{c}{p-1}\right\rfloor(p-1)+c\bmod(p-1)}\bmod p=x^{c\bmod(p-1)}\bmod p
P5505 [JSOI2011] 分特产
注：这题并不完全算二项式反演，而和容斥关系更大。不过使用二项式反演有助于更好理解题目含义。
有 n 个有标号的盒子和 m 种有标号的球，每种球有 a_i 个，求每个盒子至少放一种球的总方案数。
套路地，设 g(x) 表示钦定（也就是至少）x 个盒子为空的方案数，这样其他的盒子就可以随便选了。n 个盒子放 m 个球的方案数是 n+m-1\choose n-1 ，即 n+m-1 个空隙中任意插板子。那么有：
g(x)={n\choose x}\times\prod_{i=1}^m{a_i+n-i-1\choose n-i-1}
解释：前面的组合数是因为盒子是有标号的，后面的式子可以根据乘法原理得出。
接下来就到了二项式反演的重点：至少转恰好 。这里求恰好 0 个盒子为空，套用形式二，则有：
f(0)=\sum_{i=0}^{n-1}(-1)^ig(i)
P4859 已经没有什么好害怕的了
反演 + dp 好题。
给出长度为 n 的序列 a,b ，要求两两配对使得 a>b 的对数量减去 a<b 的对数量恰为 k ，求方案数。
发现直接做是困难的，因为不确定如何匹配。考虑可以先钦定 x 个数对满足 a_i>b_i ，剩下的随意排列，乘上 (n-x)! 。当然，这样只能算出至少 x 个满足的情况，只需进行二项式反演即可。
考虑怎么求方案数，首先对 a,b 排序，便于找出存在多少个 b_j<a_i （记为 c_i ），直接用 lowerbound 即可。记 $g {i,j} 表示考虑到 a_i（已排序），钦定了 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)}
那么我们直接开始例题。
例题
一个规律是，由于子集反演需要枚举子集，其较高的时间复杂度使得一般题目的数据范围都较小。
莫比乌斯反演
理论
从狄利克雷卷积开始
注：初学可能较为困难，仅作为理解。可以跳过（直接到例子 处）。
(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<m$（不满足直接 swap）。
> 还记得吗？
> $$\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]
}$$