Polynomial Interpolation(多項式補間) (math/fps/polynomial-interpolation.hpp)

View this file on GitHub
Last update: 2024-05-01 23:44:47+09:00
Include: #include "math/fps/polynomial-interpolation.hpp"

Depends on

Subproduct Tree (math/fps/subproduct-tree.hpp)

Verified with

test/verify/yosupo-polynomial-interpolation.test.cpp

Code

#include "subproduct-tree.hpp"

/**
 * @brief Polynomial Interpolation(多項式補間)
 */
template <template <typename> class FPS, typename Mint>
FPS<Mint> polynomial_interpolation(const FPS<Mint> &xs, const FPS<Mint> &ys) {
  assert(xs.size() == ys.size());
  auto mul = subproduct_tree(xs);
  int n = (int)xs.size(), k = (int)mul.size() / 2;
  vector<FPS<Mint> > g(2 * k);
  g[1] = mul[1].diff() % mul[1];
  for (int i = 2; i < k + n; i++) g[i] = g[i >> 1] % mul[i];
  for (int i = 0; i < n; i++) g[k + i] = {ys[i] / g[k + i][0]};
  for (int i = k; i-- > 1;)
    g[i] = g[i << 1] * mul[i << 1 | 1] + g[i << 1 | 1] * mul[i << 1];
  return g[1];
}

#line 1 "math/fps/subproduct-tree.hpp"
/**
 * @brief Subproduct Tree
 */
template <template <typename> class FPS, typename Mint>
vector<FPS<Mint> > subproduct_tree(const FPS<Mint> &xs) {
  int n = (int)xs.size();
  int k = 1;
  while (k < n) k <<= 1;
  vector<FPS<Mint> > g(2 * k, {1});
  for (int i = 0; i < n; i++) g[k + i] = {-xs[i], Mint(1)};
  for (int i = k; i-- > 1;) g[i] = g[i << 1] * g[i << 1 | 1];
  return g;
}
#line 2 "math/fps/polynomial-interpolation.hpp"

/**
 * @brief Polynomial Interpolation(多項式補間)
 */
template <template <typename> class FPS, typename Mint>
FPS<Mint> polynomial_interpolation(const FPS<Mint> &xs, const FPS<Mint> &ys) {
  assert(xs.size() == ys.size());
  auto mul = subproduct_tree(xs);
  int n = (int)xs.size(), k = (int)mul.size() / 2;
  vector<FPS<Mint> > g(2 * k);
  g[1] = mul[1].diff() % mul[1];
  for (int i = 2; i < k + n; i++) g[i] = g[i >> 1] % mul[i];
  for (int i = 0; i < n; i++) g[k + i] = {ys[i] / g[k + i][0]};
  for (int i = k; i-- > 1;)
    g[i] = g[i << 1] * mul[i << 1 | 1] + g[i << 1 | 1] * mul[i << 1];
  return g[1];
}