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?
# | User | Rating |
---|---|---|
1 | jiangly | 3640 |
2 | Benq | 3593 |
3 | tourist | 3572 |
4 | orzdevinwang | 3561 |
5 | cnnfls_csy | 3539 |
6 | ecnerwala | 3534 |
7 | Radewoosh | 3532 |
8 | gyh20 | 3447 |
9 | Rebelz | 3409 |
10 | Geothermal | 3408 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 173 |
2 | adamant | 164 |
3 | awoo | 161 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | SecondThread | 152 |
8 | pajenegod | 146 |
9 | BledDest | 144 |
10 | Um_nik | 143 |
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?
Name |
---|
You can do it as huffman. Each time multiply two smallest degree polynomials.
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
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).
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!
I was wondering if this problem can be solved using idea other than FFT?