Lagrange Interpolation

A polynomial of degree $\le n$ is uniquely determined by its values at $n+1$ distinct points:

$P(x)={\sum }_{i=0}^n{y}_i{\prod }_{j\ne i}\frac{x-x_j}{x_i-x_j}.$

General points — $O(n^2)$

long long lagrange(const vector<long long>& x, const vector<long long>& y,
                   long long target, long long MOD) {
    int n = x.size();
    long long res = 0;
    for (int i = 0; i < n; i++) {
        long long num = 1, den = 1;
        for (int j = 0; j < n; j++) {
            if (j == i) continue;
            num = num * ((target - x[j]) % MOD + MOD) % MOD;
            den = den * ((x[i] - x[j]) % MOD + MOD) % MOD;
        }
        res = (res + y[i] % MOD * num % MOD * powmod(den, MOD - 2, MOD)) % MOD;
    }
    return res;
}

$O(n^2\log )$ with a modpow per term; $O(n^2)$ if you batch the inverses.

Consecutive points — $O(n)$

When the sample points are $x=0,1,2,\dots ,n$, the products telescope into factorials:

$P(k)={\sum }_{i=0}^n{y}_i\cdot \frac{{\mathrm{pre}}_i\cdot {\mathrm{suf}}_i}{i!(n-i)!}\cdot (-1{)}^{n-i},$

with ${\mathrm{pre}}_i={\prod }_{j<i}(k-j)$ and ${\mathrm{suf}}_i={\prod }_{j>i}(k-j)$ — both computable as prefix and suffix products.

long long lagrangeConsecutive(const vector<long long>& y, long long k, long long MOD) {
    int n = y.size();                                       // points x = 0..n-1
    if (k < n) return y[k];
    vector<long long> pre(n + 1, 1), suf(n + 1, 1);
    for (int i = 0; i < n; i++) pre[i+1] = pre[i] * ((k - i) % MOD) % MOD;
    for (int i = n - 1; i >= 0; i--) suf[i] = suf[i+1] * ((k - i) % MOD) % MOD;
 
    long long res = 0;
    for (int i = 0; i < n; i++) {
        long long num = pre[i] * suf[i+1] % MOD;
        long long den = invFact[i] * invFact[n-1-i] % MOD;
        long long term = y[i] * num % MOD * den % MOD;
        res = ((n - 1 - i) & 1) ? (res - term + MOD) % MOD : (res + term) % MOD;
    }
    return res;
}

$O(n)$ after precomputing factorials — this is the version that appears in contests.

The killer application: sums of powers

$S_k(n)={\sum }_{i=1}^n{i}^k$

is a polynomial in $n$ of degree $k+1$. So compute $S_k(1),S_k(2),\dots ,S_k(k+2)$ by brute force in $O(k)$, then interpolate to get $S_k(n)$ for $n$ up to $10^{18}$ in $O(k)$.

long long powerSum(long long n, int k, long long MOD) {
    vector<long long> y(k + 2, 0);
    for (int i = 1; i <= k + 1; i++)
        y[i] = (y[i-1] + powmod(i, k, MOD)) % MOD;
    return lagrangeConsecutive(y, n, MOD);                  // points 0..k+1
}

The same trick handles any quantity known to be polynomial in $n$: prefix sums of a polynomial, counts satisfying a polynomial formula, and DP answers that are eventually polynomial.

Recognising “the answer is a polynomial”

This is the real skill. Signals:

• the answer is a sum of a polynomial over a range → degree increases by 1;
• the answer counts lattice points in a region scaling linearly with $n$ (Ehrhart polynomials);
• a DP whose transition is linear with constant coefficients, evaluated at $n$;
• the problem gives huge $n$ but the structure only depends on a small degree.

Verification: compute the first $2k+4$ values by brute force, interpolate from the first $k+2$, and check that the predicted values match the rest. If they do, the degree guess is right.

Fast interpolation and evaluation

Task	Naive	Fast
Value at one point, general $x_i$	$O(n^2)$	—
Value at one point, consecutive $x_i$	$O(n)$	—
Coefficients from $n$ points	$O(n^2)$	$O(n{\log }^{2}n)$
Values at $n$ new points	$O(n^2)$	$O(n{\log }^{2}n)$ (multipoint)
Shift $P(x)\to P(x+c)$	$O(n^2)$	$O(n\log n)$

Newton’s divided differences

An alternative form that allows adding points incrementally:

$P(x)={\sum }_i{c}_i{\prod }_{j<i}(x-x_j),$

with the $c_i$ computed by a divided-difference table. $O(n^2)$ to build, but adding one new point is $O(n)$ rather than a full rebuild — useful when the sample set grows.

Pitfalls

Three traps

1. Repeated $x_i$ makes the denominator zero. Deduplicate first.
2. Wrong degree. Interpolating $d+1$ points assumes degree $\le d$; if the true degree is higher, the answer is silently wrong. Always verify with extra points.
3. The target coincides with a sample point. Return $y_i$ directly rather than dividing by zero.

See also: Multipoint Evaluation · Polynomial Arithmetic · Combinatorics