新时代线性递推算法

无摘要

求一个满足 $k$ 阶齐次线性递推数列 $\{f_{i}\}$ 的第 $n$ 项，即：
$$
f_n=\sum\limits_{i=1}^k a_i \times f_{n-i}
$$
我们知道线性递推是能表示为有理生成函数的，即 $F(x)=\dfrac{P(x)}{Q(x)}$ 的形式。具体操作可以考虑给 $F(x)$ 乘上 $A(x)$ 观察其系数变化，这里不再赘述。

现在所求即为 $[x^n]\dfrac{P(x)}{Q(x)}$，$\dfrac{P(x)}{Q(x)}=\dfrac{P(x)Q(-x)}{Q(x)Q(-x)}$。注意到 $Q(x)Q(-x)$ 是一个偶函数，因此其只有偶数次位置有值，可以表示为 $\lambda(x^2)$。然后将 $P(x)Q(-x) \bmod x^k$ 写成 $\alpha(x^2)+x\beta(x^2)$，这里分别对应偶数次位置和奇数次位置，所以就可以将 $n$ 分成两半递归了。

这便是 Bostan-Mori 算法。

int bostan_mori(vi p, vi q, int n, int K) {
  if (n < K) return p[n];
  q[0] = 1;
  for (int i = 1; i <= K; ++i) q[i] = sub(0, q[i]);
  p = p * q; p.resize(K);
  for (; n; n >>= 1) {
    static vi r;
    r = q;
    for (int i = 1; i <= K; i += 2) r[i] = sub(0, r[i]);
    p = p * r; q = q * r;
    for (int i = 0; i < K; ++i) p[i] = p[(i << 1) | (n & 1)];
    for (int i = 0; i <= K; ++i) q[i] = q[i << 1];
    p.resize(K);
    q.resize(K + 1);
  }
  return 1ll * p[0] * Inv(q[0]) % MOD;
}