基础知识

前缀和

一维情况

设有序列 ${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 \le n}\sum_{j \le 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 \le n}a_{i,m}$,然后对第二维在 ${b_{n,m}}$ 的基础上求前缀和,得到 ${s_{n,m}}$,即 $s_{n,m}=\sum_{j \le 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 \le x_1}\sum_{i_2 \le x_2} \cdots \sum_{i_k \le 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 \le k_i$

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

$$
g _ {(k _ 1,k _ 2,\cdots,k_{\infty})}=\sum_{k’ _ 1 \le k _ 1}\sum_{k_2’ \le k_2} \cdots \sum _ {k’ _ {\infty} \le 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)}$

设 $n=\prod_{i=1}^{\infty}p_i^{k_i}$,现在要求出 $\mu(n)$

考虑到 $0 \le k_i \le 1$,因此 $n$ 应无大于 $1$ 的完全平方因子,且如果 $n$ 能写做 $k$ 个不同的素数的乘积的话,则 $\mu(n)=(-1)^{k}$

$\zeta \times \mu=\delta$

定义 $\delta(n)=[n=1]$,也就是单位函数,换而言之 $f \times \delta=f$

考虑到 $\zeta$ 表示前缀和,$\mu$ 表示差分,那么 $f$ 依次作用上这两个函数,就相当于没有进行作用

即 $f \times \zeta \times \mu=f \times (\zeta \times \mu)=f \times \delta=f$

后话

一个有趣的题:loj #6627. 等比数列三角形