Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

darkworld1's blog

How to solve This problem using FFT ?
By darkworld1, history, 4 years ago, In English

Recently I tried to solve the problem Unmerge using FFT.
After making the block array try to compute this polynomial (x^a1+1)(x^a2+1).....(x^am +1) using divide and conquer but I am getting TLE. but my complexity is n(log(n))^2. Here is my solution
please help me to optimize my solution.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Your complexity is not O(n*log^2n). That is when you multiply n 1 degree polynomials together using D&C.The polynomials you are multiplying are of degree O(n).

→ Reply