Fast Fourier Transform, Algorithms, Pattern Matching, Convolution, Combination Sum.
Q(x), then the coefficients of x^j gives the number of possible ways to get the sum j (or frequency of sum j). As seen above, we can compute the coefficients of the multiplication in O(MlogM) time complexity using the FFT algorithm. Following is the python implementation for the FFT solution. def