A more elegant solution to 1054H — Epic Convolution

Revision en5, by box, 2020-09-01 11:30:13

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English box 2020-09-01 11:30:13 96 make latex better
en4 English box 2020-09-01 03:38:45 2 (published)
en3 English box 2020-09-01 03:38:13 2
en2 English box 2020-09-01 03:34:03 10
en1 English box 2020-09-01 03:33:32 1412 Initial revision (saved to drafts)