3log 预处理，2log 查询的多项式复合幂算法

· · 算法·理论

在学习 Abhyankar-Gurjar 反演公式的证明中发现的一个新玩意，感觉应用潜力巨大，提前公开一下。如果大家有什么新的想法，欢迎讨论。这篇就不投文章广场了，方便随时修改。

我们下面会用到的结论基本来自论文 EXPONENTIAL FORMULAS FOR THE JACOBIANS AND JACOBIAN MATRICES OF ANALYTIC MAPS，结论我就直接用了，证明请看原文。我后面写 A-G 反演公式的证明时也会复述一遍证明。

注：对于幂级数 f，我们记其最低次数为 o(f)，记其 k 次复合为 f^{[k]}。如果 k 是负的，那就是其反函数的 -k 次复合（如果反函数存在）。

我们的主要成果为，给定幂级数 f 满足 o(f)=1,[x^1]f=1，以及 T 个整数 k_1,k_2,\cdots,k_T，存在 \mathcal O(n\log ^3n+Tn\log^2n) 的算法，可以求出 \forall 1\le i\le T,f^{[k_i]}(x)\bmod x^n。

以下是算法原理。

我们总假定在特征为 0 的域 K 上讨论。

定理 1. 对于幂级数 f，若 o(f)=1,[x^1]f=1，则存在唯一的幂级数 a，使得 o(a)=o(f-x)，且

\exp\left(a(x)\frac{\text d}{\text dx}\right)x=f(x).

这样的 a 称为 f 的复合基。

这里解释一下 \exp 里面那堆东西是什么。a(x)\frac{\text d}{\text dx} 是一个微分算子，它把 f 映射为 a(x)f'(x)，那么 (a(x)\frac{\text d}{\text dx})^2 就会把 f 映射为 a(af')'，以此类推。\exp 就是按泰勒展开式展开后逐项计算，再加起来。

例子 2. 对于 k\ge 1，\frac{x}{\sqrt[k]{1-kx^k}} 的复合基为 x^{k+1}。

性质 3. 任给 t\in K，以及幂级数 u(x)，沿用定理 1 中的记号，总有

\begin{aligned}\exp\left(t\,a(x)\frac{\text d}{\text dx}\right)x&=f^{[t]}(x),\\\exp\left(a(x)\frac{\text d}{\text dx}\right)u(x)&=u(f(x)).\end{aligned}

这个性质揭示了复合基的强大作用，它还给出了一种延拓复合次数的定义。

性质 4. 沿用定理 1 的记号，有 a(f(x))=a(x)f'(x)。

这个方程则告诉我们该如何由 a 计算出 f，如何由 f 计算出 a。

固定 f\neq x，则所有满足此方程的 a 的解构成一个一维的线性空间，记 k=o(f-x)，我们取形如 a_0=([x^k]f)x^k+\mathcal O(x^{k+1}) 的解作为此线性空间的基。则 f 的复合基恰好为 a_0。

固定 a，则此方程的解集就是 \{f_0^{[t]}:t\in K\}，其中 f_0 是一个特解。记 k=o(a)，我们取 f_0=x+([x^k]a)x^k+\mathcal O(x^{k+1})，则 f_0 的复合基恰好为 a。

引理 5. 复合基可在 \mathcal O(n\log^3n) 的时间内求出。

证明. 见《一些幂级数复合方程的解法》。

引理 6. 给定复合基 a，它对应的 f 可在 \mathcal O(n\log^2n) 的时间内求出。

证明. 此时性质 4 的方程是个微分方程，用常规手法可解。瓶颈在于多项式复合以及分治 FFT。

定理 7. 多项式复合幂可以 \mathcal O(n\log ^3n) 预处理，\mathcal O(n\log^2n) 查询。

证明. 在预处理阶段求出 f 的复合基 a，然后对于 k_i，求出复合基 k_ia 对应的 f^{[k_i]} 即可。

如果舍弃微分算子语言的话，其实我们可以将性质 4 写为以下的共轭形式。

性质 8. 若 ([x^2]f)^2=[x^3]f\neq 0，则存在幂级数 \psi 使得 o(\psi)+1=o(a)，且

\begin{cases}f=\psi^{-1}\circ \frac x{1-x}\circ \psi,\\ a=\psi^2/\psi'.\end{cases}

从这里其实可以看出复合的原理所在，即 f^{[t]}=\psi^{-1}\circ \frac x{1-tx}\circ \psi。

这个性质给出了另一种可能更简洁的做法：预处理阶段先由 f 求出 \psi，询问阶段直接计算 \psi^{-1}\circ \frac x{1-k_ix}\circ \psi。这样询问的时间复杂度不变，但预处理阶段也许能用半在线卷积优化，有没有半在线卷积大师看看怎么做。

上面展示了微分算子在多项式中的一点简单应用，但我相信微分算子的应用绝不仅于此。这里，我提出一个大问题：对于

f\left(a(x)\frac{\text d}{\text dx}\right)g(x)=h(x),

若 o(a)\ge 2,o(g)\ge 1,o(h)=1，给定 a,f,g,h 中的任意三个，如何快速求出另外一个？

一些简单的规约告诉我们，如果我们能在 g(x)=x 的前提下，由 a,h 求 f，由 a,f 求 h，就能解决求 f,g,h 中任意一个的问题。至于求 a，在 f 任意的情况下似乎是比较难的。

当 g=x,f=\exp 时，这个问题就变为复合基与原函数之间的转化问题。我认为求复合基应该是可以在 \mathcal O(n\log ^2n) 时间内完成的，但我还没想到怎么做。

另外，能否绕开由转置原理导出的多项式复合算法，单纯用微分算子理论导出多项式复合算法？