【OI向】快速傅里叶变换(Fast Fourier Transform)
FFT的作用
在学习一项算法之前,我们总该关心这个算法究竟是为了干什么。
（以下应用只针对OI）
一句话:求多项式乘法(当然它的实际用处很多)
设多项式
)
点值表达式之间想要确定新的点值表达式,只用将y相乘即可(
我们进行这么多操作,研究了点值表示法能够对应多项式的系数表示法的事实,当然不是为了花里胡哨得到一个)！下面会在例题里贴上一个模板,然后随着做题会更新一些题目总结吧。
资料参考 ：
【学习笔记】超简单的快速傅里叶变换（FFT）（含全套证明）
单位根-百度百科
OIwiki()
百度上的傅里叶变换()
[学校的非公开资料]这个就莫得连接
例题
代码如下：