封面来源

Pixiv にこまき-44342920

[toc]

前置芝士

1.卷积（其实没啥用）

https://www.bilibili.com/video/BV1JX4y1K7Dr

正文

1.点值表达式

多项式，可以转换为另一种表示方法，即将转为函数

2.多项式乘法

我们知道，两个次多项式相乘的复杂度为，完全不能满足某些题的要求，所以考虑优化。那如果用点值表达式来做乘法呢？

复杂度只有!!!

那么总结一下算法的大体思路：

1.将多项式转为点值表达式

2.计算多项式乘法

3.把结果转回系数表达式

但是转换的过程仍然是，所以还需要优化才行.

3.复数优化

根

定义

若，则nnn$个。

而复数单位根在复平面上模都为，所以这个单位根分布在单位圆上

考虑欧拉公式：

取,则可推出$$ e^{2\pi i}=1=\omega^n$$

此时的单位根称作主次单位根，记作

在下文中，我们记为n次单位根。

性质

单位根有三个性质：

1.对，

证明:

2.对，$$ (\omega_nk)2=\omega_{\frac{n}2}^k $$

证明:

直接展开

3.对，

证明：

等比数列求和公式可得

FFT

DFT:离散傅立叶变换

对多项式，取其在的值，将其转换为点值表达式.这个过程就是DFT。

假设是的幂，即使它不是的幂，我们也可以通过向高次幂补0来添加。

FFT优化DFT

考虑上文中的多项式，重定义为次数为的小多项式，，发现，然后就将大问题化为了两个小问题，即求和，那么，上面那个复杂度为就可以简化为$O(\log n)了。

对于另一边，我们可以通过

得到

。

这个操作叫做蝴蝶变换

IDFT:逆离散傅立叶变换

这个其实就是将FFT再搞一遍。

迭代版FFT

但是，由于上面的过程如果写递归的话会有非常大的常数，所以还要进行一些修改。

FFT分治的过程可以简单地描述一下：

发现其实可以反向迭代的。

1.取出儿子节点，算出DFT

2.用这一步的DFT替换之前的

3.直到迭代到根节点为止,否则重复1

代码

cpp
inline void Init(int lim){
    FOR(i,0,lim)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
}
inline void FFT(node *s,int lim,double flag){
    for(register int i=0;i<lim;i++) if(i<r[i]) swap(s[i],s[r[i]]);
    for(register int i=1;i<lim;i<<=1){
        node f(cos(pi/i),flag*sin(pi/i));
        for(register int j=0;j<lim;j+=(i<<1)){
            node t(1,0);
            for(register int k=0;k<i;k++,t=t*f){
                node nx=s[j+k];
                node ny=t*s[i+j+k];
                s[j+k]=nx+ny;
                s[i+j+k]=nx-ny;
            }
        }
    }
}

撒花花~~

★,°:.☆(￣▽￣)/$:.°★ 。