Bostan-Mori 算法 学习笔记

发布于

线性递推

我们说明,如果一个生成函数 $\frac{P\left(x\right)}{Q\left(x\right)}$,满足 $\deg\left(P\left(x\right)\right) < \deg\left(Q\left(x\right)\right)$,那么,该封闭形式所对应的原函数 $A\left(x\right)$ 是一个 $\deg\left(Q\left(x\right)\right)$ 阶递推。

为了方便描述,令 $d = \deg\left(Q\left(x\right)\right)$。

由于定义,对于 $i \geq d$ 有 $a_i = \sum\limits_{j = 1}^dc_ja_{i - j}$。

构造 $Q\left(x\right) = 1 - \sum\limits_{i = 1}^dc_ix^i$,设 $P\left(x\right) = Q\left(x\right)A\left(x\right)$,那对于 $i \geq d$ 我们有

$$p_i = \sum\limits_{j = 0}^dq_ja_{i - j} = a_i - \sum\limits_{j = 1}^dc_ja_{i - j} = 0$$

因此 $\deg\left(P\left(x\right)\right) \leq d - 1$。由于 $q_0 = 1$,$Q\left(x\right)$ 有逆 $Q^{-1}\left(x\right)$,对 $P\left(x\right) = Q\left(x\right)A\left(x\right)$ 两边同时乘上 $Q^{-1}\left(x\right)$,得到 $\frac{P\left(x\right)}{Q\left(x\right)} = A\left(x\right)$


同样的,在 $\frac{P\left(x\right)}{Q\left(x\right)} = A\left(x\right)$ 两边乘上 $Q\left(x\right)$,得到 $A\left(x\right)Q\left(x\right) = P\left(x\right)$,考虑 $i \geq d$ 的 $p_i$:

$$p_i = 0 = a_i - \sum\limits_{j = 1}^dc_ja_{i - j} = \sum\limits_{j = 0}^dc_ja_{i - j}$$

因此 $\left(a_n\right)_{n \geq 0}$ 是 $d$ 阶线性递推。

Bostan-Mori

假设我们要求 $a_k$。

若 $k = 0$,由于 $P\left(x\right) = A\left(x\right)Q\left(x\right)$,所以 $p_0 = a_0q_0 = a_0 = P\left(0\right)$。

对于 $k \geq 1$:
把生成函数变成 $\frac{P\left(x\right)Q\left(-x\right)}{Q\left(x\right)Q\left(-x\right)}$ 的形式。

考虑 $\left[x^t\right]Q\left(x\right)Q\left(-x\right) = \sum\limits_{i + j = t, j is even}q_iq_j + \sum\limits_{i + j = t, j is odd}q_i\left(-q_j\right) = 0$,于是我们只需要考虑它的偶数次项,存在 $V\left(x^2\right) = Q\left(x\right)Q\left(-x\right)$。

我们设 $U\left(x\right) = P\left(x\right)Q\left(-x\right)$,现在我们把 $U\left(x\right)$ 分成两个多项式,一个只有奇数次项,一个只有偶数次项:

$$U_e\left(x\right) = \sum\limits_{i = 0}^{d - 1}u_{2i}x^i$$

$$U_o\left(x\right) = \sum\limits_{i = 0}^{d - 1}u_{2i + 1}x^i$$

$$U\left(x\right) = U_e\left(x^2\right) + xU_o\left(x^2\right)$$

$x^k$ 项系数只会由 $U_e\left(x^2\right)$ 或 $U_o\left(x^2\right)$ 贡献而来。于是

$$ \left[x^k\right]\frac{U\left(x^2\right)}{V\left(x^2\right)} = \begin{cases} \left[x^k\right]\frac{U_e\left(x\right)}{V\left(x^2\right)} & k\text{ is even} \\ \left[x^k\right]\frac{U_o\left(x^2\right)}{V\left(x^2\right)} & k\text{ is odd} \end{cases} = \begin{cases} \left[x^{k / 2}\right]\frac{U_e\left(x\right)}{V\left(x\right)} & k\text{ is even} \\ \left[x^{(k - 1) / 2}\right]\frac{U_o\left(x\right)}{V\left(x\right)} & k\text{ is odd} \end{cases} $$

若使用 FFT 处理多项式乘法,则计算量为 $O\left(d \log d \log k\right)$。

代码

lib::mint Bostan_Mori(lib::poly P, lib::poly Q, tp k) {
   while (k != 0) {
      auto nQ = Q;
      for (tp i = 1; i < Q.size(); i += 2) nQ[i] = -nQ[i];
      auto U = P * nQ;
      P.clear();
      for (tp i = k % 2; i < U.size(); i += 2) P.push_back(U[i]);
      auto sQ = Q * nQ;
      Q.clear();
      for (tp i = 0; i < sQ.size(); i += 2) Q.push_back(sQ[i]);
      k >>= 1;
   }
   return P[0] / Q[0];
}

仅有一条评论

  1. hhhqx · 2025-02-04 18:25

    %%%

发表评论