Lagrange Interpolation
(math/lagrange_interpolation.hpp)

• View this file on GitHub
• Last update: 2022-03-31 22:55:04+09:00
• Include: #include "math/lagrange_interpolation.hpp"

Description

Lagrange 補間は，$d+1$ 点が与えられたときにそれらを通る$d$次以下の多項式を求めるアルゴリズムである．この多項式は一意に定まる．

Operations

• T lagrange_interpolation(vector<T> f, long long n)
  • $f(0),f(1),\dots,f(d)$ が与えられたときに，$f(n)$を求める
  • 時間計算量: $O(d)$

Reference

• ABC208 F - Cumulative Sum 解説
• verify: https://atcoder.jp/contests/abc208/submissions/30592769

Code

#pragma once
#include <vector>

template <typename T>
T lagrange_interpolation(const std::vector<T>& f, long long n) {
    const int d = f.size() - 1;
    std::vector<T> fact(d + 1, 1), fact_inv(d + 1, 1);
    for (int i = 1; i <= d; ++i) fact[i] = fact[i - 1] * i;
    fact_inv[d] = T(1) / fact[d];
    for (int i = d; i > 0; --i) fact_inv[i - 1] = fact_inv[i] * i;

    std::vector<T> num(d + 1, 1);
    T a = 1;
    for (int i = 0; i <= d; ++i) {
        num[i] *= a;
        a *= n - i;
    }
    a = 1;
    for (int i = d; i >= 0; --i) {
        num[i] *= a;
        a *= n - i;
    }
    T ans = 0;
    for (int i = 0; i <= d; ++i) {
        ans += ((i + d) & 1 ? -1 : 1) * f[i] * num[i] * fact_inv[i] * fact_inv[d - i];
    }
    return ans;
}

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

template <typename T>
T lagrange_interpolation(const std::vector<T>& f, long long n) {
    const int d = f.size() - 1;
    std::vector<T> fact(d + 1, 1), fact_inv(d + 1, 1);
    for (int i = 1; i <= d; ++i) fact[i] = fact[i - 1] * i;
    fact_inv[d] = T(1) / fact[d];
    for (int i = d; i > 0; --i) fact_inv[i - 1] = fact_inv[i] * i;

    std::vector<T> num(d + 1, 1);
    T a = 1;
    for (int i = 0; i <= d; ++i) {
        num[i] *= a;
        a *= n - i;
    }
    a = 1;
    for (int i = d; i >= 0; --i) {
        num[i] *= a;
        a *= n - i;
    }
    T ans = 0;
    for (int i = 0; i <= d; ++i) {
        ans += ((i + d) & 1 ? -1 : 1) * f[i] * num[i] * fact_inv[i] * fact_inv[d - i];
    }
    return ans;
}

Back to top page