Polynomial Interpolation
Recover or evaluate a low-degree polynomial from sample points, usually with modular Lagrange interpolation.
Polynomial Interpolation
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Polynomial interpolation appears in contest problems whenever a sequence is secretly generated by a low-degree polynomial. If you know enough sample values, you can evaluate the polynomial at new points without reconstructing every coefficient explicitly.
When to Use It
Use it when:
you know that \(f(x)\) is a polynomial of bounded degree,
values \(f(0), f(1), \dots, f(n)\) are easy to compute,
the asked point \(x\) is much larger than \(n\).
Core Idea
For a degree-\(n\) polynomial, \(n+1\) sample points determine the polynomial uniquely. Lagrange interpolation writes \[ f(x) = \sum_{i=0}^{n} f(i)\prod_{j \ne i} \frac{x-j}{i-j}. \]
In modular arithmetic, the denominators are handled with modular inverses.
Key Insight
In competitive programming, the target is usually evaluation, not symbolic reconstruction. That means you can use a fast evaluation formula directly and avoid storing the full expanded polynomial.
Worked Problem
Problem.
Suppose a sequence is known to be generated by a polynomial of degree at most \(d\), and you have computed the first \(d+1\) values by DP. Evaluate the sequence at a huge index \(N\).
Why interpolation fits.
Once the degree bound is known, the early DP values are enough. Interpolation turns those \(d+1\) samples into the value at \(N\) in roughly linear time in \(d\).
Correctness Intuition
Two degree-\(d\) polynomials that agree on \(d+1\) distinct points must be identical. So the interpolated polynomial is the same polynomial that generated the samples.
Complexity Analysis
The straightforward modular Lagrange formula on points \(0,1,\dots,n\) can be evaluated in \(O(n)\) after prefix and suffix product preprocessing.
Implementation
The code assumes:
the modulus is prime,
sample points are \(0,1,\dots,n\),
y[i] = f(i).
Common Pitfalls
Interpolating when the sequence is not actually polynomial.
Forgetting to handle the case where the query point is already among the sample indices.
Using a composite modulus without checking inverse existence.
Variants / Extensions
Interpolation on arbitrary \(x_i\).
Newton-form interpolation.
Recovering coefficients explicitly when the problem really asks for the polynomial itself.
Practice Problems
Evaluate a polynomial sequence at a huge index after computing the first values by DP.
Sum-of-powers style formulas modulo a prime.
Sequence problems where finite differences reveal a small degree.
References
Code
Contest-ready reference implementation for the idea explained above.
template <int MOD>
int mod_pow_int(int a, long long e) {
long long result = 1;
long long base = a;
while (e > 0) {
if (e & 1) result = result * base % MOD;
base = base * base % MOD;
e >>= 1;
}
return (int)result;
}
template <int MOD>
int lagrange_interpolate(const vector<int>& y, long long x) {
int n = (int)y.size() - 1;
if (0 <= x && x <= n) return y[(int)x];
vector<int> fact(n + 2, 1), inv_fact(n + 2, 1);
for (int i = 1; i <= n + 1; ++i) fact[i] = (long long)fact[i - 1] * i % MOD;
inv_fact[n + 1] = mod_pow_int<MOD>(fact[n + 1], MOD - 2);
for (int i = n; i >= 0; --i) inv_fact[i] = (long long)inv_fact[i + 1] * (i + 1) % MOD;
vector<int> pref(n + 2, 1), suff(n + 2, 1);
for (int i = 0; i <= n; ++i) pref[i + 1] = (long long)pref[i] * ((x - i) % MOD + MOD) % MOD;
for (int i = n; i >= 0; --i) suff[i] = (long long)suff[i + 1] * ((x - i) % MOD + MOD) % MOD;
long long answer = 0;
for (int i = 0; i <= n; ++i) {
long long numerator = (long long)pref[i] * suff[i + 1] % MOD;
long long denominator = (long long)inv_fact[i] * inv_fact[n - i] % MOD;
if ((n - i) & 1) denominator = (MOD - denominator) % MOD;
answer = (answer + 1LL * y[i] * numerator % MOD * denominator) % MOD;
}
return (int)answer;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.