My last blog was a bit too esoteric
This blog assumes that you can do a basic convolution (e.g. FFT). After I saw that many people did not know how to do Chirp Z-Transform with arbitrary exponents fast from my blog 9 weeks ago I decided to shitpost write a short tutorial on it.
Let's say we have a polynomial $$$P(x)$$$, such that
Now, let's say we have $$$c$$$ and $$$m$$$, and we want to find $$$P(c^0),P(c^1),P(c^2),\dots,P(c^m)$$$. Let $$$b_j=P(c^j)$$$. Consider the implications of having $$$x$$$ as such a form:
Tinkering around with different expressions for $$$ij$$$, one finds that $$$ij=\frac{(i+j)^2}{2}-\frac{i^2}{2}-\frac{j^2}{2}$$$. This means that
Hence we can find $$$b_j$$$ from the difference-convolution of $$$a_ix^{-\frac{i^2}{2}}$$$ and $$$x^{\frac{i^2}{2}}$$$. However, in many cases — especially when working under a modulus — we can't find the $$$x^{\frac{i^2}{2}}$$$ as $$$i$$$ may be odd. We use a workaround: $$$ij=\binom{i+j}{2}-\binom{i}{2}-\binom{j}{2}$$$. Proof:
Modifying our formula a bit, we get
As for implmentation details, notice that
Define $$$c_i=a_{n-i}x^{-\binom{n-i}2}$$$; $$$d_i=x^{\binom i2}$$$. We hence have
(the second through definition of convolution)
You can test your implementations here, mod 998244353 and here, mod 10^9+7, although note that the second one is both intense in precision and constant factor.
This method can be used to cheese 1184A3 - Хайди изучает хеширование (сложная) and 1054H - Эпическая свёртка, and is also a core point in 901E - Циклический шифр.
