前置知识

积性函数

满足 \(f(1)=1\)，并且当 \(\gcd(a,b)=1\) 时，有 \(f(ab) = f(a)f(b)\)，则称 \(f(n)\) 为积性函数。

如果对于全部的 \(a,b\)，都有 \(f(ab)=f(a)f(b)\)，则称 \(f(n)\) 是完全积性函数。

常见积性函数

常数函数：\(1(x)=1\)（完全积性）
恒等函数 \(id_k(n)=n^k,id_1(n)\) 简记为 \(id(n) = n\)
元函数：\(\varepsilon(n) = [n=1]\)
欧拉函数：\(\varphi(n)\)
因子函数：\(d(n)=\prod_1^k(a_i+1),a_i\)是质因数分解后质因子 \(p_i\) 的幂次。
除数函数：\(\sigma(n)=\sum_{d|n}d\)
莫比乌斯函数：

\[\mu(n) = \left\{ \begin{aligned} &1,\ \ \ \ \ \ \ \ n=1\\ &(-1)^s,n=p_1p_2\dots p_s\\ &0,\ \ \ \ \ \ \ \ n\text{包含相同质因子} \end{aligned} \right. \]

两个积性函数的性质

欧拉函数

定义

用一个式子表达就是

\[\varphi(n) = \sum_{i=1}^n[\gcd(i,n)=1] \]

性质

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

证明在我这篇博客里有。

莫比乌斯函数

定义

\[\mu(n) = \left\{ \begin{aligned} &1,\ \ \ \ \ \ \ \ n=1\\ &(-1)^s,n=p_1p_2\dots p_s\\ &0,\ \ \ \ \ \ \ \ n\text{包含相同质因子} \end{aligned} \right. \]

性质

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

也就是说除了 \(n=1\) 的时候这个式子是 \(1\) ,其余的都是 \(0\)。

证明：

当 \(n=1\) 时， \(\mu(1) = 1\)

当 \(n>1\) 时，将 \(n\) 质因数分解得到 \(n=p_1^{a_1}p_2^{a_2}\dots p_s^{a_s}\)，令 \(n'=p_1p_2\dots p_n\)，那么有

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

因为如果有幂次 \(>2\) 的因数函数值是 \(0\)，所以可以直接舍掉了。

剩下的就直接运用容斥原理解决。

不取任何质因子的方案数为 \(C_s^0\)

不取任何质因子的方案数为 \(C_s^1\)

不取任何质因子的方案数为 \(C_s^2,\dots\)

所以最后的答案

\[= (-1)^0C_s^0+(-1)C_s^1+(-1)^2C_s^2+\dots+(-1)^sC_s^s \]

\[=(1+(-1))^s = 0 \]

这个性质往往是逆用的，比如给你一个 \([x=k]\)，我们就可以把它转化成 \(\displaystyle \sum_{d|\lfloor \frac{x}{k}\rfloor}\mu(d)\)。

两个函数的联系

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

证明：

\(n=1\) 时，\(\varphi(1)=\mu(1)=1\)；

\(n>1\) 时，\(n=p_1^{a_1}p_2^{a_2}\dots p_s^{a_s}\)，令 \(n'=p_1p_2\dots p_n\)，那么有

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

这其中 \(\mu(d)\) 决定着符号，根据容斥原理，原式

\[\begin{aligned} &=n\Bigg(1-\Bigg(\frac{1}{p_1}+\dots+\frac{1}{p_s}\Bigg)+\Bigg(\frac{1}{p_1p_2}+\dots+\frac{1}{p_{s-1}p_s}\Bigg)-\dots\Bigg)\\ &=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots(1-\frac{1}{p_s})\\ &= \varphi(n) \end{aligned} \]

其中最后这一步的证明在这。

和式的变换

学会和式的变换有助于我们更好地推式子。

和式的变换规则

分配律

\[ \sum_{k\in K}ca_k = c\sum_{k\in K} a_k \]
结合律

\[ \sum_{k\in K}(a_k+b_k) = \sum_{k\in K}a_k + \sum_{k\in K} b_k \]
交换律

\[ \sum_{k\in K}a_k = \sum_{p(k)\in K}a_{p(k)} \]
\(p_k\) 指的是标集的任意一个排列

例如，\(a_1+a_2+a_3+a_6=a_6+a_2+a_3+a_1\)

和式的变换魔术

替换条件式
\[ \sum_{i=1}^n\sum_{j=1}^m\sum_{d|\gcd(i,j)}d = \sum_{i=1}^n\sum_{j=1}^m\sum_{d=1}^{\min(n,m)}[d|i] [d|j] d \]
替换指标变量
\[ \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k] = \sum_{i=1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}[\gcd(i,j)=1] \]
交换求和次序
\[ \sum_{i=1}^n\sum_{j=1}^mA(i)B(j)=\sum_{j=1}^m\sum_{i=1}^nA(i)B(j) \]
分离变量
\[ \sum_{i=1}^n\sum_{j=1}^mA(i)B(j)=\sum_{i=1}^nA(i)\sum_{j=1}^mB(j) \]

狄利克雷卷积

定义

\(f(n),g(n)\) 是两个积性函数，那么

\[(f * g)(n) = \sum_{d|n}f(d)g(\frac{n}{d})=\sum_{n|d}f(\frac{n}{d})g(d) \]

比如 \((f * g)(4) = f(1)g(4) + f(2)g(2) + f(4)g(1)\)

性质

交换律：\(f * g = g* f\)
结合律：\((f * g) * h = f * (g * h)\)
分配律：\((f+g) * h = f * h + g * h\)

常用卷积关系

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

证明：

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

\[\sum_{d|n}\varphi(d)=n \Leftrightarrow \varphi * 1 = id \]

证明：

\[(\varphi * 1)(n) = \sum_{d|n}\varphi(d)1(\frac{n}{d}) = \sum_{d|n}\varphi(d) = n = id(n) \]

\[\sum_{d|n}\mu(d)\frac{n}{d}=\varphi(n) \Leftrightarrow \mu * id = \varphi \]

证明：

\[(\mu * id)(n) = \sum_{d|n}\mu(d)id(\frac{n}{d}) = \sum_{d|n}\mu(d)\frac{n}{d} = \varphi(n) \]

\[f * \varepsilon = f \]

证明：

\[(f * \varepsilon)(n) = \sum_{d|n}f(d)\varepsilon(\frac{n}{d}) = \sum_{d|n}f(d)[\frac{n}{d}=1] = f(n) \]

这说明 \(\varepsilon\) 是狄利克雷卷积的单位元。

莫比乌斯反演

定义

若 \(f(n),g(n)\) 均为积性函数，则有

\[f(n) = \sum_{d|n}g(d) \Leftrightarrow g(n) = \sum_{d|n}\mu(d)f(\frac{n}{d}) \]

\(f(n)\) 称为 \(g(n)\) 的莫比乌斯变换；

\(g(n)\) 称为 \(f(n)\) 的莫比乌斯逆变换。

证明：

\(\text{Method 1}\)（卷积角度）

充分性：

若 \(f = g * 1\)，则 \(\mu * f = \mu * g * 1 = g * \mu * 1 = g * \varepsilon = g\)

必要性：

若 \(g = \mu * f\)，则 \(g * 1 = \mu * f * 1 = f * \mu * 1 = f * \varepsilon = f\)

\(\text{Method 2}\)（交换和号推式子）

这里只证明充分性，详细的证明可见这里

充分性：

\[\begin{aligned} &\ \ \ \ \ \sum_{d|n}\mu(d)f(\frac{n}{d})\\ &=\sum_{d|n}\mu(d)\sum_{k|\frac{n}{d}}g(k) \ \ (\text{代入充分性的条件}) \\ &=\sum_{d|n}\sum_{k|\frac{n}{d}}\mu(d)g(k)\\ &=\sum_{k|n}\sum_{d|\frac{n}{k}}\mu(d)g(k)\\ &=\sum_{k|n}g(k)\sum_{d|\frac{n}{k}}\mu(d) = g(n) \end{aligned} \]

其中第三行到第四行采用的交换和号的方式，可以列一个表格感性证明一下，可以看出先枚举行和先枚举列最终的结果是相同的。

但是好像有关 \([\gcd() = k]\) 的用黄金代换式更简单。

欧拉反演

其实也是一类套路。

对于类似 \([\gcd() = k]\) 这一类题，我们常常利用黄金代换，也就是反演的一类把这个式子用莫比乌斯函数表示出来，那么对于 \(\gcd(i,j)\) 一类的题，我们就可以类似的用欧拉函数来表示。

莫比乌斯反演运用了 \(\mu * 1 = \varepsilon\) 的性质，而欧拉反演运用的就是 \(\varphi * 1 = id\) 的性质。

求解下面的式子（默认 \(n\leq m\)）

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

因为欧拉函数具有 \(\displaystyle \sum_{d|n}\varphi(d) = n\) 的性质，所以我们把 \(\gcd(i,j)\) 看作 \(n\)，就有

\[\begin{aligned} &\ \ \ \ \ \sum_{i=1}^n\sum_{j=1}^m\sum_{d|\gcd(i,j)}\varphi(d)\\ &=\sum_{i=1}^n\sum_{j=1}^m\sum_{d=1}^n[d|i][d|j]\varphi(d)\\ &=\sum_{d=1}^n\varphi(d)\sum_{i=1}^n[d|i]\sum_{j=1}^m[d|j]\\ &=\sum_{d=1}^n\varphi(d)\lfloor \frac{n}{d} \rfloor\lfloor \frac{m}{d} \rfloor \end{aligned} \]

\(\varphi(d)\) 可以线性预处理，这个式子可以 \(O(\sqrt n)\) 整除分块，于是复杂度就降下来了。

一些常见的变换套路

黄金代换

\[ [\gcd(i,j)=1] = \sum_{d|\gcd(i,j)}\mu(d) \]
莫比乌斯函数性质的逆运用。
转艾佛森括号

\[ d|\gcd(i,j)\rightarrow [d|i][d|j] \]
以一式举例

\[\sum_{d|\gcd(i,j)}\mu(d)=\sum_{d=1}^n[d|i][d|j]\mu(d) \]
套着求和式外壳的常数

\[ \sum_{i=1}^n[d|i] = \lfloor \frac{n}{d} \rfloor \]
等号左边的实际意义就是让你求 \(1\sim n\) 中 \(d\) 的倍数的个数，那显然就是 \(\lfloor \frac{n}{d} \rfloor\) 个。
一个我也不知道叫啥的变换

\[ \sum_{k=1}^n\sum_{d=1}^{\lfloor \frac{n}{k} \rfloor}\mu(d)\lfloor \frac{n}{kd} \rfloor\lfloor \frac{m}{kd} \rfloor \rightarrow \sum_{k=1}^n\sum_{T=1}^n\mu(\frac{T}{k})\lfloor \frac{n}{T} \rfloor\lfloor \frac{m}{T} \rfloor \]
通过设 \(T=kd\)，来把下取整里面的两个变量转化为只有一个变量，方便我们进行整除分块。
有关 \([\gcd(i,j)=1]\) 的套路（默认 \(n\leq m\)）

\[ \begin{aligned} &\ \ \ \ \ \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1]\\ &=\sum_{i=1}^n\sum_{j=1}^m\sum_{d|\gcd(i,j)}\mu(d)\\ &=\sum_{i=1}^n\sum_{j=1}^m\sum_{d=1}^n[d|i][d|j]\mu(d)\\ &=\sum_{d=1}^n\mu(d)\sum_{i=1}^n\sum_{j=1}^m[d|i][d|j]\\ &=\sum_{d=1}^n\mu(d)\sum_{i=1}^n[d|i]\sum_{j=1}^m[d|j]\\ &=\sum_{d=1}^n\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor \end{aligned} \]
于是可以 \(O(n)\) 预处理 \(\mu(n)\)，后面两项整除分块即可。

通过整理式子，我们将一个 \(O(n^2)\) 的式子优化到了 \(O(n+\sqrt n)\)。
升级版 \(5\)

\[\begin{aligned} &\ \ \ \ \ \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k]\\ &\ \ \ \ \ i,j \ \text{同时除以}\ k\\ &=\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)\\ \end{aligned} \]
后面的就都一样了，注意枚举范围即可。
升级版 \(6\)

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

