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:

$

then the answer that we seek effectively becomes

$

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

$

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

$

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