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

多项式复合

多项式复合形如 \(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}\)。

拉格朗日(Lagrange)反演

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

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\)。

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

\[ [x^n]F(x)=\frac{1}{n}[x^{-1}](\frac{1}{G(x)})^n \] 显然，存在复合逆的多项式必然没有常数项：

所以上式写成更阳间的样子就是 \(\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)\) ，求其复合逆：

带入拉格朗日反演的式子：

\[ F(x)=\sum \frac{1}{i}[x^{i-1}](\frac{x}{G(x)})^i x^i \] 求这个式子的核心是 分块 + 暴力。

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

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