反演的本质

对于可逆下三角矩阵$A$（可以归纳证明$A^{-1}$也是下三角矩阵）,有$f=Ag$,那么$g=A^{-1}f$

即:

$$f_i=\sum_{j=0}^ia_{ij}g_j\Rightarrow g_i=\sum_{j=0}^ib_{ij}f_j$$

其中:
$$\sum_{k=0}^na_{ik}b_{kj}=[i==j]$$

几类特殊的反演

前缀和及差分

如果$f$是$g$的前缀和,那么:

$$f_i=\sum_{j=0}^ig_j$$

$g$即为$f$的差分:

$$g_i=f_i-f_{i-1}[i > 0]$$

那么$A$即为:

$$
A = \begin{bmatrix}
1 \
1 & 1 \
\vdots & \vdots & \ddots \
1 & 1 & \cdots & 1
\end{bmatrix}
$$

$A$的逆矩阵:

$$
A^{-1}=\begin{bmatrix}
1 \
-1 & 1 \
& -1 & \ddots \
& & \ddots & 1 \
& & & -1 & 1
\end{bmatrix}
$$

高阶前缀和及差分

很容易想到,$k$阶前缀和及差分的矩阵即为$1$阶的矩阵的$k$次:

$$
A=\begin{bmatrix}
1 \
1 & 1 \
\vdots & \vdots & \ddots \
1 & 1 & \cdots & 1
\end{bmatrix}^k
$$

其中:

$$
a_{ij}=\binom{k-1+i-j}{i-j}
$$

这个其实非常容易感性理解吧。。画个图，然后类似于算路径数

那么$A^{-1}$呢

$$
A^{-1}=\begin{bmatrix}
1 \
-1 & 1 \
& -1 & \ddots \
& & \ddots & 1 \
& & & -1 & 1
\end{bmatrix}^k
$$

其中:

$$
(a^{-1})_{ij}=(-1)^{i-j}\binom{k}{i-j}=\binom{-k-1+i-j}{i-j}
$$

和上面那个十分得神似。

二项式反演

二项式反演有两种形式

$$
f_i=\sum_{j=0}^i\binom{i}{j}g_j\Rightarrow g_i=\sum_{j=0}^i(-1)^{j-i}\binom{i}{j}f_j
\tag{1}
$$

$$
f_i=\sum_{j=0}^{i}(-1)^j\binom{i}{j}g_j\Rightarrow g_i=\sum_{j=0}^i(-1)^j\binom{i}{j}f_j
\tag{2}
$$