ラグランジュ補間

概要

$n$ 個の組 $(x,f(x))$ から関数を補間し，$f(t)$ を求めます．

使い方

$[x_1, \cdots , x_n]$, $[f(x_1), \cdots , f(x_n)]$, $t$ をとり $f(t)$ を返す．

実装

//@require ../math/modpow.cc
//@require ../math/modinv.cc
template <int mod = 1000000007>
ll lagrangeInterpolation(const std::vector<ll> &x, const std::vector<ll> &fx, ll t) {
    auto it = find(x.begin(), x.end(), t);
    if (it != x.end()) return fx[it - x.begin()];

    int n = x.size() - 1;

    ll nume = 1;
    for (int m = 0; m <= n; ++m) {
        nume *= (t - x[m] + mod) % mod;
        nume %= mod;
    }

    ll res = 0;
    for (int k = 0; k <= n; k++) {
        ll e = 1;
        for (int m = 0; m <= n; m++) {
            if (m != k) {
                e *= (x[k] - x[m] + mod) % mod;
                e %= mod;
            }
        }
        ll r = nume;
        r *= modinv((t - x[k] + mod) % mod, mod);
        r %= mod;
        r *= modinv(e, mod);
        r %= mod;
        res += fx[k] * r % mod;
    }
    return res % mod;
}

検証

ARC033 D