任意二次分式均可于 nlogn 时间复合
飞雨烟雁
·
·
算法·理论
本文最后更新于 2024 - 03 - 17。
云剪切板链接：https://www.luogu.com.cn/paste/7ahgr029。
零 · 引入
本文将介绍一种本人于五月底发现的算法（不清楚之前有没有被发现），可以在 \Theta(n\log n) 时间内右复合任意二次分式。具体问题为：
给定 n 次多项式 F(x) 及二次分式 \frac{ax^2+bx+c}{dx^2+ex+f}，试求 F(\frac{ax^2+bx+c}{dx^2+ex+f}) 的前 n 次项。
传统的分治做法可以在 \Theta(n\log ^2n) 时间内解决。这事实上可以算是比较理想的做法了，但是利用一些技巧我们还可以加速至 \Theta(n\log n)，且无需分治，只需要简单的多项式系数平移操作。
一 · 复合「二次函数」
这是后面所有复合的基础，我们可通过四步来复合任意二次函数 ax^2+bx+c：
| 步骤 |
操作 |
说明 |
由上一步变为 |
| 1 |
右复合 x+\gamma |
多项式平移 +\gamma |
F(x)\rightarrow F(x+\gamma) |
| 2 |
右复合 \alpha x |
k 次系数乘上 \alpha^k |
F(\alpha x+\gamma) |
| 3 |
右复合 x^2 |
k 次系数移动至 2k 次 |
F(\alpha x^2+\gamma) |
| 4 |
右复合 x+\beta |
多项式平移 +\beta |
F(\alpha x^2+2\alpha\beta x+\alpha\beta^2+\gamma) |
最后再解个方程：\begin{cases}a=\alpha\\b=2\alpha\beta\\c=\alpha\beta^2+\gamma\end{cases}\implies\begin{cases}\alpha=a\\\beta=\frac b{2a}\\\gamma=c-\frac {b^2}{4a}\end{cases}
这样我们就可以在 \Theta(n\log n) 时间内右复合二次函数了。
二 · 复合「常数除二次」
即复合 \frac{c}{dx^2+ex+f}，是 a=b=0 的特殊情况，且保证 c,d,f\neq 0。以下不妨设 c=1。
这里要用到一条极其关键的式子：
\displaystyle F_R(x)=x^{|F|}F\left(\frac 1x\right)
其中 F_R(x) 表示将 F(x) 系数翻转过后的多项式，|F| 是多项式 F(x) 的次数。通过这条式子我们可以得到：
\displaystyle\dfrac{F_R(dx^2+ex+f)}{(dx^2+ex+f)^n}=F\left(\frac 1{dx^2+ex+f}\right)
这样就可以把常数除二次转成复合二次函数了！于是我们通过以下步骤去复合常数除二次：
| 步骤 |
操作 |
说明 |
由上一步变为 |
| 1 |
翻转系数 |
k 次系数移动至 n-k 次 |
F(x)\rightarrow F_R(x) |
| 2\sim 5 |
右复合 dx^2+ex+f |
按照第一小节的方法 |
F_R(dx^2+ex+f) |
| 6 |
乘上 (dx^2+ex+f)^{-n} |
卷就对了！ |
\frac{F_R(dx^2+ex+f)}{(dx^2+ex+f)^n}\\=F(\frac 1{dx^2+ex+f}) |
第 6 步无需求逆，可以线性递推其系数。注意到：
\begin{aligned}G(x)&=(dx^2+ex+f)^{-n}\\\ln G(x)&=-n\ln(dx^2+ex+f)\\\frac{G'(x)}{G(x)}&=\dfrac{-2ndx-ne}{dx^2+ex+f}\\(dx^2+ex+f)G'(x)&=(-2ndx-ne)G(x)\\\end{aligned}
两边各自提取 k 次项系数整理成递推式就好了。
三 · 复合「分子或分母为完全平方式的分式」
以下以分子为完全平方式为例，分母是平方式的做法与其类似（甚至更简单）。假设我们要复合 \frac{(x+b)^2}{dx^2+ex+f}，相当于将下面这个东西平移 +b：
\displaystyle\dfrac{x^2}{dx^2+(e- 2db)x+(f-be+db^2)}
记 e'=e-2db,f'=f-be+db^2，上式相当于复合 \frac {x^2}{dx^2+e'x+f'}，再用那条翻转公式：
\displaystyle F_R\left(\dfrac{f'}{x^2}+\frac {e'}{x}+d\right)\left(\frac {x^2}{dx^2+e'x+f'}\right)^n=F\left(\frac {x^2}{dx^2+e'x+f'}\right)
记 G(x)=F_R(f'x^2+e'x+d),|G|=2n，故技重施：
\displaystyle G_R(x)=x^{2n}G\left(\frac 1x\right)=x^{2n}F_R\left(\dfrac{f'}{x^2}+\frac {e'}{x}+d\right)
也就是说：F(\frac {x^2}{dx^2+e'x+f'})={G_R(x)}\times {(dx^2+e'x+f')^{-n}}。整理一下步骤：
| 步骤 |
操作 |
说明 |
由上一步变为 |
| 1 |
翻转系数 |
k 次系数移动至 n-k 次 |
F(x)\rightarrow F_R(x) |
| 2\sim 5 |
右复合 f'x^2+e'x+d |
按照第一小节的方法 |
F_R(f'x^2+e'x+d)=G(x) |
| 6 |
翻转系数 |
k 次系数移动至 2n-k 次 |
G_R(x) |
| 7 |
右复合 x+b |
多项式平移 +b |
F\Big(\frac{(x+b)^2}{dx^2+ex+f}\Big)\times (dx^2+ex+f)^{n} |
| 8 |
乘上 (dx^2+ex+f)^{-n} |
卷！可以线性递推 |
F(\frac{(x+b)^2}{dx^2+ex+f}) |
欸？这里为什么不先卷积再平移呢？因为复合 \frac{x^2}{dx^2+ex+f} 原本应该得到一个无穷项的多项式，但是先卷积会导致更高次项的系数被扔了。此时再平移，就没法考虑到更高次项平移对低次项的影响，导致结果错误。因此应当先平移后卷积。
四 · 复合「一般二次分式」
注：这里的一般二次分式是排除了上面几种特殊情况后的二次分式，记为 \frac{ax^2+bx+c}{dx^2+ex+f}。
若 ae=bd，先平移 +\frac ad 再按上文去右复合 \frac{c-af/d}{dx^2+ex+f} 即可。以下设：ae\neq bd。
考虑消去分子的一次项和常数项，有如下分式：
\displaystyle \dfrac{a(x+\lambda)^2+b(x+\lambda)+c}{d(x+\lambda)^2+e(x+\lambda)+f}
令分子分母一次系数及常数项比值相同：\frac{2a\lambda+b}{a\lambda^2+b\lambda+c}=\frac{2d\lambda+e}{d\lambda^2+e\lambda+f}，整理有：
\displaystyle (ae-bd)\lambda^2+2(af-cd)\lambda+(bf-ce)=0
任取一根 \lambda（若无解则需扩域），并记：\mu=\frac{2a\lambda+b}{2d\lambda+e}。可以证明，\mu 值存在且非 0。
则 F\Big(\dfrac{ax^2+bx+c}{dx^2+ex+f}\Big) 相当于将 F\Big(\mu+\dfrac{(a-\mu d)x^2}{d(x+\lambda)^2+e(x+\lambda)+f}\Big) 平移 -\lambda，那么步骤很显然就出来了。
但是直接套用第三小节的方法是不行的，原因和第三小节最后一段话类似。所以要稍做修改，具体看下面的步骤表：
| 步骤 |
操作 |
说明 |
| 1 |
右复合 x+\mu |
多项式平移 +\mu |
| 2 |
翻转系数 |
k 次系数移动至 n-k 次 |
| 3\sim 6 |
右复合 \frac{d(1+\lambda x)^2+ex(1+\lambda x)+fx^2}{a-\mu d} |
按照第一小节的方法 |
| 7 |
翻转系数 |
k 次系数移动至 2n-k 次 |
| 8 |
右复合 x-\lambda |
多项式平移 -\lambda |
| 9 |
乘上 (\frac{dx^2+ex+f}{a-\mu d})^{-n} |
想保留前几项就保留前几项 |
五 · 简单的实战
以此题为例 P8561 送别（Farewell），此题最后要求我们复合 x+x^{-1}-2，也就是复合 \frac {(x-1)^2}{x}。这是一个分子为完全平方式的实例，让我们使用成套的方法解决：
此题中：b=-1,d=0,e=1,f=0。
计算得：e'=1,f'=1，需要复合二次函数 x^2+x。
计算得：\alpha=1,\beta=\frac 12,\gamma=-\frac 14，那么我们就可以写出如下步骤啦：
| 步骤 |
操作 |
说明 |
由上一步变为 |
| 1 |
翻转系数 |
k 次系数移动至 n-k 次 |
F(x)\rightarrow F_R(x) |
| 2 |
右复合 x-\frac 14 |
多项式平移 -\frac 14 |
F_R(x-\frac 14) |
| 3 |
右复合 x^2 |
k 次系数移动至 2k 次 |
F_R(x^2-\frac 14) |
| 4 |
右复合 x+\frac 12 |
多项式平移 +\frac 12 |
F_R(x^2+x) |
| 5 |
翻转系数 |
k 次系数移动至 2n-k 次 |
x^{2n}F_R\left(\frac 1{x^2}+\frac 1x\right)\\=(x+1)^{n}F\left(\frac{x^2}{x+1}\right) |
| 6 |
右复合 x-1 |
多项式平移 -1 |
x^nF\left(\frac {(x-1)^2}{x}\right) |
仅用了三次多项式平移就完成，效率上显著快于分治！同时也将此题最优时间复杂度降至 \Theta(k\log k+\log n)。
此处给一道复杂点的复合：\dfrac{x}{1+x+\frac 12x^2}，来自 P7857 「EZEC-9」Meltel，解法可参考 Meltel 复合计算笔记。但此题有别的 \Theta(n\log n) 解法，原因是 F(x) 有特殊性质。
六 · 推论及其他问题
综上，我们可以得到：任意二次分式的右复合均可在不多于 4 次多项式平移时间内完成。
此外，与二次分式相关的复合也可以在优于暴力的时间内完成，例如（双曲）三角函数。而当 F(G) 有高效的复合方法时，翻转公式本身也可以用于复合 F(\frac 1G)。
目前看来，如果仍用翻转这种操作，无论在第四部分进行怎样的变形，扩域都是无法避免的。
至于超脱于二次分式以外的复合问题，例如复合 ax^3+bx^2+cx+d, e^x+x,xe^x,\ln(1+x) 等等，我就不知道怎么办了。（三次函数复合见文末）
七 · 后记
一开始我是在搞 Meltel 这道题时想到要去找一种复合任意二次分式的算法，当初想的是只要比 \Theta(n^2) 快就算成功，就冥思苦想出个分治，然后就走人了。那时候也有往这块想，但是没注意到翻转公式这个关键的东西，所以没搞出来。
后来有天尝试复合 \frac 1{1-x}，突然从脑子里蹦出了翻转公式，就顺利搞出了复合 \frac 1{1-x} 的 \Theta(n\log n)。那时想乘胜追击，扩展到二次分式，又失败了。
直到后面想冲击一下 Farewell 这题的 \Theta(n\log n) 解法，没想到当天下午真被我搞出来了。隔天顺势把任意二次分式的算法整出来了，也就是上面那些东西。不过后来，实操时又发现有小 BUG，就是先卷积还是先平移的问题，很快就修复了。算法也就此成型。
话说我去网上搜都没找到这方面的算法，顶多分治，那么我就是第一个解决这个问题的人辣！也有可能这玩意价值不大，没人往这块想。 看来前人已经探索过这类问题了，只不过没那么广为人知而已。
23.9.19 upd：
看了 EI 的 这篇注记，终于明白怎么复合三次函数了。简单来讲，先将任意三次函数的复合归约到 x^3-3x 上，再利用 x^3-3x=(x^3-x^{-3})\circ(x+x^{-1})^{\langle-1\rangle} 进行转化。前者只需利用 (x-1/x)\circ x^3，可以做到 \Theta(n\log n)；后者则需注意到这步关键：
\displaystyle \Big(\dfrac{x+x^{-1}}2\Big)=\Big(\frac{x+1}{x-1}\Big)\circ x^2\circ\Big(\frac{x+1}{x-1}\Big)
那么复合的逆就是各部分求逆后倒序复合：
\displaystyle \Big(\dfrac{x+x^{-1}}2\Big)^{\langle-1\rangle}=\Big(\frac{x+1}{x-1}\Big)\circ \sqrt x\circ\Big(\frac{x+1}{x-1}\Big)
然后就可以 \Theta(n\log n) 做了！这个复合的逆的想法可以说是十分巧妙！
24.3.17 upd：
这是否太日新月异了？（多项式复合（逆）的 O(nlog^2n) 做法）
9 个月前 esquigybcu 的评论“加油，争取在 polylog 内解决模任意多项式复合”居然成为了现实。那时候的我是无论如何都不敢想象的。
以我自己的理解，这里转述一下做法。
[x^k]F(G(x))=\sum_{}f_i[x^k]G^i
其转置问题为：
a_k=\sum_{}f_i[x^i]G^k
设 F_r(x)=\sum_{}f_{n-i}x^i，即求：
a_k=\sum_{}[x^{n-i}]F_r[x^i]G^k=[x^n]F_rG^k
故有：
\sum a_ky^k=[x^n]\dfrac {F_r}{1-yG}
对此应用 Bostan-Mori 算法，即：
[x^n]\dfrac{P(x,y)}{Q(x,y)}=[x^n]\dfrac{P(x,y)Q(-x,y)}{Q(x,y)Q(-x,y)}=[x^n]\dfrac{P_0(x^2,y)+xP_1(x^2,y)}{R(x^2,y)}
于是可以递归到：
[x^n]\dfrac{P(x,y)}{Q(x,y)}=[x^{[n/2]}]\dfrac{P_{n\bmod 2}(x,y)}{R(x,y)}
注意到第 t 层的递归中 x,y 的次数约是 n/2^t,2^t 的，所以 P,Q 的项数约是 n 项，这保证了次数不会膨胀。
一共递归了 \log n 层，故总时间复杂度为 \Theta(n\log ^2n)。
一开始面对复合问题时，我更倾向于建立 EGF，即：
\sum_{}\dfrac{a_k}{k!}y^k=[x^n]F_r\exp(yG)
因为我认为 \exp 的性质要远优于 \frac 1{1-x}。现今看来，在 Bostan-Mori 算法的加持之下，\frac 1{1-x} 的可操作性极强，反而在这个问题上发挥了重要作用。