Möbius inversion, Möbius transformation and Inclusion-Exclusion on Posets
Möbius inversion, Möbius transformation and Inclusion-Exclusion on Posets
pre
在算法竞赛中，Möbius反演主要出现在:一类推式子题用于数论分块优化/偏序集上的容斥/求解积性函数和Dirichlet卷积相关问题。而Möbius变换经常是解决位运算卷积之类的问题。
这篇blog主要用于梳理数论上这Möbius反演这及一些前置的知识，进一步的运用，以及Möbius变换的部分内涵，两种操作之间的联系。以及一些习题和其中的trick。
Part 1. Möbius inversion
前置知识
1. 积性函数
在数论中，算术函数（或称数论函数）指定义域为正整数、陪域为复数的函数，每个算术函数都可视为复数的序列。
这篇blog讨论的所有函数都是数论函数
积性函数：
如果一个函数\(f\)具有性质\(\forall( a,b,\gcd(a,b) = 1), f(ab) =
f(a)f(b)\)，那么就称这个函数是积性函数。
如果一个函数\(f\)具有性质\(\forall(a,b),f(ab) =
f(a)f(b)\),那么称这个函数为完全积性函数。
一下是一些例子：
\(I，I(x) = 1\) ，常数函数。
\(id_k,id(x) = x^k\) ，幂函数，\(id = id_1\)即恒等函数。
\(\epsilon,\epsilon(x) = [x == 1]\)
,单位函数。
\(\sigma_k,\sigma_k(x) = \sum_{d|x}
d^k\) ,约数幂函数
\(d = \tau = \sigma_0\) ,除数函数
\(\phi ,\phi(x) = \sum_{a \nmid x}1\)
,欧拉函数
积性函数的特点是可以通过质数幂处的函数值快速得到任意位置的函数值。
几乎所有积性函数都可以通过欧拉筛线性求解\([1,n]\)的函数值(通过枚举每个数的最小质因子实现转移)。
2. Dirichlet卷积
定义两个函数的Dirichlet卷积为：
\[ (f * g)(n) =
\sum_{d|n}f(d)g(\frac{n}{d})\]
Dirichlet卷积有如下性质：
1. 交换律 \(f*g = g*f\)
2. 结合律 \((f*g)*h = f*(g*h)\)
3. 分配律 \((f + g)*h = f*h +
g*h\)
4. 消去律 \(f = g \Leftrightarrow f*h =
g*h\)，其中\(h(1) \neq 0\)
5. 单位元 \(f * \epsilon = f\)
6. 逆元 \(f * g = \epsilon\)，\(f,g\)互为逆元，逆元唯一，用\(f^{-1}\)表示。
7. \(f,g\)是积性函数，那么\(h = f*g\)也是积性函数。
证明可以证\(h(ab)=h(a)h(b)\)
8. \(f\)是积性函数，那么\(f^{-1}\)是积性函数。
9. 和函数\(F = f*I ,F(n)
= \sum_{d|n}f(d)\)
10. 由前面的推论，全体积性函数和Dirichlet卷积构成一个阿贝尔群\((G,*)\)，单位元是\(\epsilon\)。
莫比乌斯反演
首先引入莫比乌斯函数。
莫比乌斯函数是Dirichlet卷积意义下 \(I\)
的逆元。
有：
\[\begin{align*}
\mu(n)=\left\{
\begin{array}{ll}
1&n=1\\
0&\exists p,p^2 | n\\
(-1)^k&n = p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}\\
\end{array}
\right.
\end{align*}\]
由前面给出的和函数的定义，我们有：
\[F = f * I \Leftrightarrow f = \mu *
F\]
实际上，由 \(f\) 得到 \(F\)
是整除偏序上的zeta变换，而我们反过来，利用\(\mu\)由 \(F\) 得到 \(f\)
的过程称为莫比乌斯反演，这是莫比乌斯变换在整除偏序上的运用。
莫比乌斯反演公式：
\[ f(n) = \sum_{d | n}
F(d)\mu(\frac{n}{d})\]
莫比乌斯反演可以用于计算一些和整除偏序相关的容斥问题，和一些转化式子为更容易快速求值/预处理多次回答询问的问题。
以下是一些有关的式子和结论，常见于这些题目中。
1. \(\mu*I = \epsilon ,\sum_{d|n} \mu(d) =
1\)
常用于\([\gcd(i,j) = 1] = \sum_{d|\gcd(i,j)}
\mu(d) = \sum_{d|i,d|j}\mu(d)\).
2. \(\phi*I = id\)
常用于\(gcd(i,j) = \sum_{d|\gcd(i,j)}\phi(d) =
\sum_{d|i,d|j}\phi(d)\)，即\(\gcd\)拆解为\(\phi\)卷积。
3. \(id_k * I = \sigma_k \Leftrightarrow \mu *
\sigma_k = id_k\)
4. \(\sum_{i = 1}^{n} d(i) = \sum_{k =
1}^{n} \left\lfloor\frac{n}{k}\right\rfloor\)
这是对\(d\)的单点前缀和函数值的两种计算方法，前者可以线性预处理\([1,n]\),后者则可以利用整除分块加速\(O(\sqrt n)\)单点求值。
5. \(id_k(n)\)有\(O(n)\)欧拉筛预处理，\(O(1)\)单次询问的算法，也有Lagrange插值\(O(k\log^2 k)\)预处理，\(O(k)\)单次询问的单点求值法。要根据实际需要(值域，询问次数等等)来分析用哪一种比较好。
这种可以利用特殊方法加速点值求解的积性函数其实都要注意这一点。
Part 2. Möbius transformation
根据网上搜集的一些资料，我更倾向于用集合论和偏序集(poset)的语言来描述莫比乌斯变换。
1. Zeta 变换
对于定义在偏序集\((P,\leq)\)上的函数\(f : P \rightarrow \mathbb{C}\) , \(\mathcal{F}(P)\)是定义在\(P\)上的全体函数的集合.
Zeta变换 \(\zeta : \mathcal{F}(P) \rightarrow
\mathcal{F}(P)\) 定义为：
\[(\zeta f)(x) = \sum_{y \leq
x}f(y)\]
或者使用Zeta函数表述
\[(\zeta f)(x) = \sum_{y \leq
x}\zeta(y,x)f(y)\]
其中Zeta函数为：
\[\begin{align*}
\zeta(y,x)=
\begin{cases}
1&y \leq x\\
0& otherwise\\
\end{cases}
\end{align*}\] (需要注意的是偏序集如果不是全序集，\(x,y\)之间不一定有偏序关系，所以取值为\(0\)的情况是others)
2. Möbius 变换
我们定义对偏序集\((P,\leq)\)上的函数\(f : P \rightarrow
\mathbb{C}\)，Zeta变换的逆变换为莫比乌斯变换 \(\mu : \mathcal{F}(P) \rightarrow
\mathcal{F}(P)\)。
有：
\[(\mu f)(x) = \sum_{y \leq x}\mu(y,x)
f(x)\] 其中\(\mu(y,x)\)是对于偏序集上的莫比乌斯函数，这是一个二元函数，具体取值遵循以下的规律：
\[\sum_{y \leq z \leq x} \mu(y,z)\zeta(z,x) =
\delta(y,x)\] 其中\(\delta(y,x)\)是克罗内克函数
\[\begin{align*}
\delta(x,y)=
\begin{cases}
1&x = y\\
0&x\neq y\\
\end{cases}
\end{align*}\]
或者使用递归定义：
\[\mu(x,x) = 1 \\
\mu(y,x) = -\sum_{y\leq z < x}\mu(y,z)\]
作为Zeta变换的逆变换，莫比乌斯变换有以下性质：
\(\zeta\mu = \mu\zeta =
\operatorname{id}\)
3. 一些常见偏序集上的Zeta & Möbius 变换
a. 数论，整除偏序 \((Z^+,|)\)
这里的Zeta变换对应与 \(I\)
进行Dirichlet卷积，而Möbius变换则对应与\(\mu\)进行Dirichlet卷积，即数论函数的莫比乌斯反演.
\(\mu(y,x)\)函数的取值:
\[\mu(d, n) = \mu(\frac{n}{d})\]
右侧为数论中的莫比乌斯函数。
如果我们想求解\([1,n]\)上zeta变换之后的函数，一个朴素的办法是对于每个数枚举他的倍数计入贡献，这个时间复杂度是\(O(n\log n)\)的。
然而，我们可以加速这个过程。
把每个不同的质因子看作单独的一维，实际上这就是在做一个高维前缀和。于是我们可以依次枚举每个质数，对每个质数枚举\([2,\left\lfloor\frac{n}{p}\right\rfloor]\)做前缀和。
由于我们只枚举了质数位置的倍数，类似于埃氏筛法。我们可以得知这种做法的时间复杂度为\(O(n\log\log n)\)。
这个操作一般成为Dirichlet前缀和。
当然，在有限域\([1,n]\)上的整除关系上，我们可以对偶关系的Zeta变换，对应为Dirichlet后缀和，稍加变换枚举顺序即可。
实际上，应该也可以枚举质数进行高维差分，实现\(O(n\log\log n)\)
求解莫反后的函数,这也就是快速莫比乌斯变换(FMT)在整除偏序上的运用。但是实际上由于我们基本上是对一个积性函数进行莫反，得到的函数仍然是积性函数，是可以线性筛出来的，不必这样加速，所以这种情况几乎不会遇到。
b.幂集，集合包含关系偏序 \((\mathcal{P}(S),\subseteq)\)
这里的 Zeta变换对应高维前缀和， 而Möbius变换则对应高维差分。
Zeta变换的实现实际上就是我们所说的sosdp(逐维求前缀和),Möbius变换则是应该逐维差分的过程。
有时候，我们可能要将包含关系逆过来，求解对偶关系上的zeta变换，那么就是把高维前缀和变成高维后缀和。
这一对变换在算法竞赛中一般被称为快速莫比乌斯变换(FWT)，用于解决一些位运算卷积的问题。
实际上,这里的\(\mu\)函数取值是有规律可循的。有：
\[\mu(T,S) = (-1)^{|S|-|T|}\]
证明：
使用强数学归纳法。
\(n = |S| - |T| =
0\)时由定义显然成立。
假设 \(|S| - |T| = k \leq n -
1\)时成立
\(|S| - |T| = n > 0\)时，
\[\begin{align*}
\mu(T,S) &= -\sum_{T\subseteq X \subsetneq S}\mu(T,X) \\
&= -\sum_{T\subseteq X \subsetneq S} (-1)^{|X| -
|T|} &归纳假设\\
&= -\sum_{0 \leq k\leq n-1} \binom{n}{k}
(-1)^k &枚举k = |X| - |T|\\
&= (-1)^n - \sum_{0 \leq k\leq n}\binom{n}{k} (-1)^k
\quad &后半部分为0\\
&= (-1)^n\\
&= (-1)^{|S|-|T|}
\end{align*}\] 归纳成立。
于是
\[f(S) = \sum_{T \subseteq S}
(-1)^{|S|-|T|}(\zeta f)(T)\] 这也正是集合上容斥定理的内容。
此外，如果我们定义odd-negation变换\(\sigma\)：
\[(\sigma f)(X) =
(-1)^{|X|}f(X)\]
那么有：
1. \(\sigma\sigma =
\operatorname{id}\)
2. \(\mu = \sigma\zeta\sigma\)
3. \(\zeta = \sigma\mu\sigma\)
也就是说Möbius变换我们也可以通过odd-negation变换和Zeta变换来实现。
c.全序集 \((Z^+,\leq)\)
这里的zeta变换就是求前缀和了，而Möbius变换就是做差分。
有:
\[\begin{align*}
\mu(y,x)=
\left\{
\begin{array}{ll}
1&y=x\\
-1&y = x - 1\\
0& otherwise\\
\end{array}
\right.
\end{align*}\]
4.更高视角的Möbius变换
对偏序集\((P,\leq)\)，定义关联代数\(I(P)\)
\[I(P) = \mathcal{F}(P \times P) = \{
f：P\times P \rightarrow \mathbb{C} \mid f(x,y) = 0 ,\forall(x,y),x\nleq
y\}\]
定义\(I(P)\)上的卷积运算\(*\)
\[(f*g)(x,y) = \sum_{x\leq z\leq
y}f(x,z)g(z,y)\]
显然卷积运算满足结合律，存在单位元 \(\delta\) (克罗内克函数)。 于是 \((I(P)，*)\)构成一个幺半群。
如果一个函数 \(f\) 满足\(f(x,x) \neq 0 ,\forall x \in P\)，那么
\(f\) 存在逆元 \(g\)
递归定义：
\[\begin{align*}
g(x,y)=
\left\{
\begin{array}{ll}
\frac{1}{f(y,y)}&x=y\\
-\frac{1}{f(y,y)} \sum_{x\leq z< y } g(x,z)f(z,y) &x < y\\
0& otherwise\\
\end{array}
\right.
\end{align*}\] 于是 \(g*f =
\delta\),而幺半群中左逆元即为逆元。
对 \(\zeta\) 函数，它的逆即为 \(\mu\)。
我们将\(\mathrm{Z}\)变换，\(\mathrm{M}\)变换(大写以示区分)看作定义在\(\mathcal{F}(P)\)上的线性算子(根据前面的推论，它满足线性空间的8条性质)，那么我们可以得出变换和关系代数的联系
：
对 \(f\in \mathcal{F}(P)\), \[\mathrm{Z} (f) = \zeta * f, \quad \mathrm{M} (f)
= \mu * f\]
而变换的复合对应卷积
\[(\mathrm{M}\mathrm{Z}) (f) =
\operatorname{id} (f) = \delta * f = \mu * \zeta * f\]
下面是以整除关系为例展示一下上面的结论：
整除关系\(\zeta\)函数矩阵：
\[\begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1\\ 0 & 1 & 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}\] 逆矩阵(\(\mu\)函数矩阵)：
\[\begin{bmatrix} 1 & -1 & -1 & 0 & -1 & 1\\ 0 & 1 & 0 & -1 & 0 & -1\\ 0 & 0 & 1 & 0 & 0 & -1\\ 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}\]
可以观察到逆矩阵的第一行正好是\(\mu\)的前6项，这和我们的推论是吻合的。
Part 3.Inclusion-Exclusion on Posets
前面我们已经通过莫比乌斯变换很自然地导出了集合上的容斥定理: \[f(S) = \sum_{T \subseteq S} (-1)^{|S|-|T|}(\zeta
f)(T)\] 如这里 \(f\)
可以作为某个集合的上的计数函数，\(g = \zeta
f\)则是所有子集的计数和。
有限集下也有补集形式：
\[\zeta f(S) = \sum_{S \subseteq T}
(-1)^{|S|-|T|}(f)(T)\]
然而，我们知道容斥定理并非只有这一种形式，比如说还有最经典的集合交-集合并容斥，以及像Min-Max容斥和k-th容斥，二项式反演这种特殊的容斥，这些容斥可否也通过莫比乌斯变换的理论得出呢?
答案是肯定的，只需要我们选择合适的偏序集和合适的函数就可以推导出来。
交集-并集容斥
设\(S\)是全集，\(A_1,A_2,\dots,A_n \subseteq S\).
对任意子集\(I \subseteq \{1,2,\dots,n\}
=[n]\),
定义： 子集交函数\(g\),
\[g(I) = \left|\bigcap\limits_{i \in
I}A_i\right|\] 特别地，\(g(\emptyset) =
|S|\)
精确计数函数\(f\),\(f(I)\)表示恰好属于所有\(A_i，i\in I\)且不属于其他任何\(A_j,j\notin I\)的元素个数。
特别地，\(f(\emptyset) = |S| -
\left|\bigcup\limits_{i \in I}A_i\right|\)
于是有\(\mathbf{Z}_n^+\)上的Zeta变换：
\[g(I) = \sum_{J \supseteq
I}f(J)\]
(注意2点，一个是这里是在枚举超集，一个是这里\(f\)函数的定义，建议画图来理解一下实际含义。感觉上相当于先取所属集合的交集，再减去所有其他集合，可以用涂色的方式理解。而且如果我们用Venn图表示，每个\(f(I)\)都表示Venn图中极小的一块。)
于是可以得到莫比乌斯反演公式：
\[f(I) = \sum_{J\supseteq
I}(-1)^{|J|-|I|}g(J)\]
代入\(I = \emptyset\)有：
\[\begin{align*}
\left|\bigcup\limits_{i \in [n]}A_i\right|
&= |S| - \sum_{J \supseteq \emptyset}(-1)^{|J|}g(J)\\
&= \sum_{J \subseteq [n],J \neq \emptyset} (-1)^{|J| + 1}g(J)\\
&= \sum_{k = 1}^n (-1)^{k+1}\sum_{|J| = k}g(J)\\
&= \sum_{k = 1}^n (-1)^{k+1}\sum_{|J| =
k}\left|\bigcap\limits_{i \in J}A_i\right|
\end{align*}\] 由此,我们通过构造\((\mathcal{P}([n]),\supseteq)\)这一偏序集及子集交函数，精确计数函数两个函数，从莫比乌斯反演推导出了并集-交集容斥。
对于其他的容斥，也可以尝试构造合适的偏序集和函数得出。
Part 4.部分例题
这部分先鸽了之后再补
