拉格朗日反演 (Lagrange Inversion)

复合逆

对于$F(G(x))=x (\Leftrightarrow G(F(x))=x)$，则称$F(x)$与$G(x)$互为复合逆，下文中记为$\hat F(x)$

存在复合逆的条件为$[x^0]F(x)=0,[x^1]F(x)\ne 0$

$$\$$

拉格朗日反演

对于$G(x)=\hat F(x)$得到关于$F(x)$的拉格朗日反演表达式

$\displaystyle [x^n]G(x)=\frac{1} {n}x^{-1}})^n$

由于$[x^0]F(x)=0$无法求逆，所以上式更通用的形式是

$\displaystyle [x^n]G(x)=\frac{1} {n}x^{n-1}})^n$

$$\$$

求解复合逆

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

带入拉格朗日反演的式子

$\displaystyle G(x)=\sum \frac{1} {i}x^{i-1}})^i x^i$

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

$i=a\cdot S+b,S=\sqrt n$，对于每个$a,b$卷积求出$\displaystyle (\frac{x} {F(x)})^{Sa},(\frac{x} {F(x)})^b$

然后直接对于每个位置把两个式子暴力$O(n)$合并即可

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

$$\$$

扩展拉格朗日反演

对于$G(x)=\hat F(x)$，有$\displaystyle [x^n]H(G(x))=\frac{1} {n}[x^{n-1}]H’(x) (\frac{x} {F(x)})^n$

特殊情况例如

$\displaystyle [x^n]G^k(x)=\frac{k} {n}u^{n-k}})^n=\frac{k} {n}[u^{-k}]F(u)^{-n}$

也就是$\displaystyle n[x^n]G^k(x)=k[x^{-k}]F(x)^{-n}$

$$\$$ $$\$$

该式子也可以用于处理$F(G(x))=H(x)$的情况

此时，有$\hat H(F(G(x)))=x$

$G(x)=\widehat {\hat G(F(x))}=H(\hat F(x))$

带入得到$\displaystyle [x^n]G(x)=[x^n]H(\hat F(x))=\frac{1} {n}[x^{n-1}]H’(x)(\frac{x} {F(x)})^n$

即$\displaystyle [x^n]G(x)=\frac{1} {n}[u^{n-1}]H’(u)(\frac{u} {F(u)})^n$

$$\$$

另类拉格朗日反演

依然设$G(x)=\hat F(x)$，则

$\displaystyle [x^n]G^k(x)=[x^{-k-1}]\frac{F’(x)} {F^{n+1}(x)}$

改一下是

$\displaystyle [x^n]G^k(x)=[x^{n-k}] F’(x)(\frac{x} {F(x)})^{n+1}$

更一般的

$\displaystyle [x^n]H(G(x))=[x^n]H(x)F’(x)(\frac{x} {F(x)})^{n+1}$

用途：

你会发现对于不同的$k$，$[x^n]G^k(x)$对应的系数居然来自同一个函数$\displaystyle \frac{F’(x)} {F^{n+1}(x)}$

因此用于处理求多个$k$的问题

---

$$\$$ $$\$$

后记：

明明自己什么都不会还要写博客。。。