Interpolation - YessineJallouli/Competitive-Programming GitHub Wiki

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9+9;
 
struct Interpolation {
    vector<ll> xi, yi, den, invfact;
 
    ll power(ll a, ll b) const {
        ll r = 1;
        for (a %= mod; b; b >>= 1, a = a * a % mod)
            if (b & 1) r = r * a % mod;
        return r;
    }
 
    ll inv_mod(ll a) const {
        return power(a, mod - 2);
    }
 
    void precompute_fact(int n) {
        invfact.resize(n+1);
        vector<ll> fact(n+1, 1);
        for (int i = 1; i <= n; ++i) 
            fact[i] = fact[i-1] * i % mod;
        invfact[n] = inv_mod(fact[n]);
        for (int i = n; i > 0; --i) 
            invfact[i-1] = invfact[i] * i % mod;
    }
 
    void init(const vector<ll>& X, const vector<ll>& Y) {
        xi = X; yi = Y;
        int n = xi.size();
        den.resize(n);
        ll s = 1;
        for (int i = n-1; i >= 0; --i) {
            den[i] = s * invfact[n-1-i] % mod * invfact[i] % mod;
            s = (mod - s) % mod;
        }
    }
 
    ll eval(ll v) {
        int n = xi.size();
        vector<ll> L(n,1), R(n,1);
        for (int i = 1; i < n; ++i)
            L[i] = L[i-1] * ((v - xi[i-1] + mod) % mod) % mod;
        for (int i = n-2; i >= 0; --i)
            R[i] = R[i+1] * ((v - xi[i+1] + mod) % mod) % mod;
        ll ans = 0;
        for (int i = 0; i < n; ++i)
            ans = (ans + yi[i] * L[i] % mod * R[i] % mod * den[i]) % mod;
        return ans;
    }
} interpolator;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int d; cin >> d;
    vector<ll> xs(d + 1), ys(d + 1);
    for (int i = 0; i <= d; i++) { 
        xs[i] = i;
        cin >> ys[i];
    }
 
    Interpolation interp;
    interp.precompute_fact(d + 1);
    interp.init(xs, ys);
}