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
• graph/count/count_spanning_tree.hpp
• linalg/blackbox/det.hpp
• linalg/blackbox/min_poly.hpp
• seq/interpolate_linear_rec.hpp

Verified with

• test/1_mytest/min_poly.test.cpp
• test/2_library_checker/graph/count_spanning_tree_directed_dense.test.cpp
• test/2_library_checker/graph/count_spanning_tree_directed_sparse.test.cpp
• test/2_library_checker/graph/count_spanning_tree_undirected_dense.test.cpp
• test/2_library_checker/graph/count_spanning_tree_undirected_sparse.test.cpp
• test/2_library_checker/graph/counting_eulerian_dense.test.cpp
• test/2_library_checker/graph/counting_eulerian_sparse.test.cpp
• test/2_library_checker/linear_algebra/sparse_matrix_det.test.cpp
• test/2_library_checker/other/find_linear_recurrence.test.cpp
• test/3_yukicoder/1500.test.cpp
• test/3_yukicoder/1516.test.cpp
• test/3_yukicoder/1547.test.cpp
• test/3_yukicoder/1561.test.cpp
• test/3_yukicoder/1755.test.cpp
• test/3_yukicoder/1844.test.cpp
• test/3_yukicoder/2305.test.cpp
• test/3_yukicoder/2877.test.cpp
• test/3_yukicoder/310.test.cpp
• test/3_yukicoder/541.test.cpp
• test/3_yukicoder/578.test.cpp
• test/3_yukicoder/579.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