munna_jazbaati's blog

By munna_jazbaati, history, 7 years ago, In English

How to multiply n polynomials efficiently.

n <= 10^5 And the sum of degrees of all the polynomials <= 10^5

Any n log^2n or better will work? Any ideas?

  • Vote: I like it
  • +7
  • Vote: I do not like it

| Write comment?
»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

You can do it as huffman. Each time multiply two smallest degree polynomials.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    I had exact same idea. It's slightly like merging sets. I can't prove how it is n log^2 n though?

    Anyways, I required this in a recent contest on Codechef. Anyone can see the problem at : https://www.codechef.com/COOK75/problems/COUNTWAY

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Multiplying two polynomials of maximum degree n using FFT is O(n log n). Represent the multiplications done by the huffman style algorithm as a binary tree. You can prove that the height of that tree is at most log n. The sum of degrees at each level of the tree is at most n. Because (x -> x log x) is convex, you can bound the total cost by O((n log n) log (n log n)) = O(n log² n).

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I used this technique during the contest to get ac but can someone explain how this solution gets ac even without this technique? https://www.codechef.com/viewsolution/11936211

      Thanks!

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was wondering if this problem can be solved using idea other than FFT?