seq/find_linear_rec.hpp

• View this file on GitHub
• Last update: 2022-05-11 21:07:53+09:00
• Include: #include "seq/find_linear_rec.hpp"

Required by

• graph/count/BEST.hpp
• linalg/blackbox/det.hpp
• linalg/blackbox/min_poly.hpp
• seq/interpolate_linear_rec.hpp

Verified with

• test/library_checker/math/find_linear_recurrence.test.cpp
• test/library_checker/matrix/sparse_matrix_det.test.cpp
• test/mytest/min_poly.test.cpp
• test/yukicoder/1500.test.cpp
• test/yukicoder/1516.test.cpp
• test/yukicoder/1547.test.cpp
• test/yukicoder/1561.test.cpp
• test/yukicoder/1755.test.cpp
• test/yukicoder/1844.test.cpp
• test/yukicoder/2305.test.cpp
• test/yukicoder/310.test.cpp
• test/yukicoder/541.test.cpp
• test/yukicoder/578.test.cpp
• test/yukicoder/579.test.cpp
• test_atcoder/abc336g.test.cpp

Code

#pragma once

template <typename mint>
vector<mint> find_linear_rec(vector<mint>& A) {
  int N = len(A);
  vc<mint> B = {1}, C = {1};
  int l = 0, m = 1;
  mint p = 1;
  FOR(i, N) {
    mint d = A[i];
    FOR3(j, 1, l + 1) { d += C[j] * A[i - j]; }
    if (d == 0) {
      ++m;
      continue;
    }
    auto tmp = C;
    mint q = d / p;
    if (len(C) < len(B) + m) C.insert(C.end(), len(B) + m - len(C), 0);
    FOR(j, len(B)) C[j + m] -= q * B[j];
    if (l + l <= i) {
      B = tmp;
      l = i + 1 - l, m = 1;
      p = d;
    } else {
      ++m;
    }
  }
  return C;
}

#line 2 "seq/find_linear_rec.hpp"

template <typename mint>
vector<mint> find_linear_rec(vector<mint>& A) {
  int N = len(A);
  vc<mint> B = {1}, C = {1};
  int l = 0, m = 1;
  mint p = 1;
  FOR(i, N) {
    mint d = A[i];
    FOR3(j, 1, l + 1) { d += C[j] * A[i - j]; }
    if (d == 0) {
      ++m;
      continue;
    }
    auto tmp = C;
    mint q = d / p;
    if (len(C) < len(B) + m) C.insert(C.end(), len(B) + m - len(C), 0);
    FOR(j, len(B)) C[j + m] -= q * B[j];
    if (l + l <= i) {
      B = tmp;
      l = i + 1 - l, m = 1;
      p = d;
    } else {
      ++m;
    }
  }
  return C;
}

Back to top page