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

多点評価 (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;
}