This documentation is automatically generated by online-judge-tools/verification-helper
#include "math/fps/multipoint-evaluation.hpp"
#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;
}