多項式補間 (ChatGPT 生成)
| 投稿者 | AngrySadEight |
|---|---|
| 言語 | C++17 |
| 更新日時 (JST) | 2026-11-07 16:40:51 |
| サイズ | 4,565 Byte |
| 参照URL | |
更新すると更新日時が変わるので、不都合がある場合は新しく投稿してください。
using Poly = vector<mint>;
// 末尾の 0 を除去
void normalize2(Poly& a) {
while (!a.empty() && a.back() == 0) a.pop_back();
}
// 多項式の加算
Poly poly_add(const Poly& a, const Poly& b) {
Poly c(max(a.size(), b.size()));
for (int i = 0; i < (int)a.size(); i++) c[i] += a[i];
for (int i = 0; i < (int)b.size(); i++) c[i] += b[i];
normalize(c);
return c;
}
// 多項式の乗算
Poly poly_mul(const Poly& a, const Poly& b) {
if (a.empty() || b.empty()) return {};
return convolution(a, b);
}
// f(x)^(-1) mod x^n
// f[0] != 0 を仮定
Poly poly_inv(const Poly& f, int n) {
if (n == 0) return {};
Poly g = {f[0].inv()};
while ((int)g.size() < n) {
int m = min(n, (int)g.size() * 2);
Poly t(min((int)f.size(), m));
for (int i = 0; i < (int)t.size(); i++) {
t[i] = f[i];
}
t = poly_mul(t, g);
t.resize(m);
for (auto& x : t) x = -x;
t[0] += 2;
g = poly_mul(g, t);
g.resize(m);
}
return g;
}
// a(x) mod b(x)
// b != 0 を仮定
Poly poly_mod2(Poly a, const Poly& b) {
normalize(a);
if (a.size() < b.size()) return a;
if (b.size() == 1) return {};
int k = (int)a.size() - (int)b.size() + 1;
Poly ra = a, rb = b;
reverse(ra.begin(), ra.end());
reverse(rb.begin(), rb.end());
ra.resize(k);
Poly inv_rb = poly_inv(rb, k);
Poly q = poly_mul(ra, inv_rb);
q.resize(k);
reverse(q.begin(), q.end());
Poly t = poly_mul(q, b);
for (int i = 0; i < (int)t.size(); i++) {
a[i] -= t[i];
}
a.resize(b.size() - 1);
normalize2(a);
return a;
}
// 多項式の微分
Poly poly_derivative(const Poly& f) {
if (f.size() <= 1) return {};
Poly g(f.size() - 1);
for (int i = 1; i < (int)f.size(); i++) {
g[i - 1] = f[i] * i;
}
return g;
}
struct SubproductTree {
int n, sz;
vector<Poly> prod;
SubproductTree(const vector<mint>& xs) {
n = xs.size();
sz = 1;
while (sz < n) sz <<= 1;
prod.resize(sz * 2);
for (int i = 0; i < sz; i++) {
if (i < n) {
prod[sz + i] = {-xs[i], 1};
} else {
prod[sz + i] = {1};
}
}
for (int i = sz - 1; i >= 1; i--) {
prod[i] = poly_mul(prod[i * 2], prod[i * 2 + 1]);
}
}
// f(x_i) をすべて計算
vector<mint> evaluate(const Poly& f) const {
vector<mint> res(n);
if (n == 0) return res;
auto dfs = [&](auto&& self, int v, const Poly& r) -> void {
if (v >= sz) {
int i = v - sz;
if (i < n) {
res[i] = r.empty() ? mint(0) : r[0];
}
return;
}
Poly l = poly_mod2(r, prod[v * 2]);
Poly rr = poly_mod2(r, prod[v * 2 + 1]);
self(self, v * 2, l);
self(self, v * 2 + 1, rr);
};
dfs(dfs, 1, poly_mod2(f, prod[1]));
return res;
}
// w_i から補間多項式を構成
// Σ w_i * prod[1](x) / (x - x_i)
Poly build(const vector<mint>& w) const {
if (n == 0) return {};
auto dfs = [&](auto&& self, int v) -> Poly {
if (v >= sz) {
int i = v - sz;
return i < n ? Poly{w[i]} : Poly{};
}
Poly l = self(self, v * 2);
Poly r = self(self, v * 2 + 1);
Poly a = poly_mul(l, prod[v * 2 + 1]);
Poly b = poly_mul(r, prod[v * 2]);
return poly_add(a, b);
};
return dfs(dfs, 1);
}
};
// 多項式補間
// 入力: (x_i, y_i) の配列
// 出力: f(x) の係数 (定数項から昇順)
// x_i は互いに相異なると仮定
vector<mint> polynomial_interpolation(
const vector<pair<mint, mint>>& points
) {
int n = points.size();
if (n == 0) return {};
vector<mint> xs(n), ys(n);
for (int i = 0; i < n; i++) {
xs[i] = points[i].first;
ys[i] = points[i].second;
}
SubproductTree tree(xs);
// P(x) = Π (x - x_i)
const Poly& P = tree.prod[1];
// P'(x_i) を計算
Poly dP = poly_derivative(P);
vector<mint> den = tree.evaluate(dP);
// w_i = y_i / P'(x_i)
vector<mint> w(n);
for (int i = 0; i < n; i++) {
assert(den[i] != 0);
w[i] = ys[i] / den[i];
}
// f(x) = Σ w_i * P(x) / (x - x_i)
Poly f = tree.build(w);
f.resize(n);
return f;
}