一个模多项式模数做 \(f(ax^3 + bx^2 + cx + d)\) 的可能好实现一些的方法。感觉就是把 EI 老师的某博客展开写了。
理性愉悦。确实常数不是很小，至少我这个做法是这样的。
首先处理一下，把任意的三次函数转化成特殊三次函数。可以拆成 \((x + d)\circ ax\circ F\)，其中 \(F = x^3 + px^2 + qx\)。然后消掉二次项，也就是
\[x^3 + px^2 + qx = \left(x + \frac{2p^3}{27} - \frac{pq}3\right) \circ \left(x^3 + \left(q - \frac {p^2}3\right) x\right) \circ \left( x + \frac p3\right) \]虽然看着比较唬人，但这其实就是正常解三次函数时的换元。我好像不太熟知这个（
于是问题就被转化为了多项式复合 \(x^3 + cx\)。我们可以首先对某个特定的 \(c_0\) 解决，随后取 \(a\) 使得
\[x^3 + cx = \frac{x}{a^3} \circ (x^3 + c_0x) \circ ax \]即可。发现最后 \(a\) 需要开根求解，如果 \(a\) 不在当前域内需要扩域。扩域不会改变单位根的存在性，我们仍然可以加速 DFT。取 \(c_0 = -3\)。
EI 老师给出了一个构造，我们有
\[x^3 - 3x = \left(x + \frac 1x\right) \circ x^3 \left(x + \frac 1x\right)^{\langle -1 \rangle} \]可以快速验证 \(x^3 - 3x\circ (x + x^{-1}) = (x + x^{-1}) \circ x^3\)。如果我们可以把 \(x + x^{-1}\) 拆成几个易于求复合逆和易于求解的函数，我们就可以快速解决原问题。由于
\[x + \frac 1x = 2x\circ \frac{x + 1}{x - 1} \circ x^2 \circ \frac{x + 1}{x - 1} \]而 \(\dfrac{x + 1}{x - 1}\) 的复合逆就是其本身，\(x^2\) 的复合逆就是 \(\sqrt x\)。
一眼看上去，目前的难点来到了复合 \(\dfrac{x + 1}{x - 1}\) 而不展开到形式幂级数域上去，这是由于我们很难在某个位置截断。可以考虑拆开这个式子得到
\[\dfrac{x + 1}{x - 1} = (2x + 1) \circ x^{-1} \circ (x - 1) \]核心在于如何适当地复合 \(x^{-1}\)，但最终不得到形式幂级数或形式洛朗级数。
考虑得到有理分式。我们考察有理分式 \(F(x) = \dfrac{P(x)}{Q(x)}\)，其中 \(\text{deg}(P) = n, \text{deg}(Q) = m\)。\(F\circ (ax + b)\) 以及 \(F\circ x^k\) 都与正常多项式的复合相同。
考虑复合 \(x^{-1}\)。定义 \(\text r(F(x))\) 是将多项式 \(F(x)\) 的系数翻转后得到的多项式，我们知道
\[F(x^{-1}) = \frac{P(x^{-1})}{Q(x^{-1})} = \frac{\text rP(x)}{x^{n - m}\text rQ(x)} \]这个形式并未出有理分式域。
这样我们似乎就已经完成了所有内容。但整体写出 \(x^3 - 3x\) 的形式，我们会发现存在复合 \(\sqrt{x}\) 后再复合 \(2x + 1\) 的情况，而这很难直观看出最终分子分母都不会得到形式幂级数。可能有人会认为这时需要手动维护奇数项，但感性地我们可以认为之前复合完 \(x^2\) 后这里已经不存在偶数项了。但为了严谨，我们还是在纸上做一下复合吧。由于分母一直是简单多项式，我们预料这一过程不会很繁杂。
首先考虑 \(F(x) \circ x^{-1}\)。我们知道 \(F(x^{-1}) = \dfrac{\text rF(x)}{x^n}\)。
然后考虑 \(F(x) \circ \dfrac{x + 1}{x - 1}\)。我们知道
\[\begin{aligned} & F(x) \circ \frac{x + 1}{x - 1} \\ = & \ F(2x + 1) \circ x^{-1} \circ (x - 1) \\ = & \ \frac{\text r(F(2x + 1))}{x^n} \circ (x - 1) \\ = & \ \frac{\text r(F(2x + 1))\circ (x - 1)}{(x - 1)^n} \end{aligned}\]为下文简写，定义 \(R(F(x)) = \text r(F(2x + 1))\circ (x - 1)\)。
最后是原问题。我们知道
\[x^3 - 3x = 2x\circ \frac{x + 1}{x - 1} \circ x^2 \circ \frac{x + 1}{x - 1} \circ x^3 \circ \frac{x + 1}{x - 1} \circ \sqrt x \circ \frac{x + 1}{x - 1} \circ \frac x2 \]其关键在于中间七个部件的复合。为方便书写及模块化，我们定义 \(F_i(x) = \dfrac{P_i(x)}{Q_i(x)}\) 为进行完第 \(i\) 个部件后的多项式，并定义 \(F_0(x) = f(x), \text{deg}(f) = n\)。
\(1.\ F_0\circ \dfrac{x + 1}{x - 1}\)
可以知道
\[\begin{aligned} F_1(x) = F_0(x) \circ \frac{x + 1}{x - 1} = \frac{R(F_0(x))}{(x - 1)^n} \end{aligned}\]即 \(P_1(x) = R(F_0(x))\)，\(Q_1(x) = (x - 1)^n\)。
\(2.\ F_1\circ x^2\)
可以知道 \(P_2(x) = P_1(x) \circ x^2 = \text r(F(2x + 1))\circ (x^2 - 1)\)，\(Q_2(x) = (x^2 - 1)^n\)。
目前我们能发现，\(P_2\) 的确只有偶次项。
\(3.\ F_2\circ \dfrac{x + 1}{x - 1}\)
\[P_2(x) \circ \dfrac{x + 1}{x - 1} = \frac{R(P_2(x))}{(x - 1)^{2n}} \]\[Q_2(x) \circ \dfrac{x + 1}{x - 1} = \frac{(4x)^n}{(x - 1)^{2n}} \]化简可以知道
\[F_3(x) = \frac{R(P_2(x))}{(4x)^n} \]即 \(P_3(x) = R(P_2(x))\)，\(Q_3(x) = (4x)^n\)。此时 \(P_3\) 也只有偶次项。
\(4.\ F_3\circ x^3\)
可以知道 \(P_4(x) = P_3(x) \circ x^3 = \text r(P_2(2x + 1))\circ (x^3 - 1)\)，\(Q_4(x) = (4x^3)^n\)。
\(5.\ F_4\circ \dfrac{x + 1}{x - 1}\)
\[P_4(x) \circ \dfrac{x + 1}{x - 1} = \frac{R(P_4(x))}{(x - 1)^{6n}} \]\[Q_4(x) \circ \dfrac{x + 1}{x - 1} = 4^n\frac{(x + 1)^{3n}}{(x - 1)^{3n}} \]化简可以知道
\[F_5(x) = \frac{R(P_4(x))}{4^n(x - 1)^{3n}(x + 1)^{3n}} \]我们惊喜地发现，\(P_5\) 只有 \(6k\) 次项，\(Q_5 = 4^n(x^2 - 1)^{3n}\) 只有偶次项。这也就证明了我们上面感性的想法，即可以直接复合 \(\sqrt x\)，当前根本没有奇次项。
\(6.\ F_5\circ \sqrt x\)
可以知道 \(P_6(x) = P_5(x) \circ \sqrt x\)，\(Q_6(x) = 4^n(x - 1)^{3n}\)。
\(7.\ F_6\circ \dfrac{x + 1}{x - 1}\)
\[P_6(x) \circ \dfrac{x + 1}{x - 1} = \frac{R(P_6(x))}{(x - 1)^{3n}} \]\[Q_6(x) \circ \dfrac{x + 1}{x - 1} = 4^n\left(\frac{2}{x - 1}\right)^{3n} \]化简可以知道
\[F_7(x) = \frac{R(P_6(x))}{2^{5n}} \]到这里就完成了核心部分。
可以发现，最后我们并未保有有理分式的形式，而是回到了多项式域内。这也暗示着我们的方法的正确性。最后写出分子的形式：
\[\begin{aligned} & R(P_6(x)) \\ = & \ R( P_5(x) \circ \sqrt x) \\ = & \ R( R(P_4(x))\circ \sqrt x) \\ = & \ R( R( P_3(x) \circ x^3 )\circ \sqrt x) \\ = & \ R( R( R( P_2(x) ) \circ x^3 )\circ \sqrt x) \\ = & \ R( R( R( P_1(x) \circ x^2 ) \circ x^3 )\circ \sqrt x) \\ = & \ R( R( R( R(f(x)) \circ x^2 ) \circ x^3 )\circ \sqrt x) \end{aligned}\]该部分需要进行 \(8\) 次多项式点值平移，其中分别对度为 \(n, 2n, 3n, 6n\) 的多项式做了两次点值平移。
最终我们得到了一种易于实现(?)的 \(O(n\log n)\) 复杂度做法。可能常数会很大很大。
感谢 EntropyIncreaser，xiaoziyao，APJifengc，SoyTony，Jijidawang 等人的帮助与启发。以及希望我没有假。
然后是一点闲话
然后是一点闲话。基本上写写这个东西的产生历程？
晚点写完。