\(i,j\) 同时除以 \(k\)

\[\begin{aligned} &=\sum_{i=1}^{\lfloor \frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{k}\rfloor}k^2[\gcd(i,j)=1]\\ &=\sum_{i=1}^{\lfloor \frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{k}\rfloor}k^2\sum_{d|\gcd(i,j)}\mu(d)\\ \end{aligned} \]
你会发现多了一个 \(k^2\)，这是为什么呢？因为你还要考虑 \(i,j\) 的贡献，你同时除以 \(k\) 了就要乘上原来应该有的 \(k^2\) 的贡献。

一个结论
\[d(ij) = \sum_{x|i}\sum_{y|j}[\gcd(x,y)=1] \]
证明思路大致是构造一个双射，一一对应。

二项式反演

应该是运用最广泛的一个反演类型。

为什么叫二项式反演？因为它由二项式定理推过来的，并且式子也比较相似。

前置

首先我们知道二项式定理

\[(a+b)^n = \sum_{i=0}^n\binom{n}{i}a^{n-i}b^i \]

我们令 \(a=1,b=-1\)，就得到我们的推论式

\[\sum_{i=0}^n(-1)^i\binom{n}{i} = [n=0] \]

这里因为 \(0^0\) 没有意义，我们给它定义成 \(0^0 =1\)，其余的 \(0^k\) 都是 \(0\)。

