box's blog

A more elegant solution to 1054H — Epic Convolution
By box, history, 4 years ago, In English

1054H - Epic Convolution

When I first saw this problem, I did not understand the editorial at all, so I decided to come up with my own solution. After noticing the extremely small modulo, I tried using it to my advantage.

First of all, $$$i^2$$$ and $$$j^3$$$ are purely random functions. They are really just a generic function that maps integers to numbers in the range $$$[0,MOD-2]$$$. Here we can take them modulo $$$MOD-1$$$ because of Fermat's little theorem and how the given mod, $$$490019$$$, is prime.

Call the function for array $$$a$$$ as $$$f$$$, and the function for array $$$b$$$ as $$$g$$$. Notice that if we "relabel" the arrays $$$a$$$ and $$$b$$$ into arrays $$$a'$$$ and $$$b'$$$ respectively such that $$$a'$$$ and $$$b'$$$ satisfy the following equalities:

$$$\begin{align}a'_i=\sum_{f(j)=i}a_j,b'_i=\sum_{g(j)=i}b_j\end{align}$$$

then the answer that we seek effectively becomes

$$$\begin{align}\sum_{i=0}^{MOD-2}\sum_{j=0}^{MOD-2}a'_ib'_jc^{ij}\end{align}$$$

Now, if we factor out $$$a'_i$$$, this becomes

$$$\begin{align}\sum_{i=0}^{MOD-2}a'_i\sum_{j=0}^{MOD-2}b'_jc^{ij}\end{align}$$$

Notice how the internal part is effectively evaluating the generating function of $$$b'$$$ at point $$$c^i$$$. Since $$$b'$$$ is a finite sequence of length $$$MOD-1$$$ evaluating it quickly at a points of the form $$$c^i$$$ is doable with Chirp-Z transform. The answer is now reduced to

$$$\begin{align}\sum_{i=0}^{MOD-2}a'_iB'(c^i)\end{align}$$$

which is computable in $$$O(\text{mod}\log\text{mod})$$$ time.

  • Vote: I like it
  • +87
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 3   Vote: I like it +31 Vote: I do not like it

Today I learned to make Codeforces latex look good, you need to use \begin{align} and \end{align}

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +73 Vote: I do not like it

When can't understand editorial

Normal people: "Help I can't understand editorial" + blog post.

box: Comes up with own solution + blog post.

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I found it interesting that your implementation of CZT computes values at powers of an arbitrary point. I've only seen it being used to compute values at powers of a square. The solution to this problem using CZT is described in this comment, but it uses more convolutions because of aforementioned issue with a square root and hence is much slower. I've also seen CZT implementation from another respectable coder 56657031, and it explicitly asks for the square root.

Thank you for sharing both your clear approach and powerful implementation. Perhaps adamant, whose lectures on FFT are surely valued by CP community, wants to see this.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Hmm, I don't see anything new about CZT here. I mean, it can be used to calculate values at arbitrary points and the method is mentioned in my comment to which you've provided the link. And the author of this entry doesn't say in which way they used CZT to compute values at arbitrary values. Other than that I think that solution is effectively the same as mine. I mention primitive root $$$g$$$ for some reason in the comment but clearly it may be done with $$$c$$$ instead of it as well.

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

      Ah, it's just a different way of separating $$$ij$$$.

      In normal CZT, you use $$$ij=\frac{(i+j)^2}{2}-\frac{i^2}{2}-\frac{j^2}{2}$$$, but this only works when $$$c$$$ has a square root modulo MOD or you only want even powers. There is a different expansion, though: $$$ij=\binom{i+j}{2}-\binom{i}{2}-\binom{j}{2}$$$, which works for all kinds of $$$c$$$. Don't ask me who thought of this expansion....

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Nice. I knew that it's possible to reduce odd powers to even powers, but this formula is hilarious. Really, how did you learn about it though? :)

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

          It's well known in China

          → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    self advertising lol

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's even easier to compute the convolution of $$$a'_i c^{\binom{i}{2}^{-1}}$$$ and $$$b'_i c^{\binom{i}{2}^{-1}}$$$. The answer is the sum of convolution coefficients, i-th coefficient multiplied by $$$c^{\binom{i}{2}}$$$. It would be a better solution to the general problem of finding the sum of $$$a_i b_j c^{ij}$$$, but that doesn't matter in this particular case as we have polynomials of a degree up to $$$MOD - 2$$$ anyway.

Thank you for the plenty of your educational blogs.

→ Reply