浅谈多项式复合和拉格朗日反演

发表于 | 分类于 |

作者是个民科 OIer，所写内容可能包含巨大多理论错误或常识性错误，敬请读者一一指出或喷作者。

复合

对于形式幂级数 \(F(x),G(x)\)，记 \(f_n = [x^n] F(x)\)，那么定义 \(F\) 和 \(G\) 的复合为 \[ \sum\limits_{n\ge 0} f_n G^n(x) \]

显然，当 \(F(x)\) 的项有限或 \(G(0) = 0\) 时这个复合是良定义的。
通常把它记为 \((F \circ G)(x)\)。

但是对于一般的复合问题，目前并没有什么十分优秀且实用的解法。目前在 OI 中已引入的算法最优的复杂度为 \(O((n\log n)^{3/2})\)，当然常数巨大。在实践中，基于根号分治的一种 \(O(n^2 + n\sqrt n \log n)\) 的算法更为实用。
可参见洛谷 5373。

组合意义

我们知道 \(G^n(x)\) 无论 \(G\) 是 OGF 或 EGF，都可以看作将其蕴含的一类对象（也就是组合类）排成长度为 \(n\) 的序列。
在 EGF 下，对其除以 \(n!\) 就相当于取出大小为 \(n\) 的集合（这个 \(n!\) 在 \(F\) 也为 EGF 时就天然得到）。
而 \(f_n\) 则描述了将这 \(n\) 个 \(G\) 中元素拼接成一个新对象的方案数。

在组合结构符号化中，这就是所谓的 Subsitution 构造。

常见计算方式

令下文要左 / 右复合特定幂级数的幂级数为 \(F(x)\)，且 \(f_n = [x^n] F(x)\)。

右复合特定幂级数

复合 \(cx\)：
这是最为简单的一类，将 \(f_n\) 变换为 \(f_n c^n\) 即可。

复合 \(x^a\)，其中 \(a\) 为正有理数：
在 \(a\) 为整数时，将 \(f_n\) 的系数移动到 \(f_{na}\) 即可。
在 \(a\) 为有理数时，令 \(a=\frac pq\)，如果所有 \(f_n \ne 0\) 的 \(n\) 都满足 \(q \mid n\)，则直接令 \(f_n\) 移动到 \(f_{na}\) 即可；否则，一般来说无法有效处理，需要整体考虑。

复合 \(x+c\)：
根据二项式定理，我们知道 \[ \begin{aligned} F(x+c) &= \sum\limits_{n\ge 0} f_n (x+c)^n \\ &= \sum\limits_{n\ge 0} f_n \sum\limits_{i=0}^n \binom ni x^i c^{n-i} \\ &= \sum\limits_{i\ge 0} x^i \sum\limits_{n\ge 0} \binom ni f_n c^{n-i} \end{aligned} \]

容易进一步写作差卷积形式，并转化为和卷积解决。

复合 \(\sqrt{1+x}\)：
对于偶数次数部分的系数，可以单独提取出来然后首先复合 \(\sqrt x\) 再复合 \(1+x\)。
对于奇数次数部分的系数，考虑 \((1+x)^{i+1/2}\)，则 \[ \begin{aligned} (1+x)^{i+1/2} &= \sum\limits_{j\ge 0} \binom{i+\frac 12}j x^j \\ &= \sum\limits_{j\ge 0} x^j \frac{(2i+1) \cdot (2i-1) \cdots (2i-2j+3)}{j! 2^j} \\ &= \sum\limits_{j\ge 0} x^j \frac{(2i+1)!!}{j! 2^j (2i-2j+1)!!} \end{aligned} \]

代入系数后同样可以推得卷积形式。

左复合特定幂级数

