Polynomial $A(x) = \sum_{j=0}^{n-1} a_j x^j$
let coeffs $A = (a_0,...,a_{n-1})$.
that $k=0,...,n-1$ $$ \begin{align} \text{DFT}(A) &= (\sum_{j=0}^{n-1} a_j e^{-\frac{2\pi i}{n} jk},...)_k \\ &= (A(\omega_n^k),...)_k,\ \ \ \omega_n^k = \exp(-\frac{2\pi i}{n} k) \end{align} $$
then consider convolution, or multiplication of $A(x)$ and $B(x)$. we wanna know coeffs of $(A*B)(x) = A(x)B(x)$.
for simplicity write $F=DFT$, notice that, $F(A) = (A(\omega_n^k))_k$, that
$$ \begin{align} F(A*B) &= ((A*B)(\omega_n^k))_k = (A(\omega_n^k)B(\omega_n^k))_k = F(A)\cdot F(B) \\ A*B &= F^{-1}[F(A)\cdot F(B)] \end{align} $$so next we need is to compute $F, F^{-1}$ in $O(n\log n)$
Before continue, note the lemmas
$$ \begin{align} \omega_{dn}^{dk} = \omega_n^k, n,k,d \geq 0 \\ \omega_n^{n/2} = \omega_2^1 = -1, n>0 \\ (\omega_n^{k+n/2})^2=(\omega_n^k)^2=\omega_{n/2}^k, n>0, \text{even} \\ \omega_n^{k+n/2} = -\omega_n^k, n\geq 0 \end{align} $$then by separate odd,even, i.e. $A(x) = A_0(x^2) + xA_1(x^2)$. combine above lemmas, get
$$ \begin{align} A(\omega_n^k) = A_0(\omega_{n/2}^k) + \omega_n^k A_1(\omega_{n/2}^k), 0\leq k < n/2 \\ A(\omega_n^{k+n/2}) = A_0(\omega_{n/2}^k) - \omega_n^k A_1(\omega_{n/2}^k), k+n/2 \geq n/2 \end{align} $$Thus, by divide and conquer solved. what about $F^{-1}$. notice that matrix form
$$ \begin{align} y=F(A) = W a \\ w_{k,j} = \omega_n^{kj}, k,j=0,...n-1\\ a = F^{-1}(y) = W^{-1}y \end{align} $$by the special form of $W$ $$ \begin{align} W^{-1} = \frac{1}{n} \bar{W}\\ v_{kj} = \frac{1}{n} \bar{w_n} ^{kj} \end{align} $$
So, just conjugate and divided by $n$. then same method sovlable.
let $\alpha$ replace $\omega_n$ in integer field.
DFT require $$ \begin{align} \sum_{j=0}^{n-1} \alpha^{kj} = 0, k=1,...,n-1 \end{align} $$ and $\alpha^n=1, \alpha^k \neq 1, k=1,...,n-1$ is sufficient
if $n$ is power of $2$, $\alpha^{n/2} = -1$ is sufficient
if we get the $\alpha$ on $Z_p$, then $p=c2^k+1$, that $\alpha^c$ can be the $\alpha'$ to express conv length $\leq 2^{k-1}$
For in place NTT, leaves' addr. are bit-reversed. (NEED rigorous proof)
and if for $F^{-1}$, one way is calc $\alpha^{-1}$, for each iter. Here is another way. Notice the matrix form. suppose $a$ divided by $n$, then we reverse $[a_1,...,a_{n-1}]$. by the fact $\alpha^{k(n-j)} = \alpha^{-kj}$, thus result is exactly $F^{-1}$.
we wanna know $BA \equiv 1 (\mod x^n)$. by the step that double $B$'s size, with init $B_0=1/A_0$. wlog write $B_1$ repre. $B_n$, $B_2$ repre. $B_{2n}$. that $$ \begin{align} & (B_1 A - 1)^2 \equiv 0 (\mod x^2) \\ \Rightarrow & B_2 = 2B_1 - B_1^2 A (\mod x^2) \end{align} $$ note, in impl. $B_1^2A$ has $B_1(\mod x)$ part in there since $B_1A \equiv 1(\mod x)$. aka, $(\mod x)$ part remain $B_1$, actually, we only need modify the higher order part, $-B_1^2 A ([x\leq..<x^2])$
also, the double size technique $$ \begin{align} & (B_1^2 - A)^2 \equiv 0 (\mod x^2) \\ \Rightarrow & B_2 = \frac{1}{2} [B_1 + A B_1^{-1}](\mod x^2) \end{align} $$ again, notice the old part $B_1$ shall remain, we can only modify new part in impl. and careful $B_0^2=A_0$ when $\neq 1$
$\log P = \int \frac{P'}{P}$
double step, $B_2 = B_1(1 + A - \log B_1)$
Hadamard transform, def, with $H_0 = 1$ $$ \begin{align} H_m = \frac{1}{\sqrt{2}} \begin{bmatrix} H_{m-1} & H_{m-1} \\ H_{m-1} & -H_{m-1} \end{bmatrix} \\ (H_m)_{i,j} = \frac{1}{2^{m/2}} (-1)^{\langle i, j \rangle_b} \end{align} $$ where $i,j= 0,1,..,2^m-1$ and $\langle .,.\rangle_b$ is bitwise dot product, aka
__builtin_popcount(i&j)when do fwht, don't need bit reversal and generator. besides, there is good property $H_m^2= I$. One can easy show $H_1^2 = I$ by direct compute or quantum tech. $H_1 = |+\rangle \langle 0| + |-\rangle \langle 1| $. then by induction. $H_m = H_1 \otimes H_{m-1}$. that $H_m^2 = H_1^2 \otimes H_{m-1}^2 = I$. which means we can do $H^{-1}$ by direct do $H$ !
note in impl. we often omit $2^{n/2}$, that use $H' = 2^{n/2}H$. so when do inverse, we need divide by $2^n$.
still, we can do multiply by $A*B = H^{-1} [H(A) \cdot H(B)]$. note $\cdot$ is element-wise mult.
also, suprisingly, for solving equation $A*B = C$, if we put $H$ on each side, that
$H(A) \cdot H(B) = H(C)$, since $\cdot$ is element-wised, thus we can get $A = H^{-1} [H(C) / H(B)]$, element-wise.
Note. for $\sum_i B_i = 0$, aka, not linear indep. the solution may has many, notice that $R = (1,1,...,1)$, that $R*B = 0$. e.g. agc034f.
so we can minus arbitral still solution, but according specific condition, we can get the right one.
https://cp-algorithms.com/algebra/fft.html
https://cp-algorithms.com/algebra/polynomial.html#toc-tgt-4
https://en.wikipedia.org/wiki/Discrete_Fourier_transform#Polynomial_multiplication
https://en.wikipedia.org/wiki/Discrete_Fourier_transform_(general)
https://codeforces.com/blog/entry/43499
https://codeforces.com/blog/entry/48798
https://crypto.stanford.edu/pbc/notes/numbertheory/gen.html
https://csacademy.com/blog/fast-fourier-transform-and-variations-of-it
In [ ]: