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

• View this file on GitHub
• Last update: 2024-04-27 01:27:28+09:00
• Include: #include "math/combinatorics/lagrange-polynomial.hpp"

Code

/**
 * @brief Lagrange Polynomial(多項式補間, 値)
 */
template <typename T>
T lagrange_polynomial(const vector<T> &y, int64_t t) {
  int N = y.size() - 1;
  Combination<T> comb(N);
  if (t <= N) return y[t];
  T ret(0);
  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.rfact(i) * comb.rfact(N - i);
    if ((N - i) & 1)
      ret -= tmp;
    else
      ret += tmp;
  }
  return ret;
}

#line 1 "math/combinatorics/lagrange-polynomial.hpp"
/**
 * @brief Lagrange Polynomial(多項式補間, 値)
 */
template <typename T>
T lagrange_polynomial(const vector<T> &y, int64_t t) {
  int N = y.size() - 1;
  Combination<T> comb(N);
  if (t <= N) return y[t];
  T ret(0);
  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.rfact(i) * comb.rfact(N - i);
    if ((N - i) & 1)
      ret -= tmp;
    else
      ret += tmp;
  }
  return ret;
}

Back to top page