多点評価 (ChatGPT 生成)
| 投稿者 | AngrySadEight |
|---|---|
| 言語 | C++17 |
| 更新日時 (JST) | 2026-11-07 16:39:38 |
| サイズ | 2,884 Byte |
| 参照URL | |
更新すると更新日時が変わるので、不都合がある場合は新しく投稿してください。
using Poly = vector<mint>;
// 末尾の 0 を除去する
void normalize(Poly& f) {
while (f.size() > 1 && f.back() == mint(0)) {
f.pop_back();
}
if (f.empty()) f.push_back(0);
}
// 多項式の積
Poly multiply(const Poly& a, const Poly& b) {
return atcoder::convolution(a, b);
}
// 形式的冪級数の逆元
// f[0] != 0 を仮定
// f * g = 1 (mod x^n) となる g を返す
Poly fps_inv(const Poly& f, int n) {
if (n == 0) return {};
assert(!f.empty() && f[0] != mint(0));
Poly g = {f[0].inv()};
for (int k = 1; k < n; k *= 2) {
int m = min(2 * k, n);
Poly a(min((int)f.size(), m));
for (int i = 0; i < (int)a.size(); i++) {
a[i] = f[i];
}
// g <- g * (2 - f*g) mod x^m
Poly t = multiply(a, g);
t.resize(m);
for (auto& x : t) x = -x;
t[0] += 2;
g = multiply(g, t);
g.resize(m);
}
return g;
}
// 多項式の剰余 a mod b
// b != 0 を仮定
Poly poly_mod(Poly a, Poly b) {
normalize(a);
normalize(b);
assert(!(b.size() == 1 && b[0] == mint(0)));
int n = (int)a.size();
int m = (int)b.size();
if (n < m) return a;
if (m == 1) return {0};
int k = n - m + 1;
// 商 q = a / b を反転多項式から求める
Poly ra(a.rbegin(), a.rend());
Poly rb(b.rbegin(), b.rend());
ra.resize(k);
Poly ib = fps_inv(rb, k);
Poly rq = multiply(ra, ib);
rq.resize(k);
Poly q(rq.rbegin(), rq.rend());
// 余り r = a - b*q
Poly bq = multiply(b, q);
Poly r(m - 1, mint(0));
for (int i = 0; i < m - 1; i++) {
r[i] = a[i] - bq[i];
}
normalize(r);
return r;
}
// 多点評価
// f[i] は x^i の係数
// 戻り値 res[i] = f(xs[i])
vector<mint> multipoint_evaluation(
const vector<mint>& f,
const vector<mint>& xs
) {
int m = (int)xs.size();
if (m == 0) return {};
int sz = 1;
while (sz < m) sz *= 2;
// 積木
// tree[v] = 対応する (x - xs[i]) の積
vector<Poly> tree(2 * sz);
for (int i = 0; i < sz; i++) {
if (i < m) {
tree[sz + i] = {-xs[i], mint(1)};
} else {
tree[sz + i] = {mint(1)};
}
}
for (int i = sz - 1; i >= 1; i--) {
tree[i] = multiply(
tree[2 * i],
tree[2 * i + 1]
);
}
// 各ノードにおける f の剰余
vector<Poly> rem(2 * sz);
if (f.empty()) {
rem[1] = {0};
} else {
rem[1] = poly_mod(f, tree[1]);
}
for (int i = 1; i < sz; i++) {
rem[2 * i] = poly_mod(
rem[i], tree[2 * i]
);
rem[2 * i + 1] = poly_mod(
rem[i], tree[2 * i + 1]
);
}
vector<mint> res(m);
for (int i = 0; i < m; i++) {
res[i] = rem[sz + i][0];
}
return res;
}