神奇反演魔法学习笔记

反演原理

$$f_{n}=\sum\limits_{i=0}^{n}a_{n, i}\cdot g_i$$

考虑何时存在$$\sum \limits_{i=0}^{n}b_{n, i}\cdot f_i=g_n$$
将$f_{n}=\sum\limits_{i=0}^{n}a_{n, i}\cdot g_i$直接带入得
$$\begin{split}\sum \limits_{i=0}^{n}b_{n, i}\cdot f_i
&=\sum \limits_{i=0}^n b_{n, i}\cdot \sum \limits_{j=0}^{i}a_{i, j}\cdot g_j\\
&=\sum \limits_{i=0}^{n}g_i\cdot \sum \limits_{j=i}^{n}a_{j, i}\cdot b_{n, j}
\end{split}$$
所以只要$\sum \limits_{j=i}^na_{j, i}\cdot b_{n, j}=[i==n]$,就满足原式了

不过讲真我感觉这个除了证明式子成立以外根本没有什么用…

此外反演还可以用矩阵的形式表示

$$\left[ \begin{matrix}
f_{0}\\
f_{1}\\
\dots \\
f_{n}
\end{matrix}\right]=
\left[ \begin{matrix}
a_{0, 0} & a_{0, 1} & \dots & a_{0, n}\\
a_{1, 0} & a_{1, 1} & \dots & a_{1, n}\\
&\dots \\
a_{n, 0} & a_{n, 1} & \dots & a_{n, n}\\
\end{matrix}\right]\times
\left[ \begin{matrix}
g_0\\
g_1\\
\dots\\
g_n
\end{matrix}\right] $$

设$F=A\times G$,$G=B\times F$,则显然有$B=A^{-1}$

传送门

单位根反演

$$[k|n]=\frac{1}{k}\cdot \sum \limits_{i=0}^{k-1}\omega_{k}^{in}$$

斯特林数反演

$$f_n=\sum \limits_{i=0}^n{n\brace i}\cdot g_i\Leftrightarrow g_n=\sum \limits_{i=0}^n{n\brack i}\cdot f_i$$

发表评论

电子邮件地址不会被公开。 必填项已用*标注