自动搬运

查看原文

来自洛谷，原作者为

	Aleph1022 「笑可以天然地飘洒 心是一地草野 唯一的家乡」

搬运于2025-08-24 22:10:07，当前版本为作者最后更新于2024-03-17 06:12:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

来自 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)$ 的时间内解决多项式复合与多项式复合逆问题。