對于兩個n階多項式的乘法，如果模擬做的話復雜度為O(n^2)，利用快速傅里葉變換可以把復雜度降到O(nlogn)。
　　多項式有兩種表示：系數形式和點值表示。如果把兩個多項式寫成點值形式，那么相乘的復雜度就是O(n)的。FFT的基本思想就是通過把系數形式化成點值形式，相乘之后再化回來，使得復雜度降到O(nlogn)。具體就是先通過巧妙地選取n個復數單位根，利用復數的一些非常好的性質求得DFT，把這一步的復雜度降到O(nlogn)，然后將得到的點值相乘后，利用插值再變換成系數形式。插值的過程居然和求DFT的過程驚人的相似，復雜度依然為O(nlogn)。
　　在實現的時候基本參照算法導論，感覺遞歸不太好寫，就寫了個迭代的。N久不用復數了，連基本運算都忘了，導致實現的時候出了一堆錯，后來好不容易寫好了，結果卻一點都不靠譜。查了好久才發現，初始w是1的時候，我把實部和虛部都設成1了，囧。實際上虛部應該是0。改完后發現多項式的表示又出了問題，后來發現我把系數的順序寫反了。然后利用這個做了HDU 1402，就是高精度乘法。WA了幾次，很抓狂。后來寫了一個程序跑了一組極限數據，居然掛了。仔細觀察后發現是精度的問題。因為FFT中間運算過程都是浮點數，但是最后要輸出整數，取整的時候舍入精度出了問題，加了1e-3之后過了。
　　還有一道比較巧妙的FFT的題目，SRM 436 DIV 1 1000pt，做的時候開始Z0忘記取模了，結果還以為是模板的問題，找了很長時間才發現。做題還是要細心啊。