关于多项式右复合三次函数的一些思考-526互联

一个模多项式模数做 \(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 等人的帮助与启发。以及希望我没有假。

然后是一点闲话

然后是一点闲话。基本上写写这个东西的产生历程？

晚点写完。