Fast Fourier Transform, Algorithms, Pattern Matching, Convolution, Combination Sum.
r(x) which is the product of p(x) and q(x) for each x equals to the 2n roots of unity. Computing the R vector has complexity of O(nlogn) because both the DFTs has a complexity of O(nlogn). Using the 2n roots of unity, the X matrix is such that: The good thing about this matrix is that the inverse