How to calculate the expected number of operations of the editorial solution for 444B DZY Loves FFT?

Revision en2, by oos1111, 2018-02-28 16:48:30

I got stuck at the problem 444B DZY Loves FFT and I read the editorial.
And I really don't understand how to calculate the expected time complexity of the whole algorithm. How to prove that the worst expected number of operations is around ten million? Please help!

Tags probability

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English oos1111 2018-02-28 16:48:30 0 (published)
en1 English oos1111 2018-02-28 16:47:42 461 Initial revision (saved to drafts)