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

来自 [noshi91](https://noshi91.hatenablog.com/entry/2024/03/16/224034)。 首先我们考虑一个经典问题：给定 $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](https://www.luogu.com.cn/article/oggmoj4k) 算法，它能解决一元情况下小分式的远处求值。我们尝试对其应用这个算法，即维护 $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)$ 的时间内解决多项式复合与多项式复合逆问题。