拉格朗日反演
用于在(O(nlog 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) eq 0,[x^1]G(x) eq 0)。
这里有个小结论（我不会证）：若(F(G(x))=x)，则(G(F(x))=x)。
令(g_i=[x^i]G(x))，代入(G(F(x))=x)得到
[sum_{i=1}^{inf} g_i imes F^i(x) = x
]
两边求导得
[sum_{i=1}^{inf} g_i imes i imes F^{i-1}(x) imes F'(x) = 1
]
考虑两边除以(F^n(x))，并取([x^{-1}])的系数：
[[x^{-1}]sum_{i=1}^{inf} g_i imes i imes F^{i-n-1}(x) imes F'(x) = [x^{-1}]frac{1}{F^n(x)}
]
当(i eq n)时，(F^{i-n-1}(x)F'(x))等价于(frac{1}{i-n}(F^{i-n})'(x))，而任何函数求导后(-1)次项均为0，所以上式可以转化为：
[[x^{-1}] g_n imes n imes frac{F'(x)}{F(x)}=[x^{-1}]frac{1}{F^n(x)}
]
对于(frac{F'(x)}{F(x)})，有：
[egin{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} imesfrac{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)次项了。
扩展拉格朗日反演
用于在(O(nlog n))的时间内求([x^n]G(x))，其中(G(x))满足(F(G(x))=H(x))，(H(x))已知。
那么：
[g_n=[x^{n-1}]frac{H'(x)}{nF'^n(x)}
]
证明与上面类似。