最近有点彷徨……正如钱老师所说，自己有些内耗

可能还是看到自己刚刚学的东西，很多曾经的同学两三年前就会了。。。感到有点失落。

而且自己的数据结构越来越不行了。今年NOIPT4什么都没想出来。还不知道怎样补......因为不知道问题所在

不如先放首光辉岁月听听吧

将 $F(n)=\sum\limits_{i}A_{n,i}G(i)$ 转换成 $G(n)=\sum\limits_{i}B_{n,i}F(i)$ 的形式，叫做反演。

首先，我们可以发现 $F=A*G$ 和 $G=B*F$

于是 $F=A*B*F$ 即 $A*B=E$ ($E$ 表示单位矩阵)，也就是说 $A=B^{-1}$

而且由于 $(AB)^T=B^TA^T$，我们将矩阵转置一下仍然是互逆的（不会上述性质的童鞋，只需要记住，把一对互逆的矩阵行列倒过来，俩人仍然互逆）

对于矩阵里有 $(-1)^i$ 的，可以把它转移到另外一个矩阵里。可以得到无 $-1$ 因子的矩阵和另一个矩阵互逆的结论。

$1.$ 令 $A=\begin{bmatrix}(-1)^0C_0^0&0&0&\cdots&0\\(-1)^0C_1^0&(-1)^1C_1^1&0&\cdots&0\\(-1)^0C_2^0&(-1)^1C_2^1&(-1)^2C_2^2&\cdots&0\\\vdots&\vdots&\vdots&\ddots&\vdots&\\(-1)^0C_n^0&(-1)^1C_n^1&(-1)^2C_n^2&\cdots&(-1)^nC_n^n\end{bmatrix}$，则 $A^2=E$ (其中 $E$ 为单位矩阵)

这里 $A_{n,i}=(-1)^iC_n^i=(-1)^i\dbinom{n}{i}$

证明：令 $C=A^2$，则 $C_{i,j}=\sum\limits_k{A_{i,k}B_{k,j}}=\sum\limits_k{(-1)^{k-j}\dbinom{i}{k}\dbinom{k}{j}}=\dbinom{i}{j}\sum\limits_k(-1)^{k-j}\dbinom{i-j}{k}=\dbinom{i}{j}[i=j]=[i=j]$

因此 $C=E$，证毕

如果有 $f*A=g$，那么有 $g*A=f$

这里用到了恒等式 $\dbinom{i}{k}\dbinom{k}{j}=\dbinom{i}{j}\dbinom{i-j}{k-j}$，从组合意义和代数角度都较为好证

还用到了恒等式 $\sum\limits_k(-1)^k{\dbinom{n}{k}}=[n=0]$，用的是二项式定理里面，$(1-1)^n$ 的展开式。

我们发现，如果矩阵 $A$ 满足 $A_{n,i}=\dbinom{n}{i}$，矩阵 $B$ 满足 $B_{n,i}=(-1)^{n-i}\dbinom{n}{i}$，那么两者互逆。

也就是如果有 $f*A=g$，那么有 $g*B=f$

还可以用转置推出另外两个反演式子，此处省略。

先咕了。