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