Kth Term of Linearly Recurrent Sequence (math/fps/kth-term-of-linearly-recurrent-sequence.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-04-27 01:27:28+09:00
• Include: #include "math/fps/kth-term-of-linearly-recurrent-sequence.hpp"

概要

線形線形漸化的数列の第 $N$ 項を求める。

$k$ 項間漸化式 $a_n = \sum_{d=1}^{k} c_d a_{n-d} (n \ge d)$ が存在するとき数列 $a$ は線形漸化的数列であるという。線形漸化的数列 $a$ は、初項 $(a_1, \cdots, a_{d-1})$ と係数 $c = (c_1, \cdots, c_d), c_d \neq 0$ を用いることで定義される。$d$ を位数と呼ぶ。

位数 $d$ の線形漸化式が存在するとき、ある次数 $d$ の $Q(0)=1$ 満たす多項式 $Q(x)$ と次数 $d-1$ 以下の多項式 $P(x)$ が存在して、$G(x)=\frac {P(x)} {Q(x)}$ が母関数となる。具体的には、

$Q(x) = 1 - c_1x - c_2x^2 - \cdots - c_kx^k$

$P(x) = Q(x)(a_0 + a_1x + a_2x^2 + \cdots + a^{k-1}x^{k-1}) \pmod {x^k}$

とすればよい。$P(x)$ は $Q(x)$ と $a$ を畳み込むと求められる。

従って、数列 $a$ の第 $N$ 項を求めるために、 $\frac {P(x)} {Q(x)}$ の $x^N$ の係数を求めればよくて、Bostan-Mori Algorithm を用いることで効率的に計算できる。

計算量

$O(K \log K \log N)$

Depends on

• Coeff of Rational Function (math/fps/coeff-of-rational-function.hpp)

Verified with

• test/verify/yosupo-kth-term-of-linearly-recurrent-sequence.test.cpp

Code

#include "coeff-of-rational-function.hpp"

/**
 * @brief Kth Term of Linearly Recurrent Sequence
 *
 */
template <template <typename> class FPS, typename Mint>
Mint kth_term_of_linearly_recurrent_sequence(const FPS<Mint> &a, FPS<Mint> c,
                                             int64_t k) {
  assert(a.size() == c.size());
  c = FPS<Mint>{1} - (c << 1);
  return coeff_of_rational_function((a * c).pre(a.size()), c, k);
}

#line 1 "math/fps/coeff-of-rational-function.hpp"
/**
 * @brief Coeff of Rational Function
 *
 */
template <template <typename> class FPS, typename Mint>
Mint coeff_of_rational_function(FPS<Mint> P, FPS<Mint> Q, int64_t k) {
  // compute the coefficient [x^k] P/Q of rational power series
  Mint ret = 0;
  if (P.size() >= Q.size()) {
    auto R = P / Q;
    P -= R * Q;
    P.shrink();
    if (k < (int)R.size()) ret += R[k];
  }
  if (P.empty()) return ret;
  P.resize((int)Q.size() - 1);
  auto sub = [&](const FPS<Mint> &as, bool odd) {
    FPS<Mint> bs((as.size() + !odd) / 2);
    for (int i = odd; i < (int)as.size(); i += 2) bs[i >> 1] = as[i];
    return bs;
  };
  while (k > 0) {
    auto Q2(Q);
    for (int i = 1; i < (int)Q2.size(); i += 2) Q2[i] = -Q2[i];
    P = sub(P * Q2, k & 1);
    Q = sub(Q * Q2, 0);
    k >>= 1;
  }
  return ret + P[0];
}
#line 2 "math/fps/kth-term-of-linearly-recurrent-sequence.hpp"

/**
 * @brief Kth Term of Linearly Recurrent Sequence
 *
 */
template <template <typename> class FPS, typename Mint>
Mint kth_term_of_linearly_recurrent_sequence(const FPS<Mint> &a, FPS<Mint> c,
                                             int64_t k) {
  assert(a.size() == c.size());
  c = FPS<Mint>{1} - (c << 1);
  return coeff_of_rational_function((a * c).pre(a.size()), c, k);
}

Back to top page