Bostan-Mori 算法

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