再论组合卷积

· · 题解

@Kazemaru 的 题解 给出了将直接 DP 优化到 O(n^2) 的方法，本质上是优化特殊卷积

h_k=\sum_{i+j=k}\sum_{d\geq 0}\binom{i+d}{d}\binom{j+d}{d}d!f_{i+d}g_{j+d}

的计算。他的推导强依赖于组合观察和容斥原理。

接下来，本文将给出一个结论相同，但基于生成函数的做法。它代表着对一大类“组合卷积”建立对应生成函数的思路，常见的二项卷积等模型都可以统一进来。

读者应当熟知如何从解析组合的观点得到一个组合类的 OGF / EGF，否则可能产生理解障碍。

加入一个新子树时需要算上面的特殊卷积，考虑的组合结构本质上是：

先分析 f\otimes g 的生成函数，设 |f|=a,|g|=b，枚举有多少对点连接而消除

\begin{aligned} f\otimes g &\to \sum_{k=0}^{\min(a,b)} \binom{a}{k}\binom{b}{k}k!\cdot W_{a+b-2k}(x)\\ &= \sum_{k=0}^{\min(a,b)} \frac{a!b!}{k!(a-k)!(b-k)!}\cdot W_{a+b-2k}(x) \end{aligned}

其中 W_n(x) 是大小为 n 的组合对象映射到的生成函数，目前待定。

