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.
Today I learned to make Codeforces latex look good, you need to use
\begin{align}and\end{align}When can't understand editorial
Normal people: "Help I can't understand editorial" + blog post.
box: Comes up with own solution + blog post.
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.
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.
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....
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? :)
It's well known in Chinaself advertising lol
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.