Fast Fourier Transform, Algorithms, Pattern Matching, Convolution, Combination Sum.
for evaluating the R vectors, we are going to use the (2n) roots of unity, which are given by: Thus we can write p and q for the k-th root of unity as: One intereseting property of the (2n) roots of unity is that: Similar to our previous DFT post, let us define 2 polynomials p_even and p_odd as