This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
ll mod_pow(ll n, ll k, ll mod) {
ll res = 1;
for(; k>0; k>>=1) {
if(k & 1) (res *= n) %= mod;
(n *= n) %= mod;
}
return res;
}
// N 未満の範囲で、i の逆元 (mod P) を配列に覚える
template <typename NumType>
vector<NumType> get_inv_table(int N, int P) {
vector<NumType> res;
for(int i=0; i<N; i++) {
res.emplace_back(NumType(mod_pow(i, P-2, P)));
}
return res;
}
// ラグランジュ補間
// 観測された (x_i, y_i) を元に多項式を補間
// 元の式が N 次式で N+1 個の点が観測されている場合は元の式が復元可能
// 観測された点を N とすると O(N^2) で動く
template <typename NumType>
struct LagrangePolynomial {
vector<NumType> x, y, f_table, inv_table;
bool use_inv_table;
LagrangePolynomial() : x(), y() {}
LagrangePolynomial(vector<NumType> x_,
vector<NumType> y_,
int P=-1)
: x(x_), y(y_), use_inv_table(P > 0) {
int N = x.size();
for(int i=0; i<N; i++) {
f_table.emplace_back(f(i, x[i]));
}
// get_inv_table がないと CE になるので、
// コピペが面倒ならここを消す (最悪)
if(use_inv_table) {
inv_table = get_inv_table<NumType>(P, P);
}
}
NumType f(int i, NumType p) {
int N = x.size();
NumType res(1);
for(int k=0; k<N; k++) {
if(i == k) continue;
res *= NumType(p - x[k]);
}
return res;
}
NumType interpolate(NumType p) {
int N = x.size();
NumType res(0);
for(int i=0; i<N; i++) {
if(use_inv_table) {
res += y[i] * f(i, p) * inv_table[ int(f_table[i]) ];
}
else {
res += y[i] * f(i, p) / f_table[i];
}
}
return res;
}
};
#line 1 "math/math_018_ragrange_polynomial.cpp"
ll mod_pow(ll n, ll k, ll mod) {
ll res = 1;
for(; k>0; k>>=1) {
if(k & 1) (res *= n) %= mod;
(n *= n) %= mod;
}
return res;
}
// N 未満の範囲で、i の逆元 (mod P) を配列に覚える
template <typename NumType>
vector<NumType> get_inv_table(int N, int P) {
vector<NumType> res;
for(int i=0; i<N; i++) {
res.emplace_back(NumType(mod_pow(i, P-2, P)));
}
return res;
}
// ラグランジュ補間
// 観測された (x_i, y_i) を元に多項式を補間
// 元の式が N 次式で N+1 個の点が観測されている場合は元の式が復元可能
// 観測された点を N とすると O(N^2) で動く
template <typename NumType>
struct LagrangePolynomial {
vector<NumType> x, y, f_table, inv_table;
bool use_inv_table;
LagrangePolynomial() : x(), y() {}
LagrangePolynomial(vector<NumType> x_,
vector<NumType> y_,
int P=-1)
: x(x_), y(y_), use_inv_table(P > 0) {
int N = x.size();
for(int i=0; i<N; i++) {
f_table.emplace_back(f(i, x[i]));
}
// get_inv_table がないと CE になるので、
// コピペが面倒ならここを消す (最悪)
if(use_inv_table) {
inv_table = get_inv_table<NumType>(P, P);
}
}
NumType f(int i, NumType p) {
int N = x.size();
NumType res(1);
for(int k=0; k<N; k++) {
if(i == k) continue;
res *= NumType(p - x[k]);
}
return res;
}
NumType interpolate(NumType p) {
int N = x.size();
NumType res(0);
for(int i=0; i<N; i++) {
if(use_inv_table) {
res += y[i] * f(i, p) * inv_table[ int(f_table[i]) ];
}
else {
res += y[i] * f(i, p) / f_table[i];
}
}
return res;
}
};