C++ Library for Competitive Programming
#include "emthrm/math/formal_power_series/multipoint_evaluation.hpp"
複数の $x$ に対して $f(x)$ を求めるアルゴリズムである。
$\langle O(N(\log{N})^2), O(N(\log{N})^2) \rangle$
template <template <typename> class C, typename T>
struct MultipointEvaluation;
C
:冪級数を表す構造体T
:係数を表す要素型名前 | 説明 |
---|---|
std::vector<T> f_x |
$\lbrace f(x) \mid x \in \mathrm{xs} \rbrace$ |
std::vector<C<T>> subproduct_tree |
subproduct tree |
名前 | 効果 |
---|---|
explicit MultipointEvaluation(const std::vector<T> &xs); |
multipoint evaluation を考える。 |
void build(const C<T>& f); |
多項式 $f$ に対して f_x を構築する。 |
https://judge.yosupo.jp/submission/3793
#ifndef EMTHRM_MATH_FORMAL_POWER_SERIES_MULTIPOINT_EVALUATION_HPP_
#define EMTHRM_MATH_FORMAL_POWER_SERIES_MULTIPOINT_EVALUATION_HPP_
#include <algorithm>
#include <iterator>
#include <vector>
namespace emthrm {
template <template <typename> class C, typename T>
struct MultipointEvaluation {
std::vector<T> f_x;
std::vector<C<T>> subproduct_tree;
explicit MultipointEvaluation(const std::vector<T> &xs)
: f_x(xs.size()), subproduct_tree(xs.size() << 1), n(xs.size()) {
std::transform(xs.begin(), xs.end(), std::next(subproduct_tree.begin(), n),
[](const T& x) -> C<T> { return C<T>{-x, 1}; });
for (int i = n - 1; i > 0; --i) {
subproduct_tree[i] =
subproduct_tree[i << 1] * subproduct_tree[(i << 1) + 1];
}
}
void build(const C<T>& f) { dfs(f, 1); }
private:
const int n;
void dfs(C<T> f, int node) {
f %= subproduct_tree[node];
if (node < n) {
dfs(f, node << 1);
dfs(f, (node << 1) + 1);
} else {
f_x[node - n] = f[0];
}
}
};
} // namespace emthrm
#endif // EMTHRM_MATH_FORMAL_POWER_SERIES_MULTIPOINT_EVALUATION_HPP_
#line 1 "include/emthrm/math/formal_power_series/multipoint_evaluation.hpp"
#include <algorithm>
#include <iterator>
#include <vector>
namespace emthrm {
template <template <typename> class C, typename T>
struct MultipointEvaluation {
std::vector<T> f_x;
std::vector<C<T>> subproduct_tree;
explicit MultipointEvaluation(const std::vector<T> &xs)
: f_x(xs.size()), subproduct_tree(xs.size() << 1), n(xs.size()) {
std::transform(xs.begin(), xs.end(), std::next(subproduct_tree.begin(), n),
[](const T& x) -> C<T> { return C<T>{-x, 1}; });
for (int i = n - 1; i > 0; --i) {
subproduct_tree[i] =
subproduct_tree[i << 1] * subproduct_tree[(i << 1) + 1];
}
}
void build(const C<T>& f) { dfs(f, 1); }
private:
const int n;
void dfs(C<T> f, int node) {
f %= subproduct_tree[node];
if (node < n) {
dfs(f, node << 1);
dfs(f, (node << 1) + 1);
} else {
f_x[node - n] = f[0];
}
}
};
} // namespace emthrm