拉格朗日反演小记

技术分享 10个月前 (05-10) 0 999+

关注

前言

在尝试做 P7439 的时候被控到死，于是学习了拉格朗日反演。因为笔者非常弱，所以这篇博客大多都是复述别人的话（？）讲的内容可能有很多谬误而且可能不深刻，请谨慎食用。

复合

记 ((Fcirc G)(x)) 表示 (F(G(x)))，(f_i=[x^i]F(x),g_i=[x^i]G(x))。将 (F(G(x))) 写开就是：

[sum f_iG^i(x) ]

复合的运算满足结合律但不一定满足交换律，即：

[(Fcirc G)circ H=Fcirc (Gcirc H) ]

然后说一下复合问题的解法。一般的做法是根号分治，然后预处理每个块内相对位置的值和每个块第一个位置的值，然后就可以做了。时间复杂度 (O(n^2+nsqrt nlog n))。

其实还有 (O(nlog^2n)) 的科技解法，这是一位来自 japan 的大神提出的，又有大神在洛谷题解里说明了此做法。但是笔者不是很清楚，就不误人子弟了，放个链接在此，有兴趣可前去研究。

组合意义

我们可以把 (G) 看成将一个组合类排成长度为 (n) 的序列。如果是 (text{EGF}) 的话，除以 (n!) 就相当于取出一个大小为 (n) 的集合，而外层的 (F) 就是将这 (n) 个元素组合成新对象的方案数。这就是 (text{Substitution}) 构造。

接下来给出一些基础（？）的复合。

右复合

复合 (cx)：通过定义可以将常数直接提出来，(f_n:=f_nc^n)。
复合 (x^a)：当 (a) 为正有理数的时候，令 (a={pover q})，如果所有 (qmid i,f_ineq0)，就将 (f_i) 移到 (f_{ia})；否则，一般没有有效处理。
复合 (x+c)：直接用二项式定理拆：

[begin{aligned} F(x+c) &= sum_{ige0}f_i(x+c)^i\ &= sum_{ige0}f_isum_{j=0}^i{ichoose j}x^jc^{i-j}\ &= sum_{jge0}x^jsum_{ige0}{ichoose j}f_ic^{i-j}\ end{aligned} ]

可以写成卷积形式解决。
复合 (sqrt{x+1})：可以分奇偶讨论。对偶数次的系数，可以单独提取出来分步复合；对奇数次的系数有：

[begin{aligned} (x+1)^{n+{1over2}} &= sum_{ige0}{n+{1over2}choose i}x^i\ &= sum_{ige0}x^i{(n+{1over2})(n-{1over2})cdots(n-i+{3over2})over i!}\ &= sum_{ige0}x^i{(2n+1)(2n-1)cdots(2n-2i+3)over i!2^i}\ &= sum_{ige0}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=Fcirc G)，有：

[H(x)=x ]

我们称 (G) 是 (F) 的复合逆。

对于复合逆，其实常数项可能非 0，但是为了方便，我们规定常数项为 0，而一次项系数非零。注意复合逆的确定方式可类比乘法逆，我们将 (F) 和 (G) 都写开就可以得到：

[sum_{ige0} f_ileft(sum_{j>0} g_jx^jright)^i=x ]

我们把左式 (x) 每项的系数都提取出来就可以得到一些等式，然后又知道 (f_i)，就可以从低次到高次得到 (g_i)。

形式洛朗级数

许多形式幂级数操作即使推广到负指数的情况下依旧是成立的。对于一个常数项非零的形式幂级数，我们乘上一个偏移量 (x^{n_0},n_0inmathbb {Z},a_{n_0}neq0)，得到一个下标从 (n_0) 开始向正无穷延伸的幂级数，称为形式洛朗级数。

写出来是这个样子的：

[F(x)=x^{n_0}left(sum_{ige0}a_{i+n_0}x^iright) ]

其中 (a_{n_0}neq0)。

可以发现任意一个非零形式洛朗级数都有乘法逆。所以其实形式洛朗级数的四则运算与普通形式幂级数一样，所以为什么要把幂次搞成负数呢？

