多项式复合+拉格朗日反演

多项式复合

多项式复合形如$F(G(x))$，即复合函数，较为数学的形式可以写作$u=F(v),v=G(x)$

在符号上，记做$F\circ G=F(G(x))$

稍微展开一下就是$\begin{aligned} F(G(x))=\sum_i [x^i]F(x)\cdot G^i(x)\end{aligned}$

$\$

数学上，拉格朗日反演揭示了幂函数的反函数的形式

OI上，拉格朗日反演是复合逆/反函数的反演

对于多项式$F(x),G(x)$，若他们的复合满足$F(G(x))=x$，则$F(x)$与$G(x)$互为复合逆(若在非模意义下，$y=F(x),y=G(x)$的图像关于直线$y=x$对称，即反函数)，此时也有$G(F(x))=x$

拉格朗日反演用于求解复合逆的一项的值:

$\begin{aligned} [][x^n]F(x)=\frac{1} {n}[x^{-1}](\frac{1} {G(x)})^n\end{aligned} $

显然，存在复合逆的多项式必然没有常数项

所以上式写成更阳间的样子就是$\begin{aligned}[] [x^n]F(x)=\frac{1} {n}[x^{n-1}](\frac{x} {G(x)})^n\end{aligned} $

由于证明太~~，咕了

另外还有扩展拉格朗日反演

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

对于给定的$F(x)$，求其复合逆

带入拉格朗日反演的式子

$\begin{aligned} F(x)=\sum \frac{1} {i}[x^{i-1}](\frac{x} {G(x)})^i x^i\end{aligned} $

求这个式子的核心是分块+暴力

$i=a\cdot S+b$，求出$(\frac{x} {G(x)})^{Sa},(\frac{x} {G(x)})^b$，然后直接对于每个位置把两个式子暴力合并即可

两部分复杂度总和为$O(n\sqrt n\log n+n^2)$