grhkm's blog

By grhkm, history, 3 years ago, In English

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

$$$\forall 0\leq i\leq n, f(x_i)=y_i$$$

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

$$$f(x)=g_0(x)\cdot Q(x)+f_0(x)$$$
$$$f(x)\equiv f_0(x)\mod g_0(x)$$$

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

$$$f(x)=\sum_{i=1}^{n+1} \prod_{j\neq i} \frac{x-x_j}{x_i-x_j}y_i$$$

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:

$$$\prod_{j\neq i}(x_i-x_j)=\lim_{x\to x_i}\frac{\prod_{j=1}^{n+1} (x-x_j)}{x-x_i}=\lim_{x\to x_i}\frac{d}{dx}(\prod_{i=1}^{n+1} x-x_j)$$$

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

$$$f_0(x)=\sum_{i=1}^{\lfloor\frac{n+1}{2}\rfloor} v_i\prod_{j\neq i,1\leq j\leq \lfloor\frac{n+1}{2}\rfloor}(x-x_j)$$$

,

$$$f_1(x)=\sum_{i=\lfloor\frac{n+1}{2}+1\rfloor}^{n+1} v_i\prod_{j\neq i,\lfloor\frac{n+1}{2}\rfloor\leq j\leq n+1}(x-x_j)$$$

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

$$$f(x)=f_0(x)M_1(x)+f_1(x)M_0(x)$$$

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~

HKOI
  • Vote: I like it
  • +85
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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))$$$.

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

You can test your implementations of polynomial evaluation and interpolation in the Library Checker:

Polynomial Evaluation

Polynomial Interpolation

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks, let's see how much time my code will run on TC2 :D

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Have you ever read the editorial of that ABC?

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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).

      My problems with editorial:
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

»
3 years ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

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$$$

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    constraints?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      $$$1 \leq l \leq r \leq \lfloor \frac{T}{x} \rfloor$$$ and $$$0 \leq x \leq T \leq 10^{18}$$$

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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}$$$

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yes, you iterate because the sum has $$$n\leq 10^6$$$ terms. I am not sure what you're asking.

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I have been looking for an interpolation guide for multiple values for a while, and this is perfect!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Glad it helps! If you are interested in any other topic I can try to help

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The most important line in this blog:

Spoiler
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The second most important thing is the post tags