在开始之前我们先介绍一下它的形式除法。对洛朗级数 (A,B)，设其 (n_0) 分别为 (n_a,n_b)，定义 (Aover B) 是一个洛朗级数 (C)，

[C(x)=x^{n_a-n_b}{sum_{ige0}a_{i+n_0}x^ioversum_{jge0}b_{j+n_0}x^j} ]

因为右边那坨分式是两个普通幂级数的除法，左边是新的 (n_0)，所以 (C) 也是一个形式洛朗级数。

我们将 (F) 求导，按理来说对于 (forall i, x^i) 的系数都会传给 (x^{i-1})，但是当 (i=0) 的时候系数是不会传递的，于是 (x^{-1}) 的系数就变成了 0。这是一个特殊的“点”，我们称其为洛朗级数的形式留数。下面请看 (text{VCR})。

引理：对于幂级数 (F(x)) 满足 (n_0=1)，那么对于 (kinmathbb Z)，有：

[[x^{-1}]F'F^k=[k=-1] ]

证明考虑 (kneq-1) 时，对左式逆用形式链式求导得到：

[[x^{-1}]left({1over1+k}F^{k+1}right)' ]

根据形式留数的定义可发现这个是 0。

若 (k=-1)，有：

[{F'over F}=x^{-1}{1+2{a_2over a_1}x+3{a_3over a_1}x^2cdotsover1+{a_2over a_1}x+{a_3over a_1}x^2cdots} ]

这个东西其实就是 (n_0=-1,a_{n_0}=1) 的形式洛朗级数，证毕。

至此，万事俱备，只欠东风！

拉格朗日反演

~~终于到本体了~~。

对于幂级数 (F(x)) 满足 (n_0=1,G(F(x))=x) 是其复合逆，那么对于 (n,kinmathbb Z)，有

[n[x^n]F^k=k[x^{-k}]G^{-n} ]

下面开始证明：

先求导，然后拆开 (F)，有

[begin{aligned} F^k(G(x)) &= x^k \ (F^k)'(G)G' &= kx^{k-1} \ sum_iileft([x^i]F^kright)G^{i-1}G' &= kx^{k-1} \ sum_iileft([x^i]F^kright)G^{i-1-n}G' &= kx^{k-1}G^{-n} \ end{aligned} ]

提取 (x^{-1}) 的系数，有：

[[x^{-1}]sum_iileft([x^i]F^kright)G^{i-1-n}G' = [x^{-1}]kx^{k-1}G^{-n} ]

现在我们将左边的式子换一下位置，看好了，

[sum_iileft([x^i]F^kright){color{blue}[x^{-1}]G^{i-1-n}G'} = [x^{-1}]kx^{k-1}G^{-n} ]

蓝色标记的部分就是上文证明的引理，直接用得到：

[n[x^n]F^k=[x^{-1}]kx^{k-1}G^{-n}=k[x^{-k}]G^{-n} ]

推广到其线性组合有扩展版，这更实用于 OI。

[[x^n]H(F)={1over n}[x^{n-1}]H'left({xover G}right)^n ]

另类拉格朗日反演

在一些情况下纯粹利用拉格朗日反演并不一定能帮助我们求算系数，根据需要又有了另类拉格朗日反演。

对于幂级数 (F(x)) 满足 (n_0=1,G(F(x))=x) 是其复合逆，那么对于 (n,kinmathbb Z)，有

[[x^n]F^k=[x^{-k-1}]G'G^{-n-1} ]

证明：

[begin{aligned} F^k(G(x)) &= x^k \ F^k(G(x))G'G^{-n-1} &= x^kG'G^{-n-1} \ [x^{-1}]sum_ileft([x^i]F^kright)G'G^{i-n-1} &= [x^{-1}]x^kG'G^{-n-1} \ [x^n]F^k &= [x^{-1}]x^kG'G^{-n-1} \ &= [x^{-k-1}]G'G^{-n-1} end{aligned} ]

类似扩展另类拉格朗日反演的复合形式：

[[x^n]H(F)=[x^{n}]HG'left({xover G}right)^{n+1} ]

到此，恭喜你通关了拉格朗日反演这个知识点，然后因为一些原因笔者鸽掉了练习题，这里放一个找到的有关题的博客。