拉格朗日反演 (Lagrange Inversion)
拉格朗日反演 (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}](\frac{1}{F(x)})^n\)
由于 \([x^0]F(x)=0\) 无法求逆，所以上式更通用的形式是：
\(\displaystyle [x^n]G(x)=\frac{1}{n}[x^{n-1}](\frac{x}{F(x)})^n\)
### 求解复合逆
对于给定的 \(F(x)\)，求其复合逆 \(G(x)=\hat F(x)\)。
带入拉格朗日反演的式子：
\(\displaystyle G(x)=\sum \frac{1}{i}[x^{i-1}](\frac{x}{F(x)})^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}](\frac{u}{F(u)})^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\) 的问题。
后记：
明明自己什么都不会还要写博客。。。