一道 FFT 相关的题

[letianqiu]

K 个多项式，这 K 个多项式最高次数的和是 S。如何在 O(SlogSlogK)内求出这 K 个多项式的乘积。
O(KSlogS)很容易，只需要对每个多项式做 FFT, O(SlogS)，然后依次逐点相乘，最后 IFFT。总的复杂度就是 O(KSlogS)。但是如何把 K 变成 logK 就想不到了，尝试两两相乘，但是复杂度并不能降低。

[wodesuck]

两两相乘复杂度是 O(SlogSlogK)的。
两个 degree 为 a 和 b 的多项式相乘，是 O((a+b)log(a+b))。考虑做第一次两两相乘，P1 乘 P2，P3 乘 P4，P5 乘 P6...，复杂度就是 O( (d1+d2)log(d1+d2) + (d3+d4)log(d3+d4) + ...) < O((d1+d2+d3+...)logS) = O(SlogS)。乘完后 degree 和不变，下一次两两相乘的复杂度还是 O(SlogS)，一共要做 logK 趟。

[zjuturtle]

可以参考一下我的博客
https://zjuturtle.com/2017/12/26/fft/