莫反的几种形式的统一
Missa
·
·
算法·理论
《具体数学》（4.61）是一个反演法则
g(x) = \sum\limits_{d \geq 1} f(x / d) \iff f(x) = \sum_{d \geq 1} \mu(d) g(x / d)
其中 x / d 看作 \lfloor \frac{x}{d} \rfloor。
联想到 OI 中常见的两种莫比乌斯反演：
f(x) = \sum_{d \mid x} g(d) \iff g(x) = \sum_{d \mid x} \mu(x / d) f(d)
f(x) = \sum_{x \mid d} g(d) \iff g(x) = \sum_{x \mid d} \mu(d / x) f(d)
现在来找函数 \varphi(x, d) 的一个较好的性质使得
f(x) = \sum_{d \geq 1} g(\varphi(x, d)) \iff g(x) = \sum_{d \geq 1} \mu(d) f(\varphi(x, d))
恒成立。
不妨认为在莫反的第一个例子中
\varphi(x, d) =
\begin{cases}
\frac{x}{d} & d \mid x \\
0 & d \nmid x
\end{cases}
同时不妨让 f(0) = g(0) = 0。
观察证明过程
\begin{aligned}
\sum_{d \geq 1} \mu(d) g(x / d) = & \sum_{d \geq 1} \mu(d) \sum_{k \geq 1} f((x / d) / k) \\
= & \sum_{d \geq 1} \mu(d) \sum_{k \geq 1} \mu(d) f(x / dk) \\
= & \sum_{m \geq 1} f(x / m) \sum_{d, k \geq 1} \mu(d) [m = kd] \\
= & \sum_{m \geq 1} f(x / m) \sum_{d \mid m} \mu(d) \\
= & f(x)
\end{aligned}
将 x/d 换成 \varphi(x, d) 时，仅有第一行到第二行、第四行到第五行不是纯粹的代数恒等变换。
第四行到第五行需要的条件是 \varphi(x, 1) = x，第一行到第二行需要的条件是 \varphi(\varphi(x, d_1), d_2) = \varphi(x, d_1d_2)。代进去后手动验算确实得到 f(x)。
在《具体数学》给出的例子中，\varphi(x, d) = \lfloor \frac{x}{d} \rfloor。莫反的第一种常见形式中的 \varphi(x, d) 已在前面提及。在莫反的第二种常见形式中，\varphi(x, d) = xd。容易验证它们均满足上一段的两条性质。因此，通过研究一个 \varphi(x, d)，我们实现了三种常见形式的莫反的统一。
我认为这应该是容易发现的，但是因为我学习莫反时两种形式被分别列出，这里姑且写下这些东西。