多项式不存在了：多项式复合（逆）的 O(nlog^2n) 做法

· · 题解

来自 noshi91。

首先我们考虑一个经典问题：给定 n 次多项式 F(x)，计算 [x^n] F^0(x), [x^n] F^1(x), \dots, [x^n] F^n(x)。不失一般性，假设 F(0) = 0。

这等价于计算二元分式 [x^n] \frac 1{1-yF(x)}。

考虑 Bostan-Mori 算法，它能解决一元情况下小分式的远处求值。我们尝试对其应用这个算法，即维护 U_t(x, y), V_t(x, y) 表示第 t 轮后的子问题是

\left[x^{\lfloor n/2^t\rfloor}\right] \frac{U_t(x, y)}{V_t(x, y)}

迭代时，我们每次将分式变为

\frac{U_t(x, y) V_t(-x, y)}{V_t(x, y) V_t(-x, y)}

此时分母只包含偶数次项，分子分母可以同时保留一半次数的项进行递归。

现在我们考虑这个过程：注意第 t 轮 x 只需要最多 n/2^t 次，而 y 的次数每轮倍增，来到 2^t 次。因此，每一轮的次数是 O(n) 的。

若多项式乘法复杂度为 \mathsf M(n)，总复杂度即 O(\mathsf M(n) \log n)。

我们现在来考虑这个问题带来了什么：

根据拉格朗日反演，[x^n] F^k(x) = \frac kn [x^{n-k}] \left(\frac x{F^{\langle -1 \rangle}(x)}\right)^n，因此我们直接可以得到复合逆。

进一步，考虑多项式复合 G(F(x)) = \sum_{k\ge 0} G_k F^k(x)，我们至少可以通过以上方法得到其 n 次项系数。

更惊人的是，事实上，若我们将这个问题写作：给定数列 a_k，求数列

b_j = \sum_{k=0}^n a_k [x^j] F^k(x)

则其转置问题即

a_k = \sum_{j=0}^n b_j [x^j] F^k(x)

对于此问题，若记 H(x) = \sum_{j=0} b_j x^{n-j}，则只需求 [x^n] \frac{H(x)}{1-yF(x)}。容易发现上述做法仍然成立。

因此，人类已经可以在 O(\mathsf M(n) \log n) 的时间内解决多项式复合与多项式复合逆问题。