ラグランジュ補間
(library/polynomial/lagrange_interpolation.hpp)

View this file on GitHub
Last update: 2023-05-11 13:37:15+09:00
Include: #include "library/polynomial/lagrange_interpolation.hpp"

ラグランジュ補間

$\mathbb{F} _ p$ 上の高々 $N - 1$ 次の多項式 $f(x)$ について、次の情報が分かっている。

\[f(x _ i) = y _ i\ (i = 0, \ldots, N - 1).\]

$x _ i$ が全て互いに相異なるとき、$f$ は存在して一意であり、次のような表示を持つ。

\[f(x) = \sum _ {i = 0} ^ {N - 1} y _ i \dfrac{\prod _ {j \neq i} (x - x _ j)}{\prod _ {j \neq i} (x _ i - x _ j)}.\]

この $f$ を 補間多項式 と呼ぶ。

$x _ i$ および $y _ i$ に対して定まる補間多項式 $f$ に対して、ある与えられた $t$ に関する $f(t)$ を計算する。

アルゴリズム (一般の場合)

多項式 $l$ を以下で定義する。

\[l(x) = \prod _ {i = 0} ^ {N - 1} (x - x _ i)\]

このとき、$\displaystyle l’(x _ i) = \prod _ {j \neq i} (x _ i - x _ j)$ が成り立つ。

$l$ はマージテクおよび高速フーリエ変換による畳み込みなどを用いて $\Theta(N (\log N) ^ 2)$ 時間で計算でき、$l$ に対して $l’$ は $\Theta(N)$ 時間で計算できる。

各 $x _ 0, \ldots, x _ {N - 1}$ に対する $l’(x _ i)$ を求めるのは Multipoint Evaluation なので $\Theta(N (\log N) ^ 2)$ 時間で計算できる。

$l’$ を用いれば、求めたい値は次のように書ける。

