快速傅里叶变换(FFT)

这一篇博客估计要写好久了(QwQ)。
粘几个链接。。
自为风月马前卒
Miskcoo’s Space
算法导论第30章《多项式与快速傅里叶变换》
一句话理解FFT,就是直接用系数表达法完成多项式乘法效率低下,所以通过系数->点值->点值相乘->系数的方法完成,其中过程的效率分别是O(nlogn),O(n),O(nlogn),相应的可以去算导上看,非常棒。并且,正是因为通过运用2n次单位根并利用其性质,来达到O(nlogn)的复杂度。
例题:[ZJOI2014]力(这相当于裸题了,只是有一个小技巧)
QQ图片20180305145310.png
显然,我们可以构造和i-j相关的函数c。
QQ图片20180305145402.png
则,我们可得
QQ图片20180305145439.png
这可以直接用fft吗?不行。因为i-j可能是负数。所以我们要做一个转换(设Cn+i=ci,Bn+i=bi),则:
QQ图片20180305145614.png
这就是一个真的卷积形式,可以用fft了。然后最后的答案是b[0~n-1]=B[n~n+n-1]。

CODE

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

w

Connecting to %s