< AngrySadEightさんのAI生成コード置き場

多項式補間 (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;
}