Multipoint Evaluation (math/fps/multipoint-evaluation.hpp)

View this file on GitHub
Last update: 2024-04-24 02:34:04+09:00
Include: #include "math/fps/multipoint-evaluation.hpp"

Depends on

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

Verified with

test/verify/yosupo-multipoint-evaluation.test.cpp

Code

#include "subproduct-tree.hpp"

/**
 * @brief Multipoint Evaluation
 */
template< template< typename > class FPS, typename Mint >
FPS< Mint > multipoint_evaluation(const FPS< Mint > &f, const FPS< Mint > &xs) {
  auto g = subproduct_tree(xs);
  int m = (int) xs.size(), k = (int) g.size() / 2;
  g[1] = f % g[1];
  for(int i = 2; i < k + m; i++) g[i] = g[i >> 1] % g[i];
  FPS< Mint > ys(m);
  for(int i = 0; i < m; i++) ys[i] = (g[k + i].empty() ? Mint(0) : g[k + i][0]);
  return ys;
}

#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/multipoint-evaluation.hpp"

/**
 * @brief Multipoint Evaluation
 */
template< template< typename > class FPS, typename Mint >
FPS< Mint > multipoint_evaluation(const FPS< Mint > &f, const FPS< Mint > &xs) {
  auto g = subproduct_tree(xs);
  int m = (int) xs.size(), k = (int) g.size() / 2;
  g[1] = f % g[1];
  for(int i = 2; i < k + m; i++) g[i] = g[i >> 1] % g[i];
  FPS< Mint > ys(m);
  for(int i = 0; i < m; i++) ys[i] = (g[k + i].empty() ? Mint(0) : g[k + i][0]);
  return ys;
}