Fast Fourier Transform, Algorithms, Pattern Matching, Convolution, Combination Sum.
= 0 to n-1, also we can re-use the same p_even and p_odd values to compute p(w^k) for k = n to 2n-1. This is same as computing the DFT of p(x) using Fast Fourier Transform. Similarly for q(x) we evaluate the DFT of q(x) for x equals to all the (2n) roots of unity. Thus, we can compute the values of