riteme.site莫比乌斯反演
我把《组合数学》抄了一遍，免得我记不住......
偏序集
这里的莫比乌斯反演是从关联代数的角度来介绍的。首先介绍一个基础的概念：偏序集。
它通常写作
所谓偏序关系，就是指
这种偏序关系一般是比较符
卷积
对于定义在偏序集
考虑偏序集
这个卷积满足结合律：
注意，这个卷积不一定1满足交换律。
以及三种强行定义的莫名其妙的函数：
任意函数卷
以及莫比乌斯
展开卷积可得：
因此，当
莫比乌斯反演公式
(莫比乌斯反演公式)
对于有限偏序集$(X_n,\;\leqslant)$ 上的两个函数$F(x,\;y)$ 和$G(x,\;y)$ ，如果：
$$ G(x,\;y) = \sum_{x \leqslant z \leqslant y} F(x,\;z) \tag{3.1}$$ 那么：
$$F(x,\;y) = \sum_{x \leqslant z \leqslant y} G(x,\;z)\mu(z,\;y) = (G \times \mu)(x,\;y) \tag{3.2}$$
证明 首先将式子展开：
我们使用
改变求和的枚举顺序，先枚举
由于当
同理，我们可以得出
因此可以改写下界：
然后变成了卷积的形式：
当
偏序集直积
对于两个偏序集
对于偏序集的直积，我们有以下定理：
设
$A$ 和$B$ 的莫比乌斯函数分别为$\mu_1$ 和$\mu_2$ ，那么$C$ 的莫比乌斯函数满足：
$$\mu((x_1,\;y_1),\;(x_2,\;y_2)) = \mu_1(x_1,\;x_2)\mu(y_1,\;y_2) \tag{4.1}$$
证明 对于
假设对于满足
(2016.12.22: 上述证明最后一步展开存在问题 (红色正号)，但是《组合数学》上没有这一步的详细推导，正确的证明方式还请大神们指出)
由于：
所以定理成立。
在$(X_n,\;\leqslant)$ 上的莫比乌斯函数
注意这里的是真正的小于等于号了......
这个比较智障，分析一下就好了：
对于
对于
对于
不难发现，对于
总结一下就是：
在$(X_n,\;\subseteq)$ 上的莫比乌斯函数
试证明：
偏序集$(X_n,\;\subseteq)$ 的莫比乌斯函数是：
$$\mu(A,\;B) = (-1)^{|B| - |A|} \tag{6.1}$$
运用归纳法证明：
首先对于
假设对于
在$(X_n,\;\mid)$ 上的莫比乌斯函数
对于
证明 我们尝试使用归纳法证明。首先对于
假设对于
根据莫比乌斯函数的性质可得：
由于
根据归纳假设，可以将上式变为：
因此定理成立。
由于有上面的定理，所以我们只用关心
首先可以递归计算：
考虑对
对于
相当于可以看作
于是可以得到：
注意到，对于
总结一下就是：
运用直积，可以知道：
为了方便，通常把
据此，我们可以证明莫比乌斯函数是积性函数，即：
证明：
1. 如果
2. 如果
3. 此时假设
反演示例：容斥原理
设
定义函数
即：
如何脑补这个函数？可以想象成是用
对于此，再定义函数
这货居然计数的是：
如何脑补其正确性？可以想象是一个智障用
根据莫比乌斯反演公式可以知道：
所以取
这个时候的
用
反演示例：$\varphi(n)$ 通项公式
欧拉
对于欧拉
有两种证明方法：
第一种考虑不与
另一种是使用归纳法证明：
首先考虑
然后考虑质数
考虑质数
所以我们对其进行等比数列求和：
故对质数的幂也成立。
假设对于一个数
下面证明
注意到
考虑一下
设
因此可以得到下面的式子：
这恰好是下面的式子展开的形式：
因此：
反演示例：多重集合的循环排列
我们有一个多重集合
$\{\infty \cdot 1,\;\infty \cdot 2,\;\dots,\;\infty \cdot k\}$ 。易知长度为$n$ 的全排列数为$k^n$ 。
现在对于两个排列$A$ 和$B$ ，如果$A$ 通过”旋转” (即将最后一个变成第一个，并且把之前的全部后移) 能变成$B$ ，那么$A$ 和$B$ 是等价的。
换言之，最小表示法相同的排列是等价。
求不同的长度为$n$ 的循环排列数量。
对于这个计数问题，我们记
那么可以知道：
由于循环节长度小于
所以：
根据莫比乌斯反演公式可得：
带入
由于
由于：
所以：
莫比乌斯函数示例：最大公约数
除了莫比乌斯反演公式，莫比乌斯函数本身的性质也是很好的。
考虑下面一个问题：
给定
$n$ 和$m$ ，求$\gcd(x,\;y)\;\;(1 \leqslant x \leqslant n,\;1 \leqslant y \leqslant m)$ 为素数的二元组$(x,\;y)$ 个数。
换言之，我们要求的是这个：
首先，我们可以换个思路，就是枚举最大公约数的答案：
由于
由于莫比乌斯函数有这样的性质：
所以可以使用莫比乌斯函数来测试一个数是否为
因为
现在东西越来越多了，是时候考虑简化一下了。
首先对于一堆和式的一个技巧就是调整枚举顺序。
尝试先枚举
其实这个式子已经可以用来计算答案了。注意到对于一个数
- 如果
$i \leqslant \sqrt{n}$ ，这样的$i$ 只有$O(\sqrt{n})$ 种。 - 如果
$i > \sqrt{n}$ ，那么$\lfloor n / i \rfloor \leqslant \sqrt{n}$ ，这样的取值只有$O(\sqrt{n})$ 种。
所以两个向下取整的乘积最多有
然而我们可以做得更快一些。
设
这样左边就可以在
枚举大概是这样的一个过程：
1 2 3 4 5 6 | lastpos = 0
i = 1
while i <= min(n, m):
lastpos = min(n / (n / i), m / (m / i))
# Do something...
i = lastpos + 1
|
我们企图能使右边快速计算。因此我们来研究一下右边这个玩意。
设：
考虑使用线性筛来计算
- 当
$x = 1$ 时，$g(x) = 0$ 。 - 当
$x$ 为素数时，$g(x) = 1$ 。 - 在线性筛的处理过程中，设当前数为
$i$ ，枚举到的素数为$p$ ，我们将要计算$g(ip)$ ：- 当
$\mu(i) = 0$ 时，说明$i$ 的质因数分解中至少存在一个一个素因子的次数大于$1$ 。
在这种情况下，除非只有一个素因子的次数为$2$ ，其它均为$1$ ，否则无论如何$g$ 的函数值都为$0$ 。
假设只存在一个素因子的次数为$2$ ，记这个素因子为$f(i)$ 。- 若
$p \mid i$ ，那么将会导致无论是哪个素因子，$\mu$ 函数的值都为$0$ 。因此$g$ 函数的值为$0$ 。 - 若
$p \nmid i$ ，那么就只有除以$f(i)$ 时会有值，此时的值为$\mu(i / f(i) \cdot p)$ 。
- 若
- 当
$\mu(i) \neq 0$ 时，意味着$i$ 将是多个素数之积。同样我们来考虑两种情况：- 若
$p \mid i$ ，那么就只有$p$ 的次数为$2$ ，此时$g(ip) = \mu(i)$ 。 - 若
$p \nmid i$ ，那么$\mu(ip)$ 依然不为$0$ 。假设$i$ 有$r$ 个素因子，那么$g(i) = r(-1)^{r-1}$ ，并且$g(ip) = (r + 1)(-1)^r = -r(-1)^{r-1} + (-1)^{r+1}$ ，这意味着它们符号相反且绝对值差$1$ 。这样就可以直接计算。
- 若
- 当
经过一番分类讨论，我们总算成功地找到了预处理
在这中间有一个问题还亟待解决，就是我们需要计算
假设存在这样的素因子
- 当
$x = 1$ 或$x$ 为质数时，$f(x) = 1$ 。 - 每次往一个数
$i$ 加入一个素数$p$ 时，需要考虑下面的情况：- 若
$f(i) = 0$ ，那么没救了。 - 若
$p \mid i$ ，并且$f(i) = 1$ ，那么$ip$ 将不再是素数连乘的形式，此时可以记下$f(ip) = p$ 。如果$f(i) > 1$ ，那么它没救了。 - 若
$p \nmid i$ ，那么$f$ 函数值不会改变。
- 若
这样就可以欢快地计算
回到之前的问题，我们能够计算
莫比乌斯函数示例：DIVCNT2
要求求出：
$$ \sum_{a = 1}^n \sigma(a^2) $$ 的值。其中
$\sigma(n)$ 表示$n$ 的因子个数。
考虑这么几个等式关系：
其中
考虑到
因此：
即只要是
对于省去了第一维的数论函数
也就是在偏序集
利用卷积的结合律，可以得到：
注意到：
所以，我们要求的东西也就是：
首先考虑
由于下取整可以分段，所以可以在
然后考虑
这是为什么？结合
回到之前的式子：
对于
所以最后的复杂度可以这样估计：
显然右边的代价更高。用积分可以估计一下：
如果预处理前
当
当
-
在偏序集
$(X_n,\;\mid\;)$ 上简化后的卷积 (即狄利克雷卷积)，会满足交换律。 ↩