Блог пользователя darkworld1

How to solve This problem using FFT ?
Автор darkworld1, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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).

→ Ответить