Lagrange Interpolation
(math/lagrange_interpolation.hpp)

• View this file on GitHub
• Last update: 2023-10-26 02:38:17+09:00
• Include: #include "math/lagrange_interpolation.hpp"
• Link: https://atcoder.jp/contests/abc208/editorial/2195
• Link: https://atcoder.jp/contests/abc208/tasks/abc208_f

説明

$d$ 次多項式 $f$ について $f(0), f(1), \dots, f(d)$ の $d+1$ 点の値を与え、 $f(n)$ の値を求める。 $O(d)$

Required by

• $\sum_{i = 0}^{n-1} a^i f(i)$ (math/sum_of_exp_times_poly.hpp)
• $\sum_{i = 0}^{n-1} i^k$ (math/sum_of_powers_iota.hpp)

Verified with

• test/math/Sum_of_Exponential_Times_Polynomial.test.cpp
• test/math/Sum_of_Exponential_Times_Polynomial_Limit.test.cpp
• test/math/Sum_of_Powers_Iota.test.cpp
• test/yuki/yuki_2747.test.cpp

Code

#pragma once

#include <vector>

/*
    reference: https://atcoder.jp/contests/abc208/editorial/2195
    verify: https://atcoder.jp/contests/abc208/tasks/abc208_f
*/

namespace ebi {

template <class mint>
mint lagrange_interpolation(const std::vector<mint> &f, long long n) {
    const int d = int(f.size()) - 1;  // Nのd次以下の多項式
    mint fact = 1;
    std::vector<mint> inv_fact(d + 1);
    for (int i = 1; i < d + 1; ++i) {
        fact *= i;
    }
    inv_fact[d] = fact.inv();
    for (int i = d; i > 0; i--) {
        inv_fact[i - 1] = inv_fact[i] * i;
    }
    std::vector<mint> l(d + 1), r(d + 1);
    l[0] = 1;
    for (int i = 0; i < d; ++i) {
        l[i + 1] = l[i] * (n - i);
    }
    r[d] = 1;
    for (int i = d; i > 0; --i) {
        r[i - 1] = r[i] * (n - i);
    }
    mint res = 0;
    for (int i = 0; i < d + 1; ++i) {
        res += mint((d - i) % 2 == 1 ? -1 : 1) * f[i] * l[i] * r[i] *
               inv_fact[i] * inv_fact[d - i];
    }
    return res;
}

}  // namespace ebi

#line 2 "math/lagrange_interpolation.hpp"

#include <vector>

/*
    reference: https://atcoder.jp/contests/abc208/editorial/2195
    verify: https://atcoder.jp/contests/abc208/tasks/abc208_f
*/

namespace ebi {

template <class mint>
mint lagrange_interpolation(const std::vector<mint> &f, long long n) {
    const int d = int(f.size()) - 1;  // Nのd次以下の多項式
    mint fact = 1;
    std::vector<mint> inv_fact(d + 1);
    for (int i = 1; i < d + 1; ++i) {
        fact *= i;
    }
    inv_fact[d] = fact.inv();
    for (int i = d; i > 0; i--) {
        inv_fact[i - 1] = inv_fact[i] * i;
    }
    std::vector<mint> l(d + 1), r(d + 1);
    l[0] = 1;
    for (int i = 0; i < d; ++i) {
        l[i + 1] = l[i] * (n - i);
    }
    r[d] = 1;
    for (int i = d; i > 0; --i) {
        r[i - 1] = r[i] * (n - i);
    }
    mint res = 0;
    for (int i = 0; i < d + 1; ++i) {
        res += mint((d - i) % 2 == 1 ? -1 : 1) * f[i] * l[i] * r[i] *
               inv_fact[i] * inv_fact[d - i];
    }
    return res;
}

}  // namespace ebi

Back to top page