前缀和
一维情况
设有序列 ${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. 等比数列三角形