除了推广 $W_n$，还能对生成函数的“乘积”进行推广。我们希望找到一种**双线性运算** $\star$，使得“生成函数的 $\star$ 运算”能与“部分对消笛卡尔积”相对应。 > - **双线性运算**：二元运算 $\star$ 满足 $A\star B$ 在 $A,B$ 上都是线性的（即有分配率、可提取常数），则称其满足双线性。 > > 普通乘法就是一种双线性运算。 > > - **性质**：任何（满足交换律的）双线性运算都能写成 > $$ > F\star G=\sum_{i}c_i\cdot q_i(F)q_i(G) > $$ > 的形式，其中 $c_i$ 为常数，$q_i$ 为线性映射。注意 $(c_i,q_i)$ 可能有无穷个。 形式化地，记 $F(x)=\sum_{n\geq 0}f_nW_n(x),\ G(x)=\sum_{n\geq 0}g_nW_n(x)$，我们希望 $$ H(x)=F(x)\star G(x)=\sum_{a,b}f_ag_b\big(W_a\star W_b\big) $$ 这需要对每一项组合积都有 $$ W_a\star W_b=\sum_{k=0}^{\min(a,b)} \frac{a!b!}{k!(a-k)!(b-k)!}\cdot W_{a+b-2k} $$ 最简单地，先取 $W_a=x^a$，则我们需要 $$ x^a\star x^b=\sum_{k=0}^{\min(a,b)} \frac{a!b!}{k!(a-k)!(b-k)!}x^{a+b-2k} $$ 考虑将每一项 $\frac{a!b!}{k!(a-k)!(b-k)!}x^{a+b-2k}$ 凑成 $c_k\cdot q_k(x^a)q_k(x^b)$ 的形式，不难想到令 $$ q_k(x^a)=\frac{a!}{(a-k)!}x^{a-k} $$ 可以发现，这恰好是求 $k$ 阶导数。令 $q_k=\mathrm D^k$ ，其中 $\mathrm D$ 是求导算子，它的确有线性性。 至此，我们得到了想要的 $\star$： $$ \begin{aligned} x^a\star x^b&=\sum_{k\geq 0} \frac{(\mathrm D^k x^a)(\mathrm D^k x^b)}{k!}\\ F(x)\star G(x)&=\sum_{k\geq 0} \frac{(\mathrm D^k F)(\mathrm D^k G)}{k!}\\ \end{aligned} $$ 或者更简洁地，$\star = e^{\mathrm D\otimes\mathrm D}$。 $\star$ 的代数结构已经明了，但它不好计算。考虑换一组更好的基，使得 $\star$ 在这组基上的结构简单。具体地，我们希望构造一组多项式基底 $W_m(x)$，使得 $$ W_a\star W_b=W_{a+b} $$ 这样，$F\star G$ 可以完全对应系数 $f,g$ 的加法卷积，就容易计算了。 > 更具体地，计算一开始那个特殊卷积的流程是： > > - 初始时给出 $F(x)=\sum_{n\geq 0}f_nx^n$，$G(x)=\sum_{n\geq 0}g_nx^n$。 > - 将基底换为 $W_m(x)$，计算系数 $\hat f_n,\hat g_n$ 使得 $F(x)=\sum_{n\geq 0}\hat f_nW_n(x)$，$G(x)=\sum_{n\geq 0}\hat g_nW_n(x)$。 > - 求 $\hat f,\hat g$ 的加法卷积得到 $\hat h$。 > - 将基底从 $W_m$ 换回 $x^m$，得到 $H(x)=\sum_{n\geq 0}h_nx^n$ 的各项系数。 > > 接下来，我们要找出这样的基底，并得到高效的换基算法。 为了一并分析整组多项式基 $W_0,W_1,\cdots,W_m\cdots$，将其打包为二元形式幂级数 $$ \Phi(x,t)=\sum_{m\geq 0}W_m(x)\frac{t^m}{m!} $$ 观察 $W_m$ 的 $\star$-性质在 $\Phi(x,t)$ 身上的体现 $$ \begin{aligned} \Phi(x,s)\star\Phi(x,t) &=\left(\sum_{m\geq 0}W_m(x)\frac{s^m}{m!}\right)\star\left(\sum_{n\geq 0}W_n(x)\frac{t^n}{n!}\right)\\ &=\sum_{n,m\geq 0}\frac{s^mt^n}{m!n!}\cdot\big(W_n(x)\star W_m(x)\big)\\ &=\sum_{n,m\geq 0}\frac{s^mt^n}{m!n!}W_{n+m}(x)\\ &=\sum_{k\geq 0}\frac{W_k(x)}{k!}\sum_{m=0}^k\binom{k}{m}s^mt^{k-m}&(k=n+m)\\ &=\sum_{k\geq 0}W_k(x)\frac{(s+t)^k}{k!}\\ &=\Phi(x,s+t) \end{aligned} $$ 注意，此时 $\mathrm D$ 是 $x$ 上的偏导算子，其他形式元 $s,t$ 和常数一样可以自由进出 $\star$。 综上，只需构造二元生成函数 $\Phi(x,t)$ 满足 $$ \Phi(x,s)\star\Phi(x,t)=\Phi(x,s+t) $$ 问题和导数有关，可以先尝试令 $\Phi(x,t)=e^{xt}$（这是 $\mathrm D$ 最简单的特征函数），此时 $$ \begin{aligned} \Phi(x,s)\star\Phi(x,t)&=e^{xs}\star e^{xt}\\ &=\sum_{k\geq 0}\frac{(\mathrm D^ke^{xs})(\mathrm D^ke^{xt})}{k!}\\ &=\sum_{k\geq 0}\frac{(st)^ke^{x(s+t)}}{k!}\\ &=e^{st}e^{x(s+t)}\\ &=e^{st}\Phi(x,s+t) \end{aligned} $$ 几乎已经成功，只多出了一项 $e^{st}$，考虑用附加因子法将其消去，令 $$ \Phi(x,t)=\alpha(t)e^{xt} $$ 则 $$ \Phi(x,s)\star\Phi(x,t)=\frac{\alpha(s)\alpha(t)e^{st}}{\alpha(s+t)}\Phi(x,s+t) $$ 这要求附加因子 $\alpha(t)$ 满足 $$ \alpha(s)\alpha(t)e^{st}=\alpha(s+t) $$ 取对数，令 $\beta(t)=\log \alpha(t)$，则 $$ \beta(s+t)-\beta(s)-\beta(t)=st $$ 这是经典的。类似 Chirp Z-Transform 的核心配凑，令 $\beta(n)=\binom{n}{2}$ 或 $\beta(n)=\frac{n^2}{2}$ 都能满足要求。（事实上通解是 $\frac{n^2}{2}+cn$，$c$ 为任意常数） 取 $\beta(n)=\frac{n^2}{2}$，$\alpha(t)=e^{t^2/2}$，则 $\Phi(x,t)=e^{t^2/2}e^{xt}$。 至此，我们本质上掌握了各个 $W_m(x)$，如果想看具体系数： $$ \begin{aligned} W_m(x)&=\big[\tfrac{t^m}{m!}\big]\Phi(x,t)=\big[\tfrac{t^m}{m!}\big]e^{t^2/2+xt}\\ &=\big[\tfrac{t^m}{m!}\big]\sum_{k\geq 0}\frac{\big(\tfrac{t^2}{2}+xt\big)^k}{k!}\\ &=\big[\tfrac{t^m}{m!}\big]\sum_{k\geq 0}\frac{t^k}{k!}\sum_{i=0}^k\binom{k}{i}\left(\frac{t}{2}\right)^ix^{k-i}\\ &=\big[\tfrac{t^m}{m!}\big] \sum_{n\geq 0}t^n \sum_{0\leq i\leq \lfloor n/2\rfloor}\frac{x^{n-2i}}{i!(n-2i)!2^i}&(n=k+i)\\ &=\sum_{0\leq i\leq \lfloor m/2\rfloor}\frac{m!x^{m-2i}}{i!(m-2i)!2^i} \end{aligned} $$ > 1. 实际上，$W_m$ 是 Hermite 多项式 ${\rm He}_m(x)$。 > 2. $\star$ 的引入不是必要的，如果我们一开始就能想到令 $W_m={\rm He}_m(x)$，就能直接把“部分对消笛卡尔积”变成普通乘法。这里 $\star$ 只是起到便于推导的作用。 接下来考虑如何进行基变换，由 $\hat f$ 得到 $f$ 是简单的，直接展开 $W_m$ 的系数就行。考虑如何从 $f$ 得到 $\hat f$，这相当于将方幂 $x^m$ 展开到 $W_m$ 基上。 将方幂基也打包为二元形式幂级数 $\Phi_0(x,t)=\sum_{n\geq 0}\frac{x^nt^n}{n!}=e^{xt}$，则 $$ \Phi_0(x,t)=e^{-t^2/2}\Phi(x,t) $$ 对右侧提取 $\big[\frac{t^n}{n!}\big]\big[W_m(x)\big]_{W}$ 项系数得 $$ \begin{aligned} &\big[\tfrac{t^n}{n!}\big]\big[W_m(x)\big]_{W}\ e^{-t^2/2}\Phi(x,t)\\ =&\big[\tfrac{t^n}{n!}\big]\big[W_m(x)\big]_{W}\ e^{-t^2/2}\sum_{k\geq 0}\frac{t^k}{k!}W_k(x)\\ =&\big[\tfrac{t^n}{n!}\big]\frac{t^me^{-t^2/2}}{m!}\\ =&\big[2|(n-m)\big]\frac{n!}{m!\big((m-n)/2\big)!(-2)^{(m-n)/2}} \end{aligned} $$ 即 $$ x^n=\sum_{0\leq i\leq \lfloor n/2\rfloor}\frac{(-1)^in!}{i!(n-2i)!2^i}W_{n-2i}(x) $$ > 或者（利用哑演算等技术）注意到 $W_m(x)=e^{-\mathrm D^2/2}x^m$，根据算子 $e^{-\mathrm D^2/2}$ 的线性性，$\hat f\to f$ 的变换相当于对多项式施加 $e^{-\mathrm D^2/2}$；那么逆变换（$f\to\hat f$）就是 $e^{\mathrm D^2/2}$。这样也可以得到系数。 至此，我们得到了 @Kazemaru 题解中需要的所有代数结论。 如果只是想快速计算一次卷积，核心在于快速计算基变换；基变换中奇偶位置互不干扰，且各自形成加法卷积，可以做到 $O(n\log n)$。