Lagrange Polynomial(多項式補間, 値) (math/combinatorics/lagrange-polynomial.hpp)

• View this file on GitHub
• Last update: 2026-08-10 10:02:02+00:00
• Include: #include "math/combinatorics/lagrange-polynomial.hpp"

Depends on

• Enumeration (組み合わせ) (math/combinatorics/enumeration.hpp)

Code

#pragma once

#include <cstdint>
#include <vector>

#include "enumeration.hpp"

/**
 * @brief Lagrange Polynomial(多項式補間, 値)
 */
template <typename T>
T lagrange_polynomial(const std::vector<T>& y, std::int64_t t) {
  int N = y.size() - 1;
  Enumeration<T> comb(N);
  if (t <= N) return y[t];
  T ret(0);
  std::vector<T> dp(N + 1, 1), pd(N + 1, 1);
  for (int i = 0; i < N; i++) dp[i + 1] = dp[i] * (t - i);
  for (int i = N; i > 0; i--) pd[i - 1] = pd[i] * (t - i);
  for (int i = 0; i <= N; i++) {
    T tmp = y[i] * dp[i] * pd[i] * comb.finv(i) * comb.finv(N - i);
    if ((N - i) & 1)
      ret -= tmp;
    else
      ret += tmp;
  }
  return ret;
}

#line 2 "math/combinatorics/lagrange-polynomial.hpp"

#include <cstdint>
#include <vector>

#line 2 "math/combinatorics/enumeration.hpp"

#include <algorithm>
#include <cstddef>
#line 6 "math/combinatorics/enumeration.hpp"

/**
 * @brief Enumeration(組み合わせ)
 */
template <typename T>
struct Enumeration {
 private:
  static std::vector<T> _fact, _finv, _inv;

  inline static void expand(std::size_t sz) {
    if (_fact.size() < sz + 1) {
      int pre_sz = std::max(1, (int)_fact.size());
      _fact.resize(sz + 1, T(1));
      _finv.resize(sz + 1, T(1));
      _inv.resize(sz + 1, T(1));
      for (int i = pre_sz; i <= (int)sz; i++) {
        _fact[i] = _fact[i - 1] * T(i);
      }
      _finv[sz] = T(1) / _fact[sz];
      for (int i = (int)sz - 1; i >= pre_sz; i--) {
        _finv[i] = _finv[i + 1] * T(i + 1);
      }
      for (int i = pre_sz; i <= (int)sz; i++) {
        _inv[i] = _finv[i] * _fact[i - 1];
      }
    }
  }

 public:
  explicit Enumeration(std::size_t sz = 0) { expand(sz); }

  static inline T fact(int k) {
    expand(k);
    return _fact[k];
  }

  static inline T finv(int k) {
    expand(k);
    return _finv[k];
  }

  static inline T inv(int k) {
    expand(k);
    return _inv[k];
  }

  static T P(int n, int r) {
    if (r < 0 || n < r) return 0;
    return fact(n) * finv(n - r);
  }

  static T C(int p, int q) {
    if (q < 0 || p < q) return 0;
    return fact(p) * finv(q) * finv(p - q);
  }

  static T H(int n, int r) {
    if (n < 0 || r < 0) return 0;
    return r == 0 ? 1 : C(n + r - 1, r);
  }
};

template <typename T>
std::vector<T> Enumeration<T>::_fact = std::vector<T>();
template <typename T>
std::vector<T> Enumeration<T>::_finv = std::vector<T>();
template <typename T>
std::vector<T> Enumeration<T>::_inv = std::vector<T>();
#line 7 "math/combinatorics/lagrange-polynomial.hpp"

/**
 * @brief Lagrange Polynomial(多項式補間, 値)
 */
template <typename T>
T lagrange_polynomial(const std::vector<T>& y, std::int64_t t) {
  int N = y.size() - 1;
  Enumeration<T> comb(N);
  if (t <= N) return y[t];
  T ret(0);
  std::vector<T> dp(N + 1, 1), pd(N + 1, 1);
  for (int i = 0; i < N; i++) dp[i + 1] = dp[i] * (t - i);
  for (int i = N; i > 0; i--) pd[i - 1] = pd[i] * (t - i);
  for (int i = 0; i <= N; i++) {
    T tmp = y[i] * dp[i] * pd[i] * comb.finv(i) * comb.finv(N - i);
    if ((N - i) & 1)
      ret -= tmp;
    else
      ret += tmp;
  }
  return ret;
}

Back to top page