Fast Fourier Transform, Algorithms, Pattern Matching, Convolution, Combination Sum.
does fourier transform help us improving the time complexity from O(n²). Let us rewrite the multiplication equation between p and q and denote by r. Now evaluate r at 2n different points x: Representing the above equations in matrix notation, we get: In order to obtain the column vector C, we need