「算法学习」拉格朗日反演

不会抽代，我很抱歉

拉格朗日反演

设有两个多项式 $F(x)$ 和 $G(x)$ ，两个多项式都是常数项为 0 且 1 次项不为 0，如果满足 $G(F(x)) = x$，则称 $F(x)$ 与 $G(x)$ 互为复合逆，有

$$\begin{split} &[x^n]F(x) = \frac{1}{n}[x^{-1}]\left(\frac{1}{G(x)}\right)^n\\ &[x^n]H(F(x)) = \frac{1}{n}[x^{-1}]\left(H'(x)\left(\frac{1}{G(x)}\right)^n\right) \end{split}$$

该定理可以扩展到二维的形式。

证明

第一次看到这个东西，你会发现这个东西为什么会有一个 $x^{-1}$ ，其实这个东西无伤大雅，你可以把多项式想象成一个负数次也有无数项的东西，至于他们的系数是什么我们不关心（因为我也不知道，你就当他是虚空造物就好了），这样是可行的，具体的证明要用到抽代的分数环理论，我也不懂，毛估估一下应该很对。

然后直接推这个式子

对于 $G(F(x)) = x$ ，我们展开这个式子

$$\begin{split} \sum_{i}^{\infin}a_iF^i(x) = x\\ \end{split}$$

两边同时求导，得

$$\sum_{i = 1}^{\infin} ia_iF^{i - 1}(x)F'(x) = 1$$

这里的 $F’(x)$ 代表的是 F(x) 的系数

我们两边同时除以 $F^n(x)$ ，同时取 $x^{-1}$ 的系数

$$[x^{-1}]\sum_{i=1}^{\infin}ia_iF^{i - n - 1}(x)F'(x) = [x^{-1}] \frac{1}{F^n(x)}$$

对于左边，我们发现当 $i \ne n$ 时，$\frac{1}{i- n}(F^{i-n})’(x)$ ，由于任何一个多项式求导之后 -1 次都是0，所以这一部分不用考虑，只要管 $i = n$ 的时候就行了

当 $i = n$ 的时候，这个式子有

$$[x^{-1}]F^{-1}(x)F'(x) = 1$$

带入原式，有

$$\begin{split} &na_n = [x^{-1}]\frac{1}{F^n}(x)\\ &a_n = [x^{-1}]\frac1n\left(\frac{1}{F(x)}\right)^n\\ \end{split}$$

当然这个东西不能直接算就是了，我们考虑把式子右边乘上一个 $x^n$ ，那么 $x^{-1}$ 就变成了 $x^{n - 1}$ ，这个式子就可以通过一些比较好的方法计算了

$$\begin{split} &a_n = [x^{-1}]\frac1n\left(\frac{1}{F(x)}\right)^n\\ &a_n = [x^{n-1}]\frac1n\left(\frac{x}{F(x)}\right)^n\\ &a_n = [x^{n-1}]\frac1n\left(\frac{1}{\frac{F(x)}{x}}\right)^n\\ \end{split}$$

一般给定的 F(x) 会有常数项为 0，一次项不为 0 的限制，我们就可以求逆之后快速幂了。