首先根据熟知的变换, 复合 \(f(ax^3+bx^2+cx+d)\) 的问题的困难内核在于 \(f(x^3+cx)\), 在域上, 只要解决某个 \(c\neq 0\) 的情况, 就解决了一般的情况.
取 \(c = -3\), 我们有
\[x^3 - 3x = (x^3 + x^{-3}) \circ (x + x^{-1})^{\langle-1\rangle}.
\]
于是问题的难点转换成了计算复合 \(f(x+x^{-1})\), 由于
\[f\left(\frac{x+x^{-1}}2\right) = f\left( \frac{x+1}{x-1} \right) \circ x^2
\circ \frac{x+1}{x-1}, \]
整个问题可以在 \(O(n\log n)\) 时间内解决.
之前本来想要出题, 但是做过一些实验发现有几十倍的常数, 很难击败 \(O(n\log^2 n)\) 做法.
由于某些原因, 今天公开一下上面的注记.