反演

参考文献

我所理解的反演

形如
$$f(n) = \sum_i g(i)$$

对于$f(n)$易算的情况下,想要通过$f(n)$得到$g(n)$。即计算出$g(n)$关于$f(n)$的表达式。

这个过程称为反演。

其实一个比较显然的做法就是通过高斯消元直接求解$O(n^3)$,有的时候因为矩阵是个上(下)三角矩阵,因此可以简化复杂度到$O(n^2)$。

但对于数据量比较大的情况,只能手推出反演式再进行计算。

普通反演

$$f(n) = \sum_{i=0}^{n}x_ig(i)$$

写成矩阵形式

$$
\left(
\begin{matrix}
x_0 & 0 & 0 \\
x_0 & x_1 & 0 \\
x_0 & x_1 & x_2
\end{matrix}
\right) \times
\left(
\begin{matrix}
g(0) \\
g(1) \\
g(2)
\end{matrix}
\right)
= \left(
\begin{matrix}
f(0) \\
f(1) \\
f(2)
\end{matrix}
\right)
$$

直接高斯消元即可(因为已经是下三角矩阵,因此可以简化为$O(n^2)$

二项式反演

$$f(n) = \sum_{k=0}^n \tbinom{n}{k} g(k)$$

$$
g(n) = \sum_{k=0}^{n}(-1)^{n-k}\tbinom{n}{k}f(k)
$$

证明如下:

$$g(n) = \sum_{m=0}^n [n-m=0] \tbinom{n}{m} g(m) \tag1 $$

$$\sum_{k=0}^n (-1)^k \tbinom{n}{k} = [n=0] \tag2$$

$[n=0]$表示在只有在$n$为$0$时取值是$1$,否则取值为$0$。

将$(2)$代入$(1)$中

$$
g(n) = \sum_{m=0}^n \sum_{k=0}^{n-m}(-1)^k \tbinom{n-m}{k} \tbinom{n}{m} g(m)
$$

$\tbinom{n-m}{k} \tbinom{n}{m}$表示从一个大小为$n$的集合拿出两个大小分别为$m$和$k$的子集,它和$\tbinom{n-k}{m} \tbinom{n}{k}$是等价的。

$$
g(n) = \sum_{m=0}^n \sum_{k=0}^{n-m}(-1)^k \tbinom{n}{k} \tbinom{n-k}{m} g(m)
$$

交换求和符号

$$
g(n) = \sum_{k=0}^n(-1)^k\tbinom{n}{k}\sum_{m=0}^{n-k}g(m)\tbinom{n-k}{m}
$$

最右边的部分实际上是$f(n-k)$

$$
g(n) = \sum_{k=0}^n(-1)^k\tbinom{n}{k}f(n-k)
$$

变换下标

$$
g(n) = \sum_{k=0}^{n}(-1)^{n-k}\tbinom{n}{k}f(k)
$$

莫比乌斯反演

$$f(n) = \sum_{d|n} g(d)$$

$$g(n) = \sum_{d|n} \mu(\frac{n}{d})f(d)$$

证明如下:

$$g(n) = \sum_{m|n}[\frac{n}{m}=1]g(m) \tag3$$

$$\sum_{d|n}\mu(d) = [n=1] \tag4$$

将$(4)$ 代入$(3)$中

$$g(n) = \sum_{m|n}\sum_{d|\frac{n}{m}}\mu(d)g(m)$$

交换求和符号

$$g(n) = \sum_{d|n}\mu(d)\sum_{m|\frac{n}{d}}g(m)$$

最右边的部分是$f(\frac{n}{d})$

$$g(n) = \sum_{d|n}\mu(d)f(\frac{n}{d})$$

变换下标

$$g(n) = \sum_{d|n} \mu(\frac{n}{d})f(d)$$

莫比乌斯函数

莫比乌斯函数

$$
\mu (n) = \begin{cases}
1 \quad (n=0)\\
(-1)^k \quad(n=p_1p_2…p_k)\\
0 \quad (others)
\end{cases}
$$

有性质

$$\sum_{d|n}\mu(d) = [n=1]$$

子集反演

咕咕咕