拉格朗日反演

用于在\(O(n\log n)\)的时间内求\([x^n]G(x)\)，其中\(G(x)\)满足\(F(G(x))=x\)，\(F(x)\)已知，且\([x^0]F(x)=[x^0]G(x)=0,[x^1]F(x) \neq 0,[x^1]G(x) \neq 0\)。

这里有个小结论（我不会证）：若\(F(G(x))=x\)，则\(G(F(x))=x\)。

令\(g_i=[x^i]G(x)\)，代入\(G(F(x))=x\)得到

\[\sum_{i=1}^{\infin} g_i\times F^i(x) = x \]

两边求导得

\[\sum_{i=1}^{\infin} g_i\times i \times F^{i-1}(x) \times F'(x) = 1 \]

考虑两边除以\(F^n(x)\)，并取\([x^{-1}]\)的系数：

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

当\(i\neq n\)时，\(F^{i-n-1}(x)F'(x)\)等价于\(\frac{1}{i-n}(F^{i-n})'(x)\)，而任何函数求导后\(-1\)次项均为0，所以上式可以转化为：

\[[x^{-1}] g_n\times n \times \frac{F'(x)}{F(x)}=[x^{-1}]\frac{1}{F^n(x)} \]

对于\(\frac{F'(x)}{F(x)}\)，有：

\[\begin{aligned} \frac{F'(x)}{F(x)} &= \frac{a_1+2a_2x+3a_3x^2+...}{a_1x+a_2x^2+a_3x^3...}\\ &= \frac{a_1+2a_2x+3a_3x^2+...}{a_1x}\times\frac{1}{1+\frac{a_2}{a_1}x+\frac{a_3}{a_1}x^2+...} \end{aligned} \]

根据多项式求逆，后面那个多项式的常数项为\(1\)，而前面那个多项式的\(-1\)次项的系数为1，于是\([x^{-1}]\frac{F'(x)}{F(x)}=1\)

代入得

\[g_n=[x^{-1}]\frac{1}{nF^n(x)} \]

再令\(F'(x)=F(x)/x\)，原式就有：

\[g_n=[x^{n-1}]\frac{x^n}{nF^n(x)}=[x^{n-1}]\frac{1}{nF'^n(x)} \]

于是就可以\(n \log n\)求第\(n\)次项了。