2019-07-26 12:56 已编辑清华大学数据挖掘

关注

从莫比乌斯反演到前缀和

安利本人的另一个博客：https://czyhe.me/blog/algorithm/partialsum-to-mobiusinversion/partialsum-to-mobiusinversion/

基础知识

前缀和

一维情况

设有序列 $\{a_n\}$ ，定义其前缀和为序列 $\{s_n\}$ ，满足 $s_n=\sum_{i=1}^{n}a_i$

前缀和的定义有一个好处，就是可以快速提取 $a$ 的区间和（前提是存在加法逆元），即 $\sum_{i=l}^{r}a_i=s_r-s_{l-1}$

~~连续情况下为积分，此处为离散积分~~

二维情况

给定 $\{a_{n.m}\}$ ，求 $\{s_{n,m}\}$ ，满足 $s_{n,m}=\sum_{i \leq n}\sum_{j \leq m}a_{i,j}$

考虑容斥，有 $s_{n,m}=s_{n-1,m}+s_{n,m-1}-s_{n-1,m-1}+a_{n,m}$

还有另一种做法：先对第一维求前缀和 $\{b_{n,m}\}$ ，满足 $b_{n,m}=\sum_{i \leq n}a_{i,m}$ ，然后对第二维在 $\{b_{n,m}\}$ 的基础上求前缀和，得到 $\{s_{n,m}\}$ ，即 $s_{n,m}=\sum_{j \leq m}b_{n,j}$

实际上是先求出了一堆列的前缀和，然后再对行求前缀和就得到了矩形的前缀和

高维情况

给定 $\{a_{x_1,x_2,\cdots,x_k}\}$ ，求 $\{s_{x_1,x_2,\cdots,x_k}\}$ ，满足 $s_{x_1,x_2,\cdots,x_k}=\sum_{i_1 \leq x_1}\sum_{i_2 \leq x_2} \cdots \sum_{i_k \leq x_k}a_{i_1,i_2,\cdots,i_k}$

先考虑容斥，有：

$s _ {x _ 1,x _ 2,\cdots,x _ k}=a _ {x _ 1,x _ 2,\cdots,x _ k}+\sum_{i _ 1=0}^{1}\sum_{i _ 2=0}^{1}\cdots \sum_{i _ k=0}^{1} \left[\sum _ {j=1}^{k}i _ j > 0 \right](-1)^{\left(1+\sum _ {j=1}^{k}i _ j\right)} s _ {x _ 1-i _ 1,x _ 2-i _ 2,\cdots,x _ k-i _ k}$

对于另一种做法，就相当于对于每一维都依次求一遍前缀和，最后的到的结果是和容斥得到的结果相同的

差分

一维情况

差分是前缀和的逆运算，即如果知道 $\{s_n\}$ ，现在要还原 $\{a_n\}$ ，则有 $a_n=s_{n}-s_{n-1}$

~~连续情况下为微分，此处为离散微分~~

二维情况

实际上把前缀和的式子中的 $a$ 挪到一旁就是差分的方式了，即：

$\begin{aligned} &s_{n,m}=s_{n-1,m}+s_{n,m-1}-s_{n-1,m-1}+a_{n,m} \\\\ \Rightarrow &a_{n,m}=s_{n,m}-s_{n-1,m}-s_{n,m-1}+s_{n-1,m-1} \end{aligned}$

另一种方法：先把仅有第一维的前缀和 $\{b_{n,m}\}$ 求出来，即 $b_{n,m}=s_{n,m}-s_{n,m-1}$

然后 $\{a_{n,m}\}$ 就可以求了，即 $a_{n,m}=b_{n,m}-b_{n-1,m}$

高维情况

容斥的做法就较为简单了

$a_{x_1,x_2,\cdots,x_k}=\sum_{i_1=0}^{1}\sum_{i_2=0}^{1}\cdots \sum_{i_k=0}^{1} (-1)^{\left(\sum_{j=1}^{k}i_j\right)} s_{x_1-i_1,x_2-i_2,\cdots,x_k-i_k}$

如果用另一种方法的话，实际上每一维都从大往小枚举后做差分即可

正整数与唯一分解定理

正整数

非 $0$ 的自然数，也就是 $1,2,3,4,5,\cdots,\infty$ 这样的，记做 $\mathbb{N^{*}}$

唯一分解定理

设 $\mathbb{P}$ 为全体素数的集合，其中 $p_i$ 表示第 $i$ 个素数，比如说 $p_1=2,p_2=3,p_3=5$ 之类的

对于任意一个正整数 $n$ ，存在唯一一种划分：

$n=\prod_{i=1}^{\infty} p_i^{k_i}$

整除与狄利克雷卷积

整除

在 $\mathbb{N^{*}}$ 上定义二元关系整除，用符号 $|$ 来表示，其定义为：

$a\|b \Leftrightarrow a,b \in \mathbb{N^{*}} \wedge \left( \exists k \in \mathbb{N^{*}}:ka=b \right)$

狄利克雷卷积

对于序列 $\{a_n\}$ 和序列 $\{b_n\}$ ，定义其狄利克雷卷积 $\{c_n\}$ 为：

$c_n=\sum_{d|n}a_db_\frac{n}{d}$

记做 $c=a \times b$

$\zeta \times \mu=\delta$

$g=f \times \zeta$

定义 $\zeta(n)=1$ ，即：

$g_n=\sum_{d|n}f_d$

换句话说就是求了一个在整除意义下的前缀和

考虑把它写的更好看一些，不妨把 $n$ 唯一分解定理展开，即：

$n=\prod_{i=1}^{\infty} p_i^{k_i}$

于是可以把 $n$ 看作高维度空间下的一个点，即 $(k_1,k_2,\cdots,k_{\infty})$

设 $d|n$ ，且 $d=\prod_{i=1}^{\infty}p_i^{k'_i}$ ，则 $d$ 应当满足 $k'_i \leq k_i$

于是可以这么来做 $g=f \times \mu$ ，即（为了好看起见就加上了个 $k_\infty$ ，实际上不能这么写）：

$g _ {(k _ 1,k _ 2,\cdots,k_{\infty})}=\sum_{k' _ 1 \leq k _ 1}\sum_{k_2' \leq k_2} \cdots \sum _ {k' _ {\infty} \leq k_{\infty}} \left[d=\prod _ {i=1}^{\infty}p_i^{k'_i}\right] f_d$

于是就可以使用高维前缀和的做法来计算 $g$ 了

$f = g \times \mu$

如果知道 $g$ ，现在要还原 $f$ ，实际上也不难操作

一个比较简单的方法就是，从小到大枚举 $n$ ，由于 $g_n=\sum_{d|n}f_d$ ，所以 $f_n=g_n-\sum_{d|n \wedge d < n}f_d$

另一个比较巧妙的方法就是求出 $\zeta$ 的逆函数，定义它为 $\mu$

考虑到高维差分的容斥做法：

$a_{x_1,x_2,\cdots,x_k}=\sum_{i_1=0}^{1}\sum_{i_2=0}^{1}\cdots \sum_{i_k=0}^{1} (-1)^{\left(\sum_{j=1}^{k}i_j\right)} s_{x_1-i_1,x_2-i_2,\cdots,x_k-i_k}$

那么 $\mu$ 就是 $(-1)^{\left(\sum_{j=1}^{k}i_j\right)}$