Bostan-Mori 算法

WorldMachine · 2026-01-06 16:04:00 · 算法·理论

Bostan-Mori 用于提取有理分式的远端系数 [x^n]\dfrac{P(x)}{Q(x)}，其中 n 很大，\max(\deg P,\deg Q) 是常见的 m=10^5 范围。

分子分母同时乘上 Q(-x) 后，发现分母 Q(x)Q(-x) 仅余偶次项，不妨令其为 G(x^2)；将分子 P(x)Q(-x) 拆为 F_0(x^2)+xF_1(x^2)，原式化为 \dfrac{F_0(x^2)}{G(x^2)}+x\dfrac{F_1(x^2)}{G(x^2)}，分 n 的奇偶到其中一侧递归求解即可，时间复杂度为 \mathcal O(m\log m\log n)。

提取 [x^n]\ln F(x)：[x^n]\ln F(x)=[x^n]\displaystyle\int\dfrac{F'(x)}{F(x)}\text{d}x=\dfrac 1n[x^{n-1}]\dfrac{F'(x)}{F(x)}。

提取 [x^n]\displaystyle\sum_{i=1}^m\dfrac{P_i(x)}{Q_i(x)}：[x^n]\displaystyle\sum_{i=1}^m\dfrac{P_i(x)}{Q_i(x)}=[x^n]\dfrac{\sum_{i=1}^mP_i(x)\prod_{j\neq i}Q_j(x)}{\prod_{i=1}^mQ_i(x)}，分子分母都可以分治乘求出。

顺便提一嘴 \left(\displaystyle\prod_{i=1}^nF_i(x)\right)'=\displaystyle\sum_{i=1}^nF_i'(x)\displaystyle\prod_{j\neq i}F_j(x)，有时候（比如说求 \dfrac{1}{x+a_i} 之和的时候）能够少一个分治乘。

举个若智的例子，比如说求 \displaystyle\sum_{i=1}^na_i^k，k 很大，就是求 [x^k]\displaystyle\sum_{i=1}^n\dfrac{1}{1-a_ix}，用上面的方法就能做到 \mathcal O(n\log n\log k)。

这玩意的主要用途貌似还是常系数齐次线性递推。

和常系数齐次线性递推：首先提取有理分式的远端系数问题可以转为常系数齐次线性递推，设 Q(x)F(x)=P(x)，有 \displaystyle\sum_{i=0}^n[x^i]Q(x)[x^{n-i}]F(x)=[x^n]P(x)，即：

当 n>m 时 [x^n]P(x)=[x^n]Q(x)=0，此时就变成常系数齐次线性递推。

常系数齐次线性递推也可以转为上述问题：设有递推关系 f_n=\displaystyle\sum_{i=1}^ma_if_{n-i} 及初值 f_0,f_1,\cdots\!,f_{m-1}，设 f 的 OGF 为 F(x)，A(x)=\displaystyle\sum_{i=1}^ma_ix^i，F_0(x)=\displaystyle\sum_{i=0}^{m-1}f_ix^i，不难验证有：

因此有：

使用 Bostan-Mori 即可做到 \mathcal O(m\log m\log n) 求解单项，常数很小。

原来这个东西叫做 LSB-first 吗。

多次询问：直接做是 \mathcal O(qm\log m\log n) 的，考虑转成常系数齐次线性递推之后用多项式取模做法，预处理块幂，这样是 \mathcal O\left(Bm+\dfrac{nm\log m}{B}+qm\log m\right) 的，取 B=\mathcal O(\sqrt{n\log m}) 有最优复杂度 \mathcal O(m\sqrt{n\log m}+qm\log m)，或者说预处理多层块幂可以达到更好的平衡？比方说有 D+1 层，底层分块块长为 B，其它就按照 \left(\dfrac nB\right)^{1/D} 分，这样复杂度是 \mathcal O\left(Bm+D\left(\dfrac nB\right)^{1/D}m\log m+qDm\log m\right)，取 B=\mathcal O(D^{D/(D+1)}n^{1/(D+1)}\log^{D/(D+1)}m) 有最优复杂度 \mathcal O(mD^{D/(D+1)}n^{1/(D+1)}\log^{D/(D+1)}m+qDm\log m)，魔怔。

好吧 Bostan-Mori 本身也是可以多叉的？设 T=2^t，那么 \displaystyle\prod_{i=0}^{T-1}Q(\omega_T^ix) 只有次数是 T 的倍数的项系数非零，计算 \dfrac{P(x)\prod_{i=1}^{T-1}Q(\omega_T^ix)}{\prod_{i=0}^{T-1}Q(\omega_T^ix)} 的复杂度是 \mathcal O(mT\log m) 的，这样分割一次后直接跑多项式乘法逆，复杂度为 \mathcal O\left(mT\log m+\dfrac{qn\log m}{T}\right)，平衡一下复杂度是 \mathcal O(\sqrt{nmq}\log m) 的。

不过如果只算分母的话，每次从 2^{t-1} 倍增合并到 2^t，复杂度是 \mathcal O(nt\log m) 的，但是分子还是算不了。

Bostan-Mori 还可以拓展到高维情况，只需要需提取的项 [x_0^nx_1^{k_1}x_2^{k_2}\cdots x_d^{k_d}] 中 k_1,k_2,\cdots\!,k_d 较小即可，复杂度大概是 \mathcal O(m(\prod k_i)\log n(\log m+\sum\log k_i))。

还能够做一些位运算有关的魔怔东西，比方说求 \displaystyle\sum_{n'\subseteq n}[x^{n'}]\dfrac{P(x)}{Q(x)}，只需要 F_1(x)\stackrel{+}{\gets}F_0(x) 即可。

可是 [x^n]\exp{F(x)} 和 [x^n]\sqrt{F(x)} 都只能整式递推/dk/dk