若两个多项式 $F(x),G(x)$ ,都满足常数项为 $0$ , $1$ 次项不为 $0$ ,且两者互为复合逆,即, $G(F(x))=x$ ,则有
$$
[x^n] F(x)=\frac 1 n [x^{-1}] \frac{1}{G^n(x)} \\
[x^n] F(x)=\frac 1 n [x^{n-1}] (\frac{x}{G(x)})^n
$$
两个式子是等价的,在计算中常用第二个式子.
得到 $G(x)$ 后,用多项式求逆 + 多项式快速幂,可以在 $O(n\log n)$ 的时间复杂度内求出 $F(x)$ .
拓展拉格朗日反演:
$$
[x^n]H(F(x))=\frac 1 n[x^{n-1}]H’(x)(\frac x {G(x)})^n
$$
证明:
设 $F(x)$ 的各项系数为 $a_i$ ,即 $F(x)=\sum_{i} a_ix^i$ .
由于 $F(x),G(x)$ 互为复合逆,代入 $F(G(x))=x$ ,得到
$$
\sum_{i} a_i G^i(x) =x
$$
两边同时对 $x$ 求导,得到
$$
\sum_{i} a_i\cdot i\cdot G^{i-1}(x)\cdot G’(x)=1
$$
两边同时除以 $G^n(x)$ ,得到
$$
\sum_{i} a_i\cdot i\cdot G^{i-n-1}(x)\cdot G’(x)=\frac{1}{G^n(x)}
$$
取 $x$ 的 $-1$ 次项,
$$
[x^{-1}] \sum_{i} a_i\cdot i\cdot G^{i-n-1}(x)\cdot G’(x)=[x^{-1}]\frac{1}{G^n(x)}
$$
对于那些 $i\neq n$ 的项,注意到 $G^{i-n-1}(x)\cdot G’(x)=\frac{1}{i-n} (G^{i-n})’(x)$ ,是个多项式.
而任何一个多项式求导后 $x^{-1}$ 系数都为 $0$ ,所以这些项对 $x^{-1}$ 的系数没有贡献.
只需要考虑 $i=n$ 的那一项,即
$$
[x^{-1}] a_n\cdot n\cdot G^{-1}(x)\cdot G(x)=[x^{-1}]\frac{1}{G^n(x)}
$$
当 $i=n$ 时,
$$
\begin{aligned}
G^{-1}(x)\cdot G’(x)&=\frac{a_1+2a_2x+3a_3x^2+\dots}{a_1x+a_2x^2+a_3x^3+\dots} \\
&=\frac{a_1+2a_2x+3a_3x^2+\dots}{a_1 x} \cdot \frac{1}{1+\frac{a_2}{a_1}x+\frac{a_3}{a_1}x^2+\dots}
\end{aligned}
$$
对于 $1+\frac{a_2}{a_1}x+\frac{a_3}{a_1}x^2+\dots$ 这个多项式来说,它的常数项为 $1$ ,所以一定可逆,且求逆后常数项也为 $1$ .
而对于前面那个分数,将它拆开后,只有第一项的次数为 $-1$ ,且这一项的系数为 $1$ .
于是将两者乘起来,得到 $[x^{-1}] F^{-1}(x)\cdot F’(x)=1$ .
代入 $[x^{-1}] a_n\cdot n\cdot G^{-1}(x)\cdot G’(x)=[x^{-1}]\frac{1}{G^n(x)}$ 中,就得到了 $a_n=\frac {1}{n} [x^{-1}] \frac{1}{G^n(x)}$ .
即
$$
[x^n] F(x)=\frac 1 n [x^{-1}] \frac{1}{G^n(x)}
$$
由于 $G(x)$ 的常数项为 $0$ ,而一次项不为 $0$ ,所以 $\frac {x}{G(x)}$ 是可以求的,上面的式子就可以变成
$$
[x^n] F(x)=\frac 1 n [x^{n-1}] (\frac{x}{G(x)})^n
$$