常系数齐次线性递推小记

常系数齐次线性递推

对于 \(n \geq k\)，\(\sum_{i=0}^kq_ia_{n-i}=0\)，其中 \(q_0 \neq 0\)。

数列 \(a_n\) 的生成函数为 \(A(x)\)。

上式左边看作卷积，右边看作生成函数 \(P(x)\) 的 \(n \geq k\) 时的系数。

\[ Q(x)A(x) = P(x) \] \[ A(x) = \frac{P(x)}{Q(x)} \]

\(P(x)\) 为 \(k-1\) 次多项式，\(Q(x)\) 为 \(k\) 次多项式。

然后就是解决 \([x^n]\dfrac{P(x)}{Q(x)}\) 的问题。

使用 EI 提到的方法，考虑 \[ \frac{P(x)}{Q(x)} = \frac{P(x)Q(-x)}{Q(x)Q(-x)} \] 由于 \(Q(x)Q(-x) = Q(-x)Q(x)\)，所以它只有偶次项有值，设 \(U(x^2) = Q(x)Q(-x)\)， \[ \frac{P(x)}{Q(x)} = \frac{E(x^2)}{U(x^2)}+x\frac{O(x^2)}{U(x^2)} \] 只需要递归到一侧即可。

朴素实现只需要写多项式乘法，优化的实现已经在多项式板子里。

int divAt(Poly p, Poly q, LL n) {
  for (; n; n >>= 1) {
    Poly r(q);
    for (int i = 1; i < r.size(); i += 2) r[i] = P - r[i];
    Poly u = p * r, v = q * r;
    p.clear();
    for (int i = n & 1; i < u.size(); i += 2) p.push_back(u[i]);
    for (int i = 0; i < q.size(); i++) q[i] = v[i * 2];
  }
  return 1LL * p[0] * fpow(q[0]) % P;
}

Berlekamp Massey 算法

懒得学，直接拖 tourist 的板子。

template <typename T>
std::vector<T> bm(std::vector<T> a) {
  std::vector<T> p = {1}, q = {1};
  int l = 0;
  for (int r = 1; r <= (int) a.size(); r++) {
    T delta = 0;
    for (int j = 0; j <= l; j++) {
      delta += a[r - 1 - j] * p[j];
    }
    q.insert(q.begin(), 0);
    if (delta != 0) {
      vector<T> t = p;
      if (q.size() > t.size()) {
        t.resize(q.size());
      }
      for (int i = 0; i < (int) q.size(); i++) {
        t[i] -= delta * q[i];
      }
      if (2 * l <= r - 1) {
        q = p;
        T od = 1 / delta;
        for (T& x : q) {
          x *= od;
        }
        l = r - l;
      }
      swap(p, t);
    }
  }
  assert((int) p.size() == l + 1);
  reverse(p.begin(), p.end());
  return p;
}

最后修改于 2022-04-08