On Lagrange interpolation and its application

Preface

I've been doing for many years NOI The original title is , And then it did [NOI2019] robot , I was surprised to find that I didn't learn Lagrange interpolation ！

There was an inserted question in the previous provincial topic （[ Provincial election joint examination 2022] Tree filling ）, But in $\mathrm{O}\mathrm{n}\mathrm{e}\mathrm{I}\mathrm{n}\mathrm{D}\mathrm{a}\mathrm{r}\mathrm{k}$ Sterling inversion is used under the recommendation of . Actually, pulling and inserting is very simple , And it is more suitable to do things like filling trees 、 Robots are like this DP Optimize the topic .

brief introduction

Stick to others
In numerical analysis , Lagrange interpolation is based on French 18 Century mathematician Joseph · A polynomial interpolation method named by Lagrange . If you observe a physical quantity in practice , The corresponding observations are obtained in several different places , Lagrange interpolation can find a polynomial , It just takes the observed value at each observation point . The above polynomial is called Lagrange （ interpolation ） polynomial .

Lagrange interpolation

as everyone knows , Give a $n$ Polynomial of degree $n+1$ A point value can uniquely find this polynomial , A simple solution is to list $n+1$ Equation and then use Gauss elimination , Complexity $O(n^3)$, It is often accompanied by the problem of accuracy .

Lagrange interpolation can be used in $O(n^2)$ Find the polynomial with enough accuracy in time .

Directly up Lagrange interpolation formula ：
$$f(x)=\sum _{i=0}^n{y}_i\prod _{j\ne i}\frac{x-x_j}{x_i-x_j}$$ This formula is very clever , Because you can find that it can just get all the point values , And the maximum number is $n$.

Using this formula to directly find polynomials is also $O(n^3)$（ It's slower than high consumption ）, But it can be optimized ！

We can find out $g(x)={\prod }_{i=0}^n(x-x_i)$, Then enumeration $y_i$ First of all $O(n)$ Calculate the following ${\prod }_{j\ne i}\frac{1}{x_i-x_j}$, And then because of $g(x)$ It was not cut off when calculating , So single $(x-x_i)$ Divisibility $g(x)$, direct $O(n)$ Recursively find ${\prod }_{j\ne i}(x-x_j)$ that will do （ Pay attention to special judgment $x_i=0$）. In this way, the total complexity is reduced to $O(n^2)$.

Find the value of a single point

Here, to find the value of a single point means to give $k\notin \{x_i|0\le i\le n\}$, We need to ask for $f(k)$.

Obviously, we can directly find $f(x)$ Then bring in the solution , But when our goal is only to find $f(k)$ when , Doing so is cumbersome and inefficient .

We might as well bring Lagrange interpolation formula directly ：
$$f(k)=\sum _{i=0}^n{y}_i\prod _{j\ne i}\frac{k-x_j}{x_i-x_j}$$ Because it is no longer a polynomial , So we can $O(n)$ Find all in time ${\prod }_{j\ne i}(k-x_j)$, Then enumerate each time $y_i$ Just ask ${\prod }_{j\ne i}\frac{1}{x_i-x_j}$ 了 . Although still $O(n^2)$, But it reduces the constant and is simpler .

O(n) Find the value of a single point

Or just ask $f(k)$.

In most topics applied to pull and insert , this $n+1$ A point value satisfies subscript continuity , Or equidistant , namely $x_1-x_0=x_2-x_1=...=x_n-x_{n-1}$.

At this time, we can do some pretreatment （ For example, when the spacing is equal to 1 When , You need to preprocess the inverse of factorial ）, Then you can do it once $O(1)$ Find out ${\prod }_{j\ne i}\frac{1}{x_i-x_j}$.（ Special attention should be paid to symbols ）

application

There's a classic question ： Calculation ${\sum }_{i=1}^n{i}^k$. This problem can obviously be inversed by Stirling $O(k\log k\sim k^2)$ solve .

As we all know, this thing is about $n$ Of $k+1$ Sub polynomial , So we can $O(k)$（ Ignore fast exponents , You can also use a linear sieve ） Before finding out $k+2$ A point value , Then use the above method $O(k)$ Pull and insert $n$ Answer at , In this way, the total complexity is only $O(k)$.

More practical scenarios are in some DP In question , For example, you need to ask $m$ individual DP Value to transfer , But you find this $m$ A function with a point value is a function with a small number of times $n$ Sub polynomial , Then you can just ask for the front $n+1$ individual DP value , The rest can be pulled and inserted .

Generally, it needs inductive proof to see that this is a polynomial , But I will not