二项式反演

先给出式子

\[f(n) = \sum_{i=0}^n\binom{n}{i}g(i) \Longleftrightarrow g(n) = \sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f(i) \]

简单证明一下，只证明从左边推右边

\[\begin{aligned} &\ \ \ \ \ \sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f(i)\\ &=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}\sum_{j=0}^i\binom{i}{j}g(j)\\ &=\sum_{i=0}^n\sum_{j=0}^i(-1)^{n-i}\binom{n}{i}\binom{i}{j}g(j)\\ &=\sum_{j=0}^n\sum_{i=j}^n(-1)^{n-i}\binom{n}{i}\binom{i}{j}g(j)\\ &=\sum_{j=0}^n\sum_{i=j}^n(-1)^{n-i}\binom{n}{j}\binom{n-j}{i-j}g(j)\\ &=\sum_{j=0}^n\binom{n}{j}g(j)\sum_{i=j}^n(-1)^{n-i}\binom{n-j}{i-j}\\ &=\sum_{j=0}^n\binom{n}{j}g(j)\sum_{i=0}^{n-j}(-1)^{n-j-i}\binom{n-j}{i}\\ &=\sum_{j=0}^n\binom{n}{j}g(j)[n=j]=g(n) \end{aligned} \]

其中第三行到第四行是一个和式的变换。你可以把它想象成一个下三角，本来是先行再列枚举，变换后就变成了先列后行。

