前言
在尝试做 P7439 的时候被控到死，于是学习了拉格朗日反演。因为笔者非常弱，所以这篇博客大多都是复述别人的话（？）讲的内容可能有很多谬误而且可能不深刻，请谨慎食用。
复合
记\((F\circ G)(x)\)表示\(F(G(x))\)，\(f_i=[x^i]F(x),g_i=[x^i]G(x)\)。将\(F(G(x))\)写开就是：
复合的运算满足结合律但不一定满足交换律，即：
然后说一下复合问题的解法。一般的做法是根号分治，然后预处理每个块内相对位置的值和每个块第一个位置的值，然后就可以做了。时间复杂度\(O(n^2+n\sqrt n\log n)\)。
其实还有\(O(n\log^2n)\) 的科技解法，这是一位来自 japan 的大神提出的，又有大神在洛谷题解里说明了此做法。但是笔者不是很清楚，就不误人子弟了，放个链接在此，有兴趣可前去研究。
组合意义
我们可以把\(G\)看成将一个组合类排成长度为\(n\)的序列。如果是\(\text{EGF}\)的话，除以\(n!\)就相当于取出一个大小为\(n\)的集合，而外层的\(F\)就是将这\(n\)个元素组合成新对象的方案数。这就是\(\text{Substitution}\)构造。
接下来给出一些基础（？）的复合。
右复合
复合\(cx\)：通过定义可以将常数直接提出来，\(f_n:=f_nc^n\)。
复合\(x^a\)：当\(a\)为正有理数的时候，令\(a={p\over q}\)，如果所有\(q\mid i,f_i\neq0\)，就将\(f_i\)移到\(f_{ia}\)；否则，一般没有有效处理。
复合\(x+c\)：直接用二项式定理拆：
\[\begin{aligned}F(x+c) &= \sum_{i\ge0}f_i(x+c)^i\\&= \sum_{i\ge0}f_i\sum_{j=0}^i{i\choose j}x^jc^{i-j}\\&= \sum_{j\ge0}x^j\sum_{i\ge0}{i\choose j}f_ic^{i-j}\\\end{aligned}\]可以写成卷积形式解决。
复合\(\sqrt{x+1}\)：可以分奇偶讨论。对偶数次的系数，可以单独提取出来分步复合；对奇数次的系数有：
\[\begin{aligned}(x+1)^{n+{1\over2}} &= \sum_{i\ge0}{n+{1\over2}\choose i}x^i\\&= \sum_{i\ge0}x^i{(n+{1\over2})(n-{1\over2})\cdots(n-i+{3\over2})\over i!}\\&= \sum_{i\ge0}x^i{(2n+1)(2n-1)\cdots(2n-2i+3)\over i!2^i}\\&= \sum_{i\ge0}x^i{(2n+1)!!\over i!2^i(2n-2i+1)!!}\\\end{aligned}\]
在一些复合中如果所有幂存在简单递推可以用分治\(\text{NTT}\)做。
左复合
假设现在需要左复合\(G(x)\)，并且我们知道关于\(x,G,G'\dots\)的方程。设\(H(x)=G(F(x))\)，我们就可以用\(H,G\)等表示\(G^{(k)}\)。然后就这样不停代换，最后得到只有\(H\)和\(G\)的微分方程就可以做了。
复合逆
对于复合运算，若令\(H=F\circ G\)，有：
我们称\(G\)是\(F\)的复合逆。
对于复合逆，其实常数项可能非 0，但是为了方便，我们规定常数项为 0，而一次项系数非零。注意复合逆的确定方式可类比乘法逆，我们将 \(F\)和\(G\)都写开就可以得到：
我们把左式\(x\)每项的系数都提取出来就可以得到一些等式，然后又知道\(f_i\)，就可以从低次到高次得到\(g_i\)。
形式洛朗级数
许多形式幂级数操作即使推广到负指数的情况下依旧是成立的。对于一个常数项非零的形式幂级数，我们乘上一个偏移量\(x^{n_0},n_0\in\mathbb {Z},a_{n_0}\neq0\)，得到一个下标从\(n_0\)开始向正无穷延伸的幂级数，称为形式洛朗级数。
写出来是这个样子的：
其中\(a_{n_0}\neq0\)。
可以发现任意一个非零形式洛朗级数都有乘法逆。所以其实形式洛朗级数的四则运算与普通形式幂级数一样，所以为什么要把幂次搞成负数呢？
在开始之前我们先介绍一下它的形式除法。对洛朗级数\(A,B\)，设其\(n_0\)分别为\(n_a,n_b\)，定义\(A\over B\)是一个洛朗级数\(C\)，
因为右边那坨分式是两个普通幂级数的除法，左边是新的\(n_0\)，所以\(C\)也是一个形式洛朗级数。
我们将\(F\)求导，按理来说对于\(\forall i, x^i\)的系数都会传给\(x^{i-1}\)，但是当\(i=0\)的时候系数是不会传递的，于是\(x^{-1}\) 的系数就变成了 0。这是一个特殊的“点”，我们称其为洛朗级数的形式留数。下面请看\(\text{VCR}\)。
引理：对于幂级数\(F(x)\)满足\(n_0=1\)，那么对于\(k\in\mathbb Z\)，有：
\[[x^{-1}]F'F^k=[k=-1]\]
证明考虑\(k\neq-1\)时，对左式逆用形式链式求导得到：
根据形式留数的定义可发现这个是 0。
若\(k=-1\)，有：
这个东西其实就是\(n_0=-1,a_{n_0}=1\)的形式洛朗级数，证毕。
至此，万事俱备，只欠东风！
拉格朗日反演
终于到本体了。
对于幂级数\(F(x)\)满足\(n_0=1,G(F(x))=x\)是其复合逆，那么对于\(n,k\in\mathbb Z\)，有
\[n[x^n]F^k=k[x^{-k}]G^{-n}\]
下面开始证明：
先求导，然后拆开\(F\)，有
提取\(x^{-1}\)的系数，有：
现在我们将左边的式子换一下位置，看好了，
蓝色标记的部分就是上文证明的引理，直接用得到：
推广到其线性组合有扩展版，这更实用于 OI。
另类拉格朗日反演
在一些情况下纯粹利用拉格朗日反演并不一定能帮助我们求算系数，根据需要又有了另类拉格朗日反演。
对于幂级数\(F(x)\)满足\(n_0=1,G(F(x))=x\)是其复合逆，那么对于\(n,k\in\mathbb Z\)，有
\[[x^n]F^k=[x^{-k-1}]G'G^{-n-1}\]
证明：
类似扩展另类拉格朗日反演的复合形式：
到此，恭喜你通关了拉格朗日反演这个知识点，然后因为一些原因笔者鸽掉了练习题，这里放一个找到的有关题的博客。
后记
这篇博客告诉了我们不要随意去开多项式工业，不然你就会陷入很深但又永不循环的沼泽，会浪费掉大量时间（？）
还是希望等笔者有了一定的数学能力后能写出更多优质的博客吧（）
参考资料
浅谈多项式复合和拉格朗日反演 - 洛谷专栏（这篇不错）
从多项式到 Laurent 级数：Lagrange 反演入门 - gsj_z - 博客园（这篇有点晦涩难懂）
拉格朗日反演 - yyyyxh - 博客园（这篇略简略）