As promised, here's "interpolating multiple values" in $$$O(n\log^2 n)$$$.

Pre-req: Polynomial multiplication and modulos, basic lagrange interpolation knowledge (you can read my previous post here)

As a reminder, polynomial mod is $$$O(n\log n)$$$.

Main results:

Given $$$f(x)$$$ and $$$x_1, x_2, \cdots, x_n$$$, we can find $$$f(x_1), f(x_2), \cdots, f(x_n)$$$ in $$$O(n\log^2 n)$$$.

Given a bunch of points $$${(x_0, y_0), (x_2, y_2), \cdots, (x_n, y_n)}$$$, we can find a degree $$$n$$$ polynomial $$$f(x)$$$ such that

Why useful?

It helps you AC problems that you can't with $$$O(n^2)$$$.

It also gives you contribution on CF

Idea 1:

Since the pre-req says polynomial modulo, let's see if we can mod something to calculate some of $$$f(x_1), f(x_2), \cdots$$$ quickly.

It can be seen that we can split the set of $$$x$$$ into two halves — $$$X_0={x_1, x_2, \cdots, x_{\lfloor\frac{n}{2}\rfloor}}$$$ and the rest $$$X_1={x_{\lfloor\frac{n}{2}\rfloor+1}, x_{\lfloor\frac{n}{2}\rfloor+2}, \cdots, x_n}$$$

Now the crucial observation is that if we consider the polynomial $$$g_0(x)=\prod_{i=1}^{\lfloor\frac{n}{2}\rfloor} (x-x_i)$$$, then $$$\forall x\in X_0, g_0(x)=0$$$.

We can then see that polynomial mod helps us, as writing

Moreover, $$$\forall x\in X_0, f(x)=f_0(x)$$$ and the RHS can be calculated by polynomial mod. It is similar for $$$X_1$$$.

Now just recur and time complexity is $$$T(n)=2T(\frac{n}{2})+O(n\log n)=O(n\log^2 n)$$$.

Idea 2:

Given $$$(x_1,y_1),\cdots,(x_{n+1},y_{n+1})$$$, find a $$$(n-1)$$$-degree polynomial $$$f(x)$$$.

From my first post, we know that

Now look at that denominator $$$\prod_{j\neq i}x_i - x_j$$$. We can think of it as the whole product divided by $$$(x_i-x_i)$$$. We can't divide by zero but limits are cool:

We can write $$$P(x)=\prod_{i=1}^{n+1} x-x_j$$$, which can be calculated in $$$O(n\log^2 n)$$$ via divide and conquer. Then $$$P'(x)$$$ can also be found.

Now going back to the original expression, $$$f(x)=\sum_{i=1}^{n+1} \frac{y_i}{M'(x_i)}\prod_{j\neq i}(x-x_j)$$$. Simplifying a bit we shall write $$$v_i=\frac{y_i}{M'(x_i)}$$$ and that $$$f(x)=\sum_{i=1}^{n+1} v_i\prod_{j\neq i}(x-x_j)$$$. I swear this is not becoming a graph problem.

Now let's consider what happens if we try to divide and conquer on this term. By divide and conquering we will get the terms

,

Comparing those with the $$$f(x)$$$ we want we can notice that the product part in $$$f_0(x)$$$ is missing the later half's terms, so we can "put them back" via multiplying $$$f_0(x)$$$ by $$$M_1(x)=\prod_{\lfloor\frac{n+1}{2}\rfloor\leq j\leq n+1}(x-x_j)$$$. Doing the same for $$$f_1(x)$$$, we get that

which can then be calculated by divide and conquer.

Also note that $$$M_0(x)$$$ and $$$M_1(x)$$$ is calculated in the process of calculating the original $$$M(x)=\prod (x-x_i)$$$, so those don't require extra time.

Time complexity is $$$O(n\log^2 n)$$$ for similar reasons.

Thank you for reading the post. I'm too lazy to code it up but I still hope this blog helps someone.

I might start working through the "maths blog post recommendation" topics and post a few more blogs~