I am trying to solve this question: http://sharecode.io/contests/problem/61839756/F
I used the fft implementation of stanford’s team notebook: http://stanford.edu/~liszt90/acm/notebook.html#file16
Here is my code: link
I am getting wrong answer on it. I have tested lots of different tests on it but I couldn’t find the error. Now I am not sure what to do. Could it be because of double’s error or is it something else? If that’s the case could anyone provide an implementation of real FFT?
a brief description of the problem: Given the coefficients of two polynomials calculate the coefficients of their multiplication.