对于这样的复合问题，通常会更为简单。
倘若需要左复合 \(G(x)\)，而我们知道一个关于 \(x,G,G',\dots\) 的方程。
则设 \(H(x) = G(F(x))\)，通过递推容易将 \(G^{(k)}\) 写作与 \(H,G\) 和其导数相关的形式。
然后在方程中替换掉 \(G^{(k)}\)，我们即得一个关于 \(H\) 和 \(G\) 的微分方程。
这个时候，运用常用的求解幂级数方程的算法计算即可。

当然，在 \(G\) 的项数较少时，也可以暴力计算。

另外，只要能快速计算左复合 \(G\)，就可以利用在同复杂度内计算 \(G\) 的复合逆。
当然一般情况下，如果可以快速计算左复合，也可以利用类似的方式求出 \(G\) 的复合逆的方程并直接求解。

例：CF438E

对于一棵有根无标号二叉树，对其每个结点赋予一个正整数权值，且在 \(\{c_1,c_2,\dots,c_n\}\) 中。
给定 \(m\)，问权值为 \(0,1,\dots,m\) 的二叉树数量，模 \(998244353\)。

根据经典的卡特兰数，我们知道 \(n\) 个结点的有根无标号二叉树的生成函数满足 \[ C(x) = xC^2(x)+1 \]

现在我们考虑实际上的一个结点。对权值定义 OGF，那么它就是 \[ W(x) = \sum\limits_{i=1}^n x^{c_i} \]

根据如上的组合意义，我们直接知道答案 \(F = C \circ W\)。然后根据如上方程，就有 \[ F = WF^2+1 \]

可选的处理方式有解出根后套用多项式开根模板或是直接对其牛顿迭代。通常认为后者更易实现。

拉格朗日反演

为了看起来我写了证明，还是稍微引入一点代数知识。

形式洛朗级数

记域 \(K\) 上的形式洛朗级数为 \(K((x))\) 或 \(K[[x]][x^{-1}]\)。也即对 \(f(x) \in K((x))\)，且 \(f \ne 0\)，存在数列 \(\{a_n\}_{n \ge n_0}\)，有 \[ f(x) = x^{n_0} \left(\sum\limits_{n\ge 0} a_{n+n_0} x^n\right) \]

其中 \(a_{n_0} \ne 0\)。
对于 \(k \in \mathbb Z\)，可以在 \(K((x))\) 中定义 \(f^k\) 为 \[ f^k(x) = x^{n_0k} \left(\sum\limits_{n\ge 0} a_{n+n_0} x^n\right)^k \]

证明

我们引入一个在特征为 \(0\) 的域上的代数证明，在实践中这已经足够。

引理：对于幂级数 \(F(x)\) 满足 \(n_0 = 1\)，那么对于 \(k \in \mathbb Z\)，有 \[[x^{-1}]F'F^k = [k=-1]\]

证明略。只需在 \(k\ne -1\) 时考察 \(\frac1{k+1}F^{k+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}\]

容易发现这是非常有对称性的。
证明： \[ \begin{aligned} F^k(G(x)) &= x^k \\ (F^k)'(G)G' &= kx^{k-1} \\ \sum\limits_i i([x^i] F^k)G^{i-1}G' &= kx^{k-1} \\ \sum\limits_i i([x^i] F^k)G^{i-1-n}G' &= kx^{k-1} G^{-n} \\ [x^{-1}]\sum\limits_i i([x^i] F^k)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} \end{aligned} \]

推及其线性组合，我们知道所谓“扩展拉格朗日反演” \[ [x^n] H(F) = \frac 1n [x^{n-1}] H' \left(\frac xG\right)^n \]

其中 \(H \in K((x))\)。

这一形式往往更适于 OI 中的计算。

事实上，对于扩展拉格朗日反演，利用复合的组合意义描述复合逆的组合意义，可以得到一个基于 Prufer 序列的双射证明。
具体可参考 https://xyix.gitee.io/posts/?page=2&postname=lagrange-inv-bij。

另类拉格朗日反演

在一些情况下纯粹利用拉格朗日反演并不一定能帮助我们求算系数，例如 \(n=0,k<0\)。从而引出了

另类拉格朗日反演：对于幂级数 \(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}\]

证明： \[ \begin{aligned} F^k(G(x)) &= x^k \\ \sum\limits_i ([x^i] F^k)G^i &= x^k \\ \sum\limits_i ([x^i] F^k)G'G^{i-n-1} &= x^k G'G^{-n-1} \\ [x^{-1}]\sum\limits_i ([x^i] F^k)G'G^{i-n-1} &= [x^{-1}]x^k G'G^{-n-1} \\ [x^n]F^k &= [x^{-1}]x^k G'G^{-n-1} \\ &= [x^{-k-1}] G'G^{-n-1} \end{aligned} \]

我们也可以写作类似扩展拉格朗日反演的复合形式 \[ [x^n] H(F) = [x^n] H G' \left(\frac xG\right)^{n+1} \]

应用

对已知复合逆的幂级数提取系数

例：洛谷 7592 弱化版

给定 \(n,k_1,k_2\)，统计所有具有 \(n\) 个结点，且满足每个非叶结点必为 \(k_1\) 或 \(k_2\) 个儿子的无标号有根树的个数。
答案对 \(P = 998244353\) 取模。

令答案的生成函数为 \(F(x)\)，则根据题意可以列出方程 \[ F = x( 1 + F^{k_1} + F^{k_2} ) \]

显然其复合逆即为 \(\frac x{ 1 + x^{k_1} + x^{k_2} }\)。

根据拉格朗日反演 \[ [x^n] F = \frac1n [x^{n-1}] ( 1 + x^{k_1} + x^{k_2} )^n \]

提取系数 \[ \begin{aligned} [x^{n-1}] ( 1 + x^{k_1} + x^{k_2} )^n &= [x^{n-1}] \sum\limits_{i=0}^n \binom ni (x^{k_1}+x^{k_2})^i \\ &= \sum\limits_{i=0}^n \sum\limits_{k=0}^i \binom ni \binom ik [kk_1 + (i-k)k_2 = n-1] \end{aligned} \]

枚举 \(i\)，容易发现使艾佛森括号取到 \(1\) 的 \(k\) 唯一，直接提取即可。
时间复杂度 \(O(n)\)。

对多元函数的其中一个元应用拉格朗日反演

例：LibreOJ 6728

有 \(n\times m\) 个格子，每个格进行染色，可以选择 \(k\) 种颜色之一。对于集合 \(S, T\)，你需要计数有多少种格子的染色方案，满足：

  • 对于每一行的图案拿出来，和它相同的图案总共有 \(r\) 行（含自身），则 \(r\in S\)。
  • 对于每一列的图案拿出来，和它相同的图案总共有 \(c\) 列（含自身），则 \(c\in T\)。

答案对 \(P = 998244353\) 取模。

根据斯特林反演，我们考虑给每个大小为 \(i\) 的集合赋予一个容斥系数 \(a_i\)，而一个集合划分的贡献定义为各个集合的系数的乘积。
那么令 \(F = \sum\limits_{i\in S} \frac{x^n}{i!},A = \sum\limits_{i\ge 0} \frac{a_i}{i!}\)，显然就有 \(\exp A = 1 + F\)。
即 \(A = \ln(1+F)\)。

记 \(f_{n,i}\) 为将 \(n\) 个元素划分到 \(i\) 个集合的所有方案的贡献和，则有 \[ f_{n,i} = n! [x^n] \frac{A^i}{i!} = n! [x^n] \frac{\ln^i(1+F)}{i!} \]

类似地定义 \(g\)，那么类似 Bluestein's Algorithm 不难计算答案 \[ \sum\limits_{i=1}^n \sum\limits_{j=1}^m f_{n,i} g_{m,j} k^{ij} \]

接下来考察 \(f\) 的求算。我们知道这实际上就是 \([x^n] \exp(u \ln(1+F))\)。根据拉格朗日反演有 \[ [x^n] \exp(u \ln(1+F)) = \frac 1n [x^{n-1}] u{\rm e}^{ux} \left(\frac x{(\ln(1+F))^{<-1>}(x)}\right)^n \]

其中 \(F^{<-1>}\) 为 \(F\) 的复合逆。
由于 \(a=|S|\) 较小，所以可以 \(O(an\log n)\) 牛顿迭代求出 \((\ln(1+F))^{<-1>}\)。

事实上，如上例题也揭示了一个经典问题的常用解法：对给定的 \(F,n,m\)，求所有 \(1 \le k \le m\) 的 \([x^n] F^k\)。
而对于多元函数的其中一个元应用拉格朗日反演也是常见的技巧。

如何向复合的形式贴近

例 1

证明 \[ \frac 1{ \sqrt{1-4x} } \left(\frac{ 1-\sqrt{1-4x} }{2x}\right)^m = \sum\limits_n \binom{m+2n}n x^n \]

EI 在 营业日志 2020.5.9 借助拉格朗日反演给出了一个证明，但这里我们利用另类拉格朗日反演可以给出更简洁的推导。

\(\sqrt{1-4x}\) 使我们联想到二叉树方程 \(F = x(1+F)^2\) 的根 \(F = \frac{ 1-2x-\sqrt{1-4x} }{2x}\)，因此将原式写作复合形式 \[ \frac 1{ \sqrt{1-4\frac F{(1+F)^2}} } (1+F)^m = \frac{ (1+F)^{m+1} }{1-F} \]

接下来就很简单了，运用另类拉格朗日反演就有 \[ \begin{aligned} [x^n]\frac{ (1+F)^{m+1} }{1-F} &= [x^n] \frac{ (1+x)^{m+1} }{1-x} \left(\frac x{(1+x)^2}\right)' (1+x)^{2(n+1)} \\ &= [x^n] \frac{ (1+x)^{m+1} }{1-x} \frac{1-x}{(1+x)^3} (1+x)^{2(n+1)} \\ &= [x^n] (1+x)^{2n+m} \\ &= \binom{2n+m}n \end{aligned} \]

例 2

计算 \([u^n] \frac{ {\rm e} ^{-u} }{(1- {\rm e} ^u+u {\rm e} ^u)(1-t {\rm e} ^u)} \bmod t^{n+1}\)，系数模 \(998244353\)。
出自 CF1349F2。

我们注意到 \(\frac{ {\rm e} ^{-u} }{1- {\rm e} ^u+u {\rm e} ^u}\) 部分容易直接计算，记为 \(u^{-1} R(u)\)。接下来需要计算 \[ [u^{n+1}] \frac{R(u)}{1-t{\rm e}^u} \]

然而 \({\rm e}^u\) 并不能被应用拉格朗日反演，不过考虑设 \(F(u) = {\rm e}^u-1\)，然后令 \(G = F^{<-1>} = \ln(1+u),Q(u) = R(G)\)，问题就变成了 \[ \begin{aligned} [u^{n+1}] \frac{Q(F)}{1-t(1+F)} &= \frac1{n+1} [u^n] \left(\frac{Q(u)}{1-t(1+u)}\right)' \left(\frac u{G(u)}\right)^{n+1} \\ &= \frac1{n+1} [u^n] \left(\frac{tQ(u)}{(1-t(1+u))^2}+\frac{Q'(u)}{1-t(1+u)}\right) \left(\frac uG\right)^{n+1} \end{aligned} \]

设 \(H = \left(\frac uG\right)^{n+1}\)，有 \[ \begin{aligned} & \quad \; [u^n] \left(\frac{tQ(u)}{(1-t(1+u))^2}+\frac{Q'(u)}{1-t(1+u)}\right) H \\ &= [u^n] \left(Q\sum\limits_{i\ge 0}(i+1) t^{i} (1+u)^i+Q'\sum\limits_{i\ge 0} t^i (1+u)^i\right) H \end{aligned} \]

然后 \[ \begin{aligned} & \quad \; [u^n t^k] \left(\frac{tQ(u)}{(1-t(1+u))^2}+\frac{Q'(u)}{1-t(1+u)}\right) H \\ &= [u^n] \left(Q\cdot k(1+u)^{k-1}+Q'\cdot (1+u)^k\right) H \\ &= k[u^n] (1+u)^{k-1} QH + [u^n] (1+u)^k Q'H \\ &= k\sum\limits_{i=0}^n \binom{k-1}i [x^{n-i}] QH + \sum\limits_{i=0}^n \binom ki [x^{n-i}] Q'H \end{aligned} \]

容易卷积。
时间复杂度 \(O(n \log n)\)。

总结

有时容易应用拉格朗日反演的形式并不非常明晰，这时为了容易计算，我们往往会根据经验选出一些更简洁的函数作为其中右复合的部分。
对于带有根式的情况，我们往往联想二叉树方程（因为其复合逆是很简单的）。而经过换元大部分都可以转化为其形式。
而常数项不为 \(0\) 者，则可以试着直接减去这个常数，在某些时候也可以试着给其乘上一个元。
\(F\) 的最低项为 \(x^c\) \((c > 1)\) 时，可以设 \(([x^c] F)G^c = F\)，然后将其改写为右复合 \(G\) 的形式。

逆用拉格朗日反演

这里指的并不是利用拉格朗日反演的逆命题证明复合逆关系，而是仅仅单纯地从等式右边推及等式左边。
以下借助拉格朗日反演和另类拉格朗日反演分别给出一个例子。

例 1

求 \(F(x) = \sum\limits_{n\ge 0} n^{n-1} \frac{x^n}{n!}\) 的复合逆。

注意到 \[ [x^n] F = \frac{ n^{n-1} }{n!} = \frac 1n \frac{ n^{n-1} }{(n-1)!} = \frac 1n [x^{n-1}] {\rm e}^{nx} = \frac 1n [x^{n-1}] \left(\frac x{ x{\rm e}^{-x} }\right)^n \]

根据拉格朗日反演，我们知道 \(F\) 的复合逆就是 \(x{\rm e}^{-x}\)。

当然，根据组合意义我们立刻知道这是有标号有根树的 EGF，从而有方程 \[ F = x{\rm e}^F \]

这就验证了我们的结果。

例 2

求算 \(Q_k(x) = \sum_n \binom{2n-k}{n-k} x^n\) 的封闭形式。

出自 营业日志 2020.7.4 新瓶旧酒，EI 在其中给出了一个利用基础组合恒等式建立线性递推的做法，这里借助另类拉格朗日反演给出另一个做法。

注意到 \[ \begin{aligned} [x^n] Q_k(x) &= [x^n] x^k (1+x)^{2n-k} \\ &= [x^n] x^k (1+x)^{-k-2} (1+x)^{2(n+1)} \\ &= [x^n] x^k (1+x)^{-k-2} \left(\frac x{ x(1+x)^{-2} }\right)^{n+1} \\ &= [x^n] \frac{x^k (1+x)^{1-k}}{1-x} \cdot \frac{1-x}{(1+x)^3} \left(\frac x{ x(1+x)^{-2} }\right)^{n+1} \\ \end{aligned} \]

因此 \(Q_k(x) = \frac{ F^k (1+F)^{1-k} }{1-F}\)，其中 \(F\) 的复合逆为 \(G(x) = \frac x{(1+x)^2}\)。
也即 \[ F = x(1+F)^2 \]

可以解得 \[ F = \frac{ 1-2x-\sqrt{1-4x} }{2x} \]

代入并进行化简可得 \[ Q_k = \frac{\left(\frac{ \sqrt{1-4x} }2\right)^k}{ \sqrt{1-4x} } \]

这和 EI 得到的结果也是一致的。

多元拉格朗日反演

顺着一般的拉格朗日反演，我们考虑将其扩展到多元。然而我们并不能很完美地对一个多元幂级数定义复合逆。
所以我们首先引入和一个与复合的组合意义息息相关的概念。

树形复合方程

令 \(\mathbf x = (x_1,x_2,\dots,x_n)\)，对于 \(n\) 元幂级数 \(G_i(\mathbf x)\) 满足 \(G_i(\mathbf 0) \ne 0\)，再令 \(\mathbf F = (F_1,F_2,\dots,F_n)\) 满足 \(F_i = x_i G_i(\mathbf F)\)，则记 \(\mathbf F\) 是由 \(\mathbf G\) 定义的一组树形复合方程。

称其为树形是很形象的。
我们首先考虑只有一元的情况，根据复合的组合意义，可以注意到方程 \[ F = xG(F) \]

可以视作 \(F\) 描述了一族有根树，其安排 \(k\) 个儿子的方案数为 \([x^k] G\)，并以一个 \(x\) 描述新树的根。

而扩展到多元，我们不妨视其为 \(n\) 类不同的结点，则 \(F_i\) 就描述了以 \(i\) 类结点为根的有根树，\(G_i\) 则描述了以 \(i\) 类结点为根时，每种儿子集合的安排方式。

本体

对于 \(n\) 元幂级数 \(H(\mathbf x)\) 和由 \(\mathbf G\) 定义的树形复合方程 \(\mathbf F\)，有 \[ [\mathbf x^{\mathbf k}] H(\mathbf F) = [\mathbf x^{\mathbf k}] H \mathbf G^{\mathbf k} \left\|[i=j]-\frac{x_j}{G_i(\mathbf x)}\frac{\partial G_i(x)}{\partial x_j}\right\| \]

其中 \(\mathbf x^{\mathbf k} = x_1^{k_1}x_2^{k_2}\cdots x_n^{k_n}\)，\(\|*\|\) 表示行列式。

证明

依然引入一个在特征为 \(0\) 的域上的证明，不过这次会显得相对组合。

考虑证明 \(H = \mathbf x^{\mathbf m}\) 的情形，然后推及其线性组合。
则 \[ [\mathbf x^{\mathbf k}] \mathbf F^{\mathbf m} = [\mathbf x^{\mathbf k}] \mathbf x^{\mathbf m} \mathbf G^{\mathbf k} \left\|[i=j]-\frac{x_j}{G_i(\mathbf x)}\frac{\partial G_i(x)}{\partial x_j}\right\| \]

从 EGF 的角度审视，则左边即为以 \(m_i\) 棵以 \(i\) 类结点为根的树组成的森林的个数。
而右边的 \(\mathbf x^{\mathbf m} G^{\mathbf k}\) 则表示取消树的限制，只保留对根的强制要求，然后每个结点任选可能成为儿子的结点作为儿子。
自然，这样会连出环。则需要容斥，令 \[ \mathbf M = \left(\frac{x_j}{G_i(\mathbf x)}\frac{\partial G_i(x)}{\partial x_j}\right)_{i,j=1}^n \]

我们注意到 \(x_j \frac{\partial G_i(x)}{\partial x_j}\) 实际上是给 \(G_i(x)\) 的每一项乘上 \(x_j\) 的次数，即从所有 \(j\) 类点中钦定一个点。
则对于 \(t\)，考虑 \(\mathbf M^t\) 主对角线上的一个位置 \(i,i\) 在最终乘积中的一项，其描述了首先去除 \(t\) 类点本身选取儿子的贡献，然后钦定这 \(t\) 类点连成一个环（互相从前一类点中钦定一个）。
那么实际上的一个长度为 \(t\) 的环会被统计 \(\frac 1t\) 次。
故钦定单个环的生成函数为 \[ C = \sum\limits_{t\ge 1} \frac 1t \operatorname{tr} \mathbf M^t = \operatorname{tr}\left(\sum\limits_{t\ge 1} \frac 1t \mathbf M^t\right) = \operatorname{tr}(-\log(\mathbf I - \mathbf M)) \]

进一步容斥，则生成函数为 \[ \sum\limits_{l\ge 0} \frac{(-C)^l}{l!} = \exp(-\operatorname{tr}(-\log(\mathbf I - \mathbf M))) = \exp(\operatorname{tr} \log(\mathbf I - \mathbf M)) \]

根据 \(\det \exp \mathbf A = \exp \operatorname{tr} \mathbf A\)，故容斥因子即为 \(\det(\mathbf I - \mathbf M)\)。

事实上，不难发现这个矩阵与矩阵树定理中基尔诺夫矩阵的高度相似性，因此某种意义上可以利用矩阵树定理对其进行证明。
（这同时可以利用组合意义证明 \(\det \exp \mathbf A = \exp \operatorname{tr} \mathbf A\)）

应用

出于种种原因，我并不愿意在此处展开举例说明其应用。
多元拉格朗日反演在 OI 中的应用还十分有限，其题目几乎都可以用矩阵树定理 / Prufer 序列 / 组合意义解决。
据我所知，x义x 和 EI 都曾经试过出题来引入多元拉格朗日反演（虽然 EI 其实只是给集训队论文找个例题），但都被更初等的做法解决了。
所以，希望看到这里的你，能够延续他们的步伐。

参考文献