第六行到第七行就是枚举范围的变化，令 \(i\) 变为 \(i+j\)，相应的范围也发生变化。然后就套用我们的推论式就可以了。

应用

二项式反演往往可以抽象成两种模型。

恰好 \(\rightarrow\) 至多型

设 \(g(m)\) 代表恰好满足条件 \((=m)\)，剩下的不满足的方案数，也就是答案。

再设 \(f(m)\) 表示至多满足条件 \((\leq m)\) 的方案数。

这种题往往 \(f(m)\) 是好求的，我们先求出 \(f(m)\)，再反演求 \(g(m)\)

\[f(m)=\sum_{i=0}^m\binom{m}{i}g(i) \Rightarrow g(m) = \sum_{i=0}^m(-1)^{m-i}\binom{m}{i}f(i) \]

恰好 \(\rightarrow\) 至少型

设 \(g(m)\) 代表恰好满足条件 \((=m)\) ，剩下的不满足的方案数，也就是答案。

再设 \(f(m)\) 表示钦定 \(m\) 个元素满足条件 \((\leq m)\)，剩下的随便选的方案数。

同理，这种题往往 \(f(m)\) 是好求的，我们先求出 \(f(m)\)，再反演求 \(g(m)\)

\[f(m)=\sum_{i=m}^n\binom{i}{m}g(i) \Rightarrow g(m) = \sum_{i=m}^n(-1)^{i-m}\binom{i}{m}f(i) \]

其中 \(\displaystyle \binom{i}{m}\) 我们可以理解为，我们钦定了其中 \(m\) 个满足限制，那么对于一个满足了 \(k \ge m\) 个限制的方案，它就会被我们算 \(\binom{k}{m}\) 次，因此要乘一个系数。

这其实是二项式反演的另一种性质，上界变而不是下界，我们再简单证明一下。

\[\begin{aligned} &\ \ \ \ \ \sum_{i=m}^n(-1)^{i-m}\binom{i}{m}f(i)\\ &=\sum_{i=m}^n(-1)^{i-m}\binom{i}{m}\sum_{j=i}^n\binom{j}{i}g(j)\\ &=\sum_{i=m}^n\sum_{j=i}^n(-1)^{i-m}\binom{j}{i}\binom{i}{m}g(j)\\ &=\sum_{j=m}^n\sum_{i=m}^j(-1)^{n-i}\binom{j}{m}\binom{j-m}{i-m}g(j)\\ &=\sum_{j=m}^n\binom{j}{m}g(j)\sum_{i=0}^{j-m}(-1)^{i-m}\binom{n-j}{i-j}\\ &=\sum_{j=0}^n\binom{n}{j}g(j)\sum_{i=0}^{n-j}(-1)^i\binom{j-m}{i}\\ &=\sum_{j=m}^n\binom{j}{m}g(j)[j=m]=g(m) \end{aligned} \]

例题

\(n\) 个人 \(n\) 封信，求全部装错的方案数

这是一个典型的错排问题，但是我们也可以用二项式反演来得出答案。

设 \(g(n)\) 表示恰好 \(n\) 个装错的方案数，这也是我们想求出的，但是它并不好直接求出。

设 \(f(n)\) 代表至多 \(n\) 个装错的方案数，这个很好求，答案就是全排列，因为每一种方案都符合要求，并且 \(f(n)\) 和 \(g(i)\) 有如下关系

\[f_n = \sum_{i=0}^n\binom{n}{i}g_i \]

你会发现这符合二项式反演的式子，于是 \(g(n)\) 就可以求解了。

\[\begin{aligned} g(n) &= \sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f_i\\ &=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}i!\\ &=\sum_{i=0}^n\frac{(-1)^{n-i}n!}{(n-i)!}\\ &=\sum_{i=0}^n\frac{(-1)^{i}n!}{i}\\ \end{aligned} \]

于是这题就做完了。