C++ Library for Competitive Programming
#include "emthrm/math/lagrange_interpolation.hpp"
$1 \leq i < j \leq N,\ x_i \neq x_j$ を満たす $(x_i, y_i)$ に対して $f(x_i) = y_i$ を満たす $N - 1$ 次以下の多項式 $f$ を求める。
時間計算量 | |
---|---|
評価版 | $O(N^2)$ |
評価版2 | $O(N)$ |
多項式補間 | $O(N(\log{N})^2)$ |
名前 | 戻り値 | 要件 |
---|---|---|
template <typename T> T lagrange_interpolation(const std::vector<T>& x, const std::vector<T>& y, const T t);
|
$f(x_i) = y_i$ を満たす $f(t)$ | $x_i$ は互いに異なる。 |
template <typename T> T lagrange_interpolation(const std::vector<T>& y, const T t);
|
$f(i) = y_i$ を満たす $f(t)$ | $t < 0,\ N \leq t$ |
名前 | 戻り値 | 備考 |
---|---|---|
template <template <typename> class C, typename T> C<T> polynomial_interpolation(const std::vector<T>& x, const std::vector<T>& y);
|
$f(x_i) = y_i$ を満たす $f$ |
C は冪級数を表す構造体である。 |
ラグランジュ補間
多項式補間
#ifndef EMTHRM_MATH_LAGRANGE_INTERPOLATION_HPP_
#define EMTHRM_MATH_LAGRANGE_INTERPOLATION_HPP_
#include <algorithm>
#include <functional>
#include <iterator>
#include <numeric>
#include <vector>
namespace emthrm {
template <typename T>
T lagrange_interpolation(const std::vector<T>& x, const std::vector<T>& y,
const T t) {
const auto it = std::find(x.begin(), x.end(), t);
if (it != x.end()) return y[std::distance(x.begin(), it)];
const int n = x.size();
T res = 0;
for (int i = 0; i < n; ++i) {
T den = t - x[i];
for (int j = 0; j < n; ++j) {
if (j != i) den *= x[i] - x[j];
}
res += y[i] / den;
}
return std::transform_reduce(
x.begin(), x.end(), res, std::multiplies<T>(),
[t](const T& x_i) -> T { return t - x_i; });
}
} // namespace emthrm
#endif // EMTHRM_MATH_LAGRANGE_INTERPOLATION_HPP_
#line 1 "include/emthrm/math/lagrange_interpolation.hpp"
#include <algorithm>
#include <functional>
#include <iterator>
#include <numeric>
#include <vector>
namespace emthrm {
template <typename T>
T lagrange_interpolation(const std::vector<T>& x, const std::vector<T>& y,
const T t) {
const auto it = std::find(x.begin(), x.end(), t);
if (it != x.end()) return y[std::distance(x.begin(), it)];
const int n = x.size();
T res = 0;
for (int i = 0; i < n; ++i) {
T den = t - x[i];
for (int j = 0; j < n; ++j) {
if (j != i) den *= x[i] - x[j];
}
res += y[i] / den;
}
return std::transform_reduce(
x.begin(), x.end(), res, std::multiplies<T>(),
[t](const T& x_i) -> T { return t - x_i; });
}
} // namespace emthrm