Lagrange Interpolation
(math/lagrange_interpolation.hpp)

• View this file on GitHub
• Last update: 2026-10-27 12:32:30+09:00
• Include: #include "math/lagrange_interpolation.hpp"

概要

• 標本点を通る多項式の値を求める。

使い方

• lagrange_interpolation(y, c): $f(i) = $ y[i] ($0 \le i < n$) となる次数 $n - 1$ 以下の多項式 $f$ について $f(c)$ を返す。
• lagrange_interpolation(x, y, c): $f($ x[i] $) = $ y[i] ($0 \le i < n$) となる次数 $n - 1$ 以下の多項式 $f$ について $f(c)$ を返す。

制約

• mint は atcoder::static_modint<m> または atcoder::dynamic_modint<id>
• $m$ は素数
• $1 \le n < m$
• lagrange_interpolation(x, y, c): x の要素は相異なる

計算量

• lagrange_interpolation(y, c): $\mathcal{O}(n)$
• lagrange_interpolation(x, y, c): $\mathcal{O}(n^2)$

Depends on

• Combinatorics (math/combinatorics.hpp)

Verified with

• test/unit/lagrange_interpolation.test.cpp
• test/yukicoder/665.test.cpp

Code

#pragma once
#include <cassert>
#include <vector>

#include "math/combinatorics.hpp"
template <class mint> mint lagrange_interpolation(const std::vector<mint>& y, mint c) {
    int n = int(y.size());
    assert(n >= 1);
    long long cv = c.val();
    if (cv < n) return y[cv];
    std::vector<mint> pre(n + 1, 1), suf(n + 1, 1);
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] * (c - i);
    for (int i = n - 1; i >= 0; i--) suf[i] = suf[i + 1] * (c - i);
    using comb = combinatorics<mint>;
    mint ret = 0;
    for (int i = 0; i < n; i++) {
        mint t = y[i] * pre[i] * suf[i + 1] * comb::fact_inv(i) * comb::fact_inv(n - 1 - i);
        ret += (n - 1 - i) & 1 ? -t : t;
    }
    return ret;
}
template <class mint>
mint lagrange_interpolation(const std::vector<mint>& x, const std::vector<mint>& y, mint c) {
    int n = int(x.size());
    assert(n >= 1 && int(y.size()) == n);
    mint ret = 0;
    for (int i = 0; i < n; i++) {
        mint num = 1, den = 1;
        for (int j = 0; j < n; j++) {
            if (j == i) continue;
            assert(x[i] != x[j]);
            num *= c - x[j];
            den *= x[i] - x[j];
        }
        ret += y[i] * num / den;
    }
    return ret;
}

#line 2 "math/lagrange_interpolation.hpp"
#include <cassert>
#include <vector>

#line 4 "math/combinatorics.hpp"
template <typename mint>
struct combinatorics {
    static mint fact(int n) {
        ensure(n);
        return facts[n];
    }
    static mint fact_inv(int n) {
        ensure(n);
        return ifacts[n];
    }
    static mint inv(int n) {
        assert(1 <= n);
        ensure(n);
        return ifacts[n] * facts[n - 1];
    }
    static mint C(int n, int k) {
        if (n < 0 || n < k || k < 0) return 0;
        return fact(n) * fact_inv(n - k) * fact_inv(k);
    }
    static mint P(int n, int k) {
        if (n < 0 || n < k || k < 0) return 0;
        return fact(n) * fact_inv(n - k);
    }
    static mint H(int n, int k) {
        if (n < 0 || k < 0) return 0;
        if (k == 0) return 1;
        return C(n + k - 1, k);
    }
    static void ensure(int n) {
        assert(n < mint::mod());
        int sz = facts.size();
        if (sz > n) return;
        if (n < sz << 1) n = std::min(mint::mod() - 1, sz << 1);
        facts.resize(n + 1);
        ifacts.resize(n + 1);
        for (int i = sz; i <= n; i++) facts[i] = facts[i - 1] * i;
        ifacts[n] = facts[n].inv();
        for (int i = n; i >= sz; i--) ifacts[i - 1] = ifacts[i] * i;
    }

private:
    static inline std::vector<mint> facts{1};
    static inline std::vector<mint> ifacts{1};
};
#line 6 "math/lagrange_interpolation.hpp"
template <class mint> mint lagrange_interpolation(const std::vector<mint>& y, mint c) {
    int n = int(y.size());
    assert(n >= 1);
    long long cv = c.val();
    if (cv < n) return y[cv];
    std::vector<mint> pre(n + 1, 1), suf(n + 1, 1);
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] * (c - i);
    for (int i = n - 1; i >= 0; i--) suf[i] = suf[i + 1] * (c - i);
    using comb = combinatorics<mint>;
    mint ret = 0;
    for (int i = 0; i < n; i++) {
        mint t = y[i] * pre[i] * suf[i + 1] * comb::fact_inv(i) * comb::fact_inv(n - 1 - i);
        ret += (n - 1 - i) & 1 ? -t : t;
    }
    return ret;
}
template <class mint>
mint lagrange_interpolation(const std::vector<mint>& x, const std::vector<mint>& y, mint c) {
    int n = int(x.size());
    assert(n >= 1 && int(y.size()) == n);
    mint ret = 0;
    for (int i = 0; i < n; i++) {
        mint num = 1, den = 1;
        for (int j = 0; j < n; j++) {
            if (j == i) continue;
            assert(x[i] != x[j]);
            num *= c - x[j];
            den *= x[i] - x[j];
        }
        ret += y[i] * num / den;
    }
    return ret;
}

Back to top page