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~
Nice post, but I think the complexity of calculating $$$P(x) = \prod\limits_{j = 1}^{n+1} (x - x_j) $$$ is $$$O(n*log^2n)$$$ and not $$$O(n*log(n))$$$.
You right, thank you!
You can test your implementations of polynomial evaluation and interpolation in the Library Checker:
Polynomial Evaluation
Polynomial Interpolation
Thanks, let's see how much time my code will run on TC2 :D
Nice post, thanks. Here if one more problem on this topic to your list. But I don't get why in discussion there seam to be a consensus with rgnerdplayer that polynomial degree is (K + M) while in your example#0 (part 1) you have same looking Sum(i^k) polynomial (just without (binomial) coefficients) and assert it's degree is (K + 1). Would be grateful if someone would explain why my assertion is wrong.
Have you ever read the editorial of that ABC?
Yes, I read it, but I couldn't get a lot from it starting part 3. And some things after — just seamed unnecessary (but judge gives WA without them).
Part 3 has a few things that are strange for me:
When we move from $$$T_K(n)=n^K - (n-1)^K$$$ to $$$\displaystyle \sum_{n=0}^N T_{K+1}(n) = N^{K+1}$$$ — since n starts from 0, it seams we either lost $$$-(0-1)^k$$$ or sum should be from 1: $$$\displaystyle \sum_{n=1}^N T_{K+1}$$$
Now in this part: $$$\displaystyle \sum_{n=0}^N T_{K+1}(n) = \sum_{n=0}^N Kn^K + (\text{polynomial in }n\text{ of degree }(K-1))$$$ we've lost $$$n^{K+1}$$$ but somewhere we found $$$K$$$ coefficient in sum. Overall I agree that $$$ \sum_{n=1}^N i^K = (\text{polynomial in }n\text{ of degree }K+1)$$$ but how they got it here I don't understand.
And lastly this thing in part 4:
$$$\begin{eqnarray} f(N, m+1) &=& \sum_{n = 1} ^ N f(n, m) \newline &=& \sum_{n=1}^N (\text{polynomial in }n\text{ of degree }(m+K)) \newline &=& (\text{polynomial in }N\text{ of degree }(m+K+1)), \end{eqnarray}$$$
Yes, I agree. I didn't get how they prove it, but let's say that sum of polynomial of degree N can be expressed as polynomial of degree (N+1). But why do we need it at all? Isn't sum of polynomial of degree N is itself a polynomial of degree N? I'm sure it is. So why do we need (K + M) thing?
The simplest way to explain would be to draw a table and look at some special cases.
When M=0 the value f(N, 0) is of degree K
When M=1, f(N, 1) = deg (K+1) instead by sum of power
In addition, N = 1 yields f(1, M) = 1^K = degree 0 (constant)
Now f(N, M) = f(N, M — 1) + f(N — 1, M) = f(1, M) + $$$\sum_{i=2}^{M} f(i, M-1)$$$, just recursive until you get a base case. Then it should be obvious that the degree is (K+M), either by induction or other methods.
Nice post and very beautiful math trick
But I have a question, whether this function can do the trick:
$$$f(l, r, x) = \overset{r}{\underset{k = l}{\LARGE \Sigma}} \Large \lfloor \normalsize \frac{T}{kx} \Large \rfloor$$$
constraints?
$$$1 \leq l \leq r \leq \lfloor \frac{T}{x} \rfloor$$$ and $$$0 \leq x \leq T \leq 10^{18}$$$
Ofc you can't solve it with lagrange interpolation since there's like nothing related to polynomials with this function. However, a hint I would give is that T//(k*x) == (T//x) // k so you eliminate one variable, and the rest is the prefix sum of floor division which I believe can be solved in approximately O(n^(1/3)) — you might want to refer to SPOJ DIVCNT1 or something. Hope this helps :/
PS O(sqrt(n)) won't work since your constraint is huge
Yes, thank you about that
Also is it possible to calculate
$$$f(n, x) = \overset{n}{\underset{k = 1}{\LARGE \Sigma}} \Large \lfloor \normalsize \frac{a[k]}{x} \Large \rfloor$$$
for $$$n \leq 10^6$$$ and $$$0 \leq x, a_i \leq 10^{18}$$$
Yes, you iterate because the sum has $$$n\leq 10^6$$$ terms. I am not sure what you're asking.
I have been looking for an interpolation guide for multiple values for a while, and this is perfect!
Glad it helps! If you are interested in any other topic I can try to help
The most important line in this blog:
It also gives you contribution on CF
The second most important thing is the post tags