根据 noshi91 的新算法，多项式复合最快可做到 \Theta(n\log ^2n)。这为我们解决一类复合方程提供了巨大的便利。例如「半复合」问题，即给定幂级数 g(x)，求解 f(x) 使得 f\circ f=g。本文将给出半复合问题的 \Theta(n\log ^3n) 解法。不过在此之前，我们需要先解决一类与之相关的复合方程。
求解 A(x)F(x)+B(x)F(G(x))=P(x)
给定幂级数 A,B,G,P，求解幂级数 F 使得 A\cdot F+B\cdot F(G)\equiv P\pmod {x^n}。
为了保证解的存在性和唯一性，我们假设 A(0)=B(0)=1，并且 [x^0]G=0,[x^1]G=1。
至于 P，它的最低项次数是多少并不是本质的。因为我们有如下引理：
引理：若 x^m||P，记 f_* 为方程 A f_* + (G/x)^mBf_* (G)\equiv P/x^m\pmod {x^{n-m}} 的解。则原方程的解为 x^m f_ * (x)。
证明略。
注意到 B 可逆，我们可以在方程两边乘上 B^{-1}。这样我们只需求解以下方程：
A(x)F(x)+F(G(x))\equiv P(x)\pmod {x^{2n}}\tag{1}
我们考虑分治，分别求解 F 的高次项和低次项。在模 x^{2n} 意义下，我们设 F=f_0+x^nf_1，只需求 f_0,f_1。
$$A(x)f_0(x)+f_0(G(x))\equiv P(x)\pmod {x^n}\tag{2}$$
递归即可。我们看看 $f_1$ 怎么求。
将 $F=f_0+x^nf_1$ 代入 $(1)$ 式，整理得：
$$x^n[Af_1+(G/x)^nf_1(G)]\equiv P-Af_0-f_0(G)\pmod {x^{2n}}$$
由 $(2)$ 式知，$x^n$ 整除 $P-Af_0-f_0(G)$，记 $Q=[P-Af_0-f_0(G)]/x^n$，则：
$$Af_1+(G/x)^nf_1(G)\equiv Q\pmod {x^n}$$
同样可以递归处理。
递归到 $n=1$ 处，在 $(1)$ 式两边取常数项可得：
$$2F(0)=P(0)$$
返回 $\frac 12P(0)$ 即可。
时间复杂度 $T(n)$ 满足：
$$T(n)=2T(n/2)+\Theta(n\log ^2n)$$
单步瓶颈是多项式复合。故该方程可以在 $\Theta(n\log ^3n)$ 时间内求解。
## 求解 $F(F(x))=G(x)
我们只考虑 [x^0]G=0,[x^1]G=1 时的情况。
考虑倍增，初值显然可设置为 x。假设我们已知模 x^n 意义下的解，试求以下方程的解：
F(F(x))\equiv G(x)\pmod {x^{2n}}\tag{3}
记 f_0 为如下方程的解：
f_0(f_0(x))\equiv G(x)\pmod {x^n}\tag{4}
设 F=f_0+x^n f，那么有：
f_0(f_0+x^nf)+(f_0+x^nf)^n \cdot f(f_0+x^nf)\equiv G(x)\pmod {x^{2n}}
（注意区分复合和乘法的符号）
为了简化这个方程，我们有如下引理：
f_0(f_0+x^nf)\equiv f_0(f_0)+f_0'(f_0)x^nf\pmod {x^{2n}}
f(f_0+x^nf)\equiv f(f_0)\pmod {x^{n}}
(f_0+x^nf)^n\equiv x^n[(f_0/x)^n+nf_0^{n-1}f]\pmod {x^{2n}}
前两条用泰勒展开证明即可。第三条需注意 x|f_0，然后用二项式定理即可。
代入前式可知：
f_0(f_0)+f_0'(f_0)x^nf+x^n[(f_0/x)^n+nf_0^{n-1}f]f(f_0)\equiv G(x)\pmod {x^{2n}}
由 (4) 式知，x^n 整除 G-f_0(f_0)。故设 Q=[G-f_0(f_0)]/x^n，则：
f_0'(f_0)f+[(f_0/x)^n+nf_0^{n-1}f]f(f_0)\equiv Q(x)\pmod {x^{n}}\tag{5}
在上式两端取常数项可知：
f(0)+(1+0)f(0)= Q(0)
故 f(0)=\frac 12 Q(0)，因为：
nf_0^{n-1}f\cdot f(f_0)\equiv nf(0)x^{n-1}f(f_0)\pmod{x^n}
代入 (5) 式可得：
f_0'(f_0)f+[(f_0/x)^n+nf(0)x^{n-1}]f(f_0)\equiv Q(x)\pmod {x^{n}}
可以发现 f 符合我们先前讨论过的方程的形式，可以 \Theta(n\log ^3n) 求得。
时间复杂度 T(n) 满足：
T(n)=T(n/2)+\Theta(n\log ^3n)
故半复合问题可以在 \Theta(n\log ^3n) 时间内求解。