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
Practice question:
CF 622F (Example 0)
- Thank you demoralizer for telling me this :)
Luogu P4463 (Example 2)
Codechef XETF (Example 3)
Not in order of difficulty:
SPOJ HARD which is harder than EXTREME
Atcoder ARC33D (Japanese)
Unfortunately you can't get full score, but you can get up to subtask 4
Still not trivial, do first 3 subtasks would give insight
For full solution please wait for my next blog (next year)
