Fast Fourier Transform, Algorithms, Pattern Matching, Convolution, Combination Sum.
follows, this is assuming that n is even. Then we can write p(x) using the above 2 polynomials as: In terms of the (2n) roots of unity, for the k-th root, we have: Similarly for the (k+n)-th root, we have: Thus, once we compute p_even(w²k) and p_odd(w²k) for k=0 to n-1, we can compute p(w^k) for k