\[f(t) = \sum _ {i = 0} ^ {N - 1} \dfrac{y _ i}{l'(x _ i)} \prod _ {j \neq i} (t - x _ j).\]

$i = 0, \ldots, N - 1$ に対して、次を満たす補助的な配列 $\mathrm{pre}, \mathrm{suf}$ を前計算しておく。

\[\begin{aligned} \mathrm{pre}(i) &= \prod _ {j = 0} ^ {i - 1} (t - x _ j),\\ \mathrm{suf}(i) &= \prod _ {j = i + 1} ^ {N - 1} (t - x _ j). \end{aligned}\]

このとき、$\displaystyle \prod _ {j \neq i} (t - x _ j) = \left(\prod _ {j = 0} ^ {i - 1} (t - x _ j)\right)\cdot \left(\prod _ {j = i + 1} ^ {N - 1} (t - x _ j)\right) = \mathrm{pre}(i) \cdot \mathrm{suf}(i)$ として計算できる。

従って、全体 $\Theta(N (\log N) ^ 2)$ 時間で $f(t)$ を計算出来る。

アルゴリズム ($x _ i$ が等差数列を成す場合)

ある $a, b$ に対して $x _ i = a i + b$ が成り立つと仮定すると、求めたい値は次のように書くことが出来る。ここで、$a = 0$ のときは $x _ i$ が全て互いに相異なるという制約から $N = 1$ となり $0 ^ 0$ が現れるが、ここでは $0 ^ 0 = 1$ と定める。

\[f(t) = \dfrac{1}{a ^ {N - 1}}\sum _ {i = 0} ^ {N - 1} y _ i \dfrac{\prod _ {j \neq i} (t - x _ j)}{\prod _ {j \neq i} (i - j)}.\]

各 $\prod _ {j \neq i} (t - x _ j)$ については、一般の場合と同様にして $\Theta(N)$ 時間で計算できる。

$\prod _ {j \neq i} (i - j)$ に関しては、次のように計算できる。

\[\begin{aligned} \prod _ {j \neq i} (i - j) &= \left(\prod _ {j = 0} ^ {i - 1} (i - j)\right) \cdot \left(\prod _ {j = i + 1} ^ {N - 1} (i - j)\right)\\ &= (i\times (i - 1) \times \cdots \times 1) \cdot ((-1) \times (-2) \times \cdots \times (-(N - i - 1)))\\ &= (-1) ^ {N - i - 1} \times i! \times (N - i - 1)!. \end{aligned}\]

従って、$0!, \ldots, (N - 1)!$ の乗法逆元を前計算しておけば、各 $i$ に対する $y _ i \dfrac{\prod _ {j \neq i} (t - x _ j)}{\prod _ {j \neq i} (i - j)}$ は $O(1)$ 時間で計算することが出来ます。

$0!, \ldots, (N - 1)!$ の乗法逆元の計算は $\Theta(N + \log p)$ で、$\dfrac{1}{a ^ {N - 1}}$ の計算は $\Theta(\log N)$ で計算できるので、全体 $\Theta(N + \log p)$ 時間で $f(t)$ を計算できる。

Depends on

Required by

$\displaystyle \sum _ i i ^ d r ^ i$ (library/math/sum_i^d_r^i.hpp)

Verified with

Code

#ifndef SUISEN_INTERPOLATION
#define SUISEN_INTERPOLATION

#include "library/math/product_of_differences.hpp"

namespace suisen {
    // O(N^2+NlogP)
    template <typename T>
    T lagrange_interpolation_naive(const std::vector<T>& xs, const std::vector<T>& ys, const T t) {
        const int n = xs.size();
        assert(int(ys.size()) == n);

        T p{ 1 };
        for (int i = 0; i < n; ++i) p *= t - xs[i];

        T res{ 0 };
        for (int i = 0; i < n; ++i) {
            T w = 1;
            for (int j = 0; j < n; ++j) if (j != i) w *= xs[i] - xs[j];
            res += ys[i] * (t == xs[i] ? 1 : p / (w * (t - xs[i])));
        }
        return res;
    }

    // O(N(logN)^2+NlogP)
    template <typename FPSType, typename T>
    typename FPSType::value_type lagrange_interpolation(const std::vector<T>& xs, const std::vector<T>& ys, const T t) {
        const int n = xs.size();
        assert(int(ys.size()) == n);

        std::vector<FPSType> seg(2 * n);
        for (int i = 0; i < n; ++i) seg[n + i] = FPSType {-xs[i], 1};
        for (int i = n - 1; i > 0; --i) seg[i] = seg[i * 2] * seg[i * 2 + 1];
        seg[1] = seg[1].diff() % seg[1];
        for (int i = 2; i < 2 * n; ++i) seg[i] = seg[i / 2] % seg[i];

        using mint = typename FPSType::value_type;
        mint p{ 1 };
        for (int i = 0; i < n; ++i) p *= t - xs[i];

        mint res{ 0 };
        for (int i = 0; i < n; ++i) {
            mint w = seg[n + i][0];
            res += ys[i] * (t == xs[i] ? 1 : p / (w * (t - xs[i])));
        }
        return res;
    }

    // xs[i] = ai + b
    // requirement: for all 0≤i<j<n, ai+b ≢ aj+b mod p
    template <typename T>
    T lagrange_interpolation_arithmetic_progression(T a, T b, const std::vector<T>& ys, const T t) {
        const int n = ys.size();
        T fac = 1;
        for (int i = 1; i < n; ++i) fac *= i;
        std::vector<T> fac_inv(n), suf(n);
        fac_inv[n - 1] = T(1) / fac;
        suf[n - 1] = 1;
        for (int i = n - 1; i > 0; --i) {
            fac_inv[i - 1] = fac_inv[i] * i;
            suf[i - 1] = suf[i] * (t - (a * i + b));
        }
        T pre = 1, res = 0;
        for (int i = 0; i < n; ++i) {
            T val = ys[i] * pre * suf[i] * fac_inv[i] * fac_inv[n - i - 1];
            if ((n - 1 - i) & 1) res -= val;
            else                 res += val;
            pre *= t - (a * i + b);
        }
        return res / a.pow(n - 1);
    }
    // x = 0, 1, ...
    template <typename T>
    T lagrange_interpolation_arithmetic_progression(const std::vector<T>& ys, const T t) {
        return lagrange_interpolation_arithmetic_progression(T{1}, T{0}, ys, t);
    }
} // namespace suisen

#endif // SUISEN_INTERPOLATION

#line 1 "library/polynomial/lagrange_interpolation.hpp"



#line 1 "library/math/product_of_differences.hpp"



#include <deque>
#line 1 "library/polynomial/multi_point_eval.hpp"



#include <vector>

namespace suisen {
    template <typename FPSType, typename T>
    std::vector<typename FPSType::value_type> multi_point_eval(const FPSType& f, const std::vector<T>& xs) {
        int n = xs.size();
        if (n == 0) return {};
        std::vector<FPSType> seg(2 * n);
        for (int i = 0; i < n; ++i) seg[n + i] = FPSType{ -xs[i], 1 };
        for (int i = n - 1; i > 0; --i) seg[i] = seg[i * 2] * seg[i * 2 + 1];
        seg[1] = f % seg[1];
        for (int i = 2; i < 2 * n; ++i) seg[i] = seg[i / 2] % seg[i];
        std::vector<typename FPSType::value_type> ys(n);
        for (int i = 0; i < n; ++i) ys[i] = seg[n + i].size() ? seg[n + i][0] : 0;
        return ys;
    }
} // namespace suisen


#line 6 "library/math/product_of_differences.hpp"

namespace suisen {
    /**
     * O(N(logN)^2)
     * return the vector p of length xs.size() s.t. p[i]=Π[j!=i](x[i]-x[j])
     */
    template <typename FPSType, typename T>
    std::vector<typename FPSType::value_type> product_of_differences(const std::vector<T>& xs) {
        // f(x):=Π_i(x-x[i])
        // => f'(x)=Σ_i Π[j!=i](x-x[j])
        // => f'(x[i])=Π[j!=i](x[i]-x[j])
        const int n = xs.size();
        std::deque<FPSType> dq;
        for (int i = 0; i < n; ++i) dq.push_back(FPSType{ -xs[i], 1 });
        while (dq.size() >= 2) {
            auto f = std::move(dq.front());
            dq.pop_front();
            auto g = std::move(dq.front());
            dq.pop_front();
            dq.push_back(f * g);
        }
        auto f = std::move(dq.front());
        f.diff_inplace();
        return multi_point_eval<FPSType, T>(f, xs);
    }
} // namespace suisen



#line 5 "library/polynomial/lagrange_interpolation.hpp"

namespace suisen {
    // O(N^2+NlogP)
    template <typename T>
    T lagrange_interpolation_naive(const std::vector<T>& xs, const std::vector<T>& ys, const T t) {
        const int n = xs.size();
        assert(int(ys.size()) == n);

        T p{ 1 };
        for (int i = 0; i < n; ++i) p *= t - xs[i];

        T res{ 0 };
        for (int i = 0; i < n; ++i) {
            T w = 1;
            for (int j = 0; j < n; ++j) if (j != i) w *= xs[i] - xs[j];
            res += ys[i] * (t == xs[i] ? 1 : p / (w * (t - xs[i])));
        }
        return res;
    }

    // O(N(logN)^2+NlogP)
    template <typename FPSType, typename T>
    typename FPSType::value_type lagrange_interpolation(const std::vector<T>& xs, const std::vector<T>& ys, const T t) {
        const int n = xs.size();
        assert(int(ys.size()) == n);

        std::vector<FPSType> seg(2 * n);
        for (int i = 0; i < n; ++i) seg[n + i] = FPSType {-xs[i], 1};
        for (int i = n - 1; i > 0; --i) seg[i] = seg[i * 2] * seg[i * 2 + 1];
        seg[1] = seg[1].diff() % seg[1];
        for (int i = 2; i < 2 * n; ++i) seg[i] = seg[i / 2] % seg[i];

        using mint = typename FPSType::value_type;
        mint p{ 1 };
        for (int i = 0; i < n; ++i) p *= t - xs[i];

        mint res{ 0 };
        for (int i = 0; i < n; ++i) {
            mint w = seg[n + i][0];
            res += ys[i] * (t == xs[i] ? 1 : p / (w * (t - xs[i])));
        }
        return res;
    }

    // xs[i] = ai + b
    // requirement: for all 0≤i<j<n, ai+b ≢ aj+b mod p
    template <typename T>
    T lagrange_interpolation_arithmetic_progression(T a, T b, const std::vector<T>& ys, const T t) {
        const int n = ys.size();
        T fac = 1;
        for (int i = 1; i < n; ++i) fac *= i;
        std::vector<T> fac_inv(n), suf(n);
        fac_inv[n - 1] = T(1) / fac;
        suf[n - 1] = 1;
        for (int i = n - 1; i > 0; --i) {
            fac_inv[i - 1] = fac_inv[i] * i;
            suf[i - 1] = suf[i] * (t - (a * i + b));
        }
        T pre = 1, res = 0;
        for (int i = 0; i < n; ++i) {
            T val = ys[i] * pre * suf[i] * fac_inv[i] * fac_inv[n - i - 1];
            if ((n - 1 - i) & 1) res -= val;
            else                 res += val;
            pre *= t - (a * i + b);
        }
        return res / a.pow(n - 1);
    }
    // x = 0, 1, ...
    template <typename T>
    T lagrange_interpolation_arithmetic_progression(const std::vector<T>& ys, const T t) {
        return lagrange_interpolation_arithmetic_progression(T{1}, T{0}, ys, t);
    }
} // namespace suisen

ラグランジュ補間 (library/polynomial/lagrange_interpolation.hpp)