Lagrange Interpolation by grhkm

No polynomial stuff because I don't know $O(n\log{n})$ polynomial multiplication :(

Main results:

Given $f(x_1)=y_1, f(x_2)=y_2, ..., f(x_n)=y_n$ we can calculate $f(X)$ where $f$ is the unique $(n+1)$-degree polynomial

For general {$x_i$} we can do so in $O(n^2)$

For consecutive {$x_i$} i.e. $x_j=x_1+(j-1)$, we can do so in $O(n)$ excluding binary exponentiation

Why useful?

Calculate $1^n+2^n+...+X^n$ in $O(n)$

DP optimization

With polynomials you can do cool things but not gonna cover this blog

Let's get started :)

Assume all polynomials below are $(n+1)$ degree unless specified.

Idea:

To start let's deal with first problem:

Given $f(x_1)=y_1, f(x_2)=y_2, ..., f(x_n)=y_n$ and an integer $X$ we can calculate $f(X)$ where $f$ is the unique $(n+1)$-degree polynomial

Let's consider an easier version:

Find polynomial satisfying $f(x_1)=y_i, f(x_2)=0, ..., f(x_n)=0$

As we learn in school, $f(r)=0 \implies (x-r)$ is divisor

We can write this down:

Now notice that $f(x_1)=\prod_{i=2}^n (x_1-x_i)$ (a constant), but we want it to be $y_1$

We can simply scale the polynomial by a correct factor i.e.

Similarly, we can find a similar polynomial such that $f_i(x_i)=y_i$ and $f_i(x_j)=0 \forall j \neq i$

Okay now finally to answer the original question, we can notice that $f(x)=\sum_{i=1}^n f_i(x)$ satisfies the constraints. So there we have it! Lagrange interpolation:

$O(n^2)$ excluding inverse for division

Optimization:

Let's try to optimise it now! Assume that we're given $f(1), f(2), \cdots, f(n)$, how can we calculate $f(X)$ quickly?

Notice that here, $x_i=i$ and $y_i=f(i)$. Substitute!

Let's consider the numerator and denominator separately

Numerator

We can pre-calculate prefix and suffix product of x, then we can calculate the numerator (for each $i$) in $O(1)$

Denominator

So we can precompute factorials (preferably their inverse directly) then $O(1)$ calculation

So now we can calculate $f(X)$ in $O(n)$

Example 0

Find_ $\sum_{i=1}^N i^k$, $k\leq 1e6, N\leq 1e12$

Solution: Notice that the required sum will be a degree $(k+1)$ polynomial, and thus we can interpolate the answer with $(k+2)$ data points (Remember, we need $deg(f)+1$ points)

To find the data points simply calculate $f(0)=0, f(x)=f(x-1)+x^k$

Here is my code for 622F: here

Example 1

(BZOJ 3453, judge dead): Find_ $\sum_{i=0}^n \sum_{j=1}^{a+id} \sum_{k=1}^j k^x \mod 1234567891, x \leq 123, a, n, d \leq 123456789$

Example 2 (ADVANCED)

(Luogu P4463 submit here): Given $n \leq 500, k \leq 1e9$, we call a sequence ${a_n}$ nice if $1\leq a_i \leq k \forall i$ and $(a_i\neq a_j) \forall i\neq j$. Find the sum of (products of elements in the sequence) over all nice sequences._

Example 3 (ADVANCED TOO)

Problem https://www.codechef.com/problems/XETF : Find $\sum_{i=1,gcd(i,N)=1}^N i^k, N \leq 1e12, k \leq 256$

If you have any questions feel free to ask below