#include "fps/lagrange-interpolation-point.hpp"
#pragma once #include "../modulo/binomial.hpp" // given : y(x=0) , y(x=1) , ... , y(k) // return : y(x) template <typename mint> mint lagrange_interpolation(const vector<mint>& y, long long x, Binomial<mint>& C) { int N = (int)y.size() - 1; if (x <= N) return y[x]; mint ret = 0; vector<mint> dp(N + 1, 1), pd(N + 1, 1); mint a = x, one = 1; for (int i = 0; i < N; i++) dp[i + 1] = dp[i] * a, a -= one; for (int i = N; i > 0; i--) pd[i - 1] = pd[i] * a, a += one; for (int i = 0; i <= N; i++) { mint tmp = y[i] * dp[i] * pd[i] * C.finv(i) * C.finv(N - i); ret += ((N - i) & 1) ? -tmp : tmp; } return ret; }
#line 2 "fps/lagrange-interpolation-point.hpp" #line 2 "modulo/binomial.hpp" #include <cassert> #include <type_traits> #include <vector> using namespace std; // コンストラクタの MAX に 「C(n, r) や fac(n) でクエリを投げる最大の n 」 // を入れると倍速くらいになる // mod を超えて前計算して 0 割りを踏むバグは対策済み template <typename T> struct Binomial { vector<T> f, g, h; Binomial(int MAX = 0) { assert(T::get_mod() != 0 && "Binomial<mint>()"); f.resize(1, T{1}); g.resize(1, T{1}); h.resize(1, T{1}); if (MAX > 0) extend(MAX + 1); } void extend(int m = -1) { int n = f.size(); if (m == -1) m = n * 2; m = min<int>(m, T::get_mod()); if (n >= m) return; f.resize(m); g.resize(m); h.resize(m); for (int i = n; i < m; i++) f[i] = f[i - 1] * T(i); g[m - 1] = f[m - 1].inverse(); h[m - 1] = g[m - 1] * f[m - 2]; for (int i = m - 2; i >= n; i--) { g[i] = g[i + 1] * T(i + 1); h[i] = g[i] * f[i - 1]; } } T fac(int i) { if (i < 0) return T(0); while (i >= (int)f.size()) extend(); return f[i]; } T finv(int i) { if (i < 0) return T(0); while (i >= (int)g.size()) extend(); return g[i]; } T inv(int i) { if (i < 0) return -inv(-i); while (i >= (int)h.size()) extend(); return h[i]; } T C(int n, int r) { if (n < 0 || n < r || r < 0) return T(0); return fac(n) * finv(n - r) * finv(r); } inline T operator()(int n, int r) { return C(n, r); } template <typename I> T multinomial(const vector<I>& r) { static_assert(is_integral<I>::value == true); int n = 0; for (auto& x : r) { if (x < 0) return T(0); n += x; } T res = fac(n); for (auto& x : r) res *= finv(x); return res; } template <typename I> T operator()(const vector<I>& r) { return multinomial(r); } T C_naive(int n, int r) { if (n < 0 || n < r || r < 0) return T(0); T ret = T(1); r = min(r, n - r); for (int i = 1; i <= r; ++i) ret *= inv(i) * (n--); return ret; } T P(int n, int r) { if (n < 0 || n < r || r < 0) return T(0); return fac(n) * finv(n - r); } // [x^r] 1 / (1-x)^n T H(int n, int r) { if (n < 0 || r < 0) return T(0); return r == 0 ? 1 : C(n + r - 1, r); } }; #line 4 "fps/lagrange-interpolation-point.hpp" // given : y(x=0) , y(x=1) , ... , y(k) // return : y(x) template <typename mint> mint lagrange_interpolation(const vector<mint>& y, long long x, Binomial<mint>& C) { int N = (int)y.size() - 1; if (x <= N) return y[x]; mint ret = 0; vector<mint> dp(N + 1, 1), pd(N + 1, 1); mint a = x, one = 1; for (int i = 0; i < N; i++) dp[i + 1] = dp[i] * a, a -= one; for (int i = N; i > 0; i--) pd[i - 1] = pd[i] * a, a += one; for (int i = 0; i <= N; i++) { mint tmp = y[i] * dp[i] * pd[i] * C.finv(i) * C.finv(N - i); ret += ((N - i) & 1) ? -tmp : tmp; } return ret; }