FFT

作者：陈犇

FFT教程

标签（空格分隔）： 数学 ACM

---

FFT是什么？

FFT是快速傅里叶变换(fast Fourier transform)的简称。在ACM领域主要是用来快速求解多项式乘法的算法，
在信号领域也有很大用途

---

基础知识

1. 卷积
   举个例子，给你两个向量 a(a0,a1,a2),b(b0,b1,b2)
   a和b的卷积就是(a0∗b0,a1∗b0+a0∗b1,a2∗b0+a1∗b1+a0∗b2,a1∗b2+a2∗b1,a2∗b2)
   即可以看作两个多项式A(x)=a0+a1x1+a2x2和B(x)=b0+b1x+b2x2相乘。
   所以卷积就可看做多项式乘法。那些形如ck=Σki=0aibk−i卷积的就可以类比成多项式乘法 ，就可通过fft快速求解。

2. 多项式

   • 多项式有两种表达形式
   • 一种是系数表达形如A(x)=Σn−1i=0aixi
   • 另一种是点值表达， 形如(x1,y1),(x2,y2),(x3,y3)...(xm,ym), 且m>=n
   • 多项式的点值表示和插值表示可以互推
3. wn=e2πi/n
   
   • wn/2+kn=−wkn
   • w2kn=wkn/2
   • Σn−1j=0wjkn=(k%n==0)?n:0

---

傅里叶变换的原理

在傅里叶变换里面系数表达和点值表达如何互推？

一个暴力点的方法
系数表达->点值表达 yk=Σn−1i=0aiwkin
点值表达->系数表达 ak=1/n∗Σn−1i=0yiw−kin
证明看黑板
所以不论是系数表达推点值表达还是点值表达推系数表达方法都一样

如何快速的求出上面的式子呢
假设 A(x)=a0+a1x+a2x2+...+an−1xn−1
那A(x)=(a0+a2x2+a4x4+...+an−2xn−2)+(a1x+a3x3+..+an−1xn−1)
令A0(x)=a0+a2x+a4x2+...+an−2xn/2−1,A1(x)=a1+a3x+a5x+...+an−1xn/2−1
则A(x)=A0(x2)+xA1(x2)
那么就可以用A0(w0n/2),A0(w1n/2)...A0(wn/2−1n/2) 和 A1(w0n/2),A1(w1n/2)...A1(wn/2−1n/2
得出A(w0n),A(w1n)...A(wnn−1)

所以可以采用非递归分值的办法求解FFT

分治图

void ntt(ll* a, int n, int t) {
    rep(i, 0, n) {
        int rv = rev(i,n);
        if(i<rv) swap(a[i], a[rv]);
    }
    ll g=1;
    if(t==1) g=3;
    else g=inv[3];
    for(int m=2; m<n+1; m<<=1) {
        ll wm= mypow(g, (MOD-1)/m);
        int mid=m>>1;
        for(ll *p=a; p<a+n; p+=m) {
            ll w=1;
            rep(i, 0, mid) {
                ll t=w*(p[mid+i]);
                p[mid+i] = p[i]-t;
                p[i] = p[i]+t;
                w = w*wm%MOD;

                p[i]=%MOD, p[mid+i]%=MOD;
            }
        }
    }
    if(t==-1) {
        rep(i, 0, tn)
            a[i]=a[i]*inv[n]%MOD;
    }
}
void fft(ll *a, ll* b, int n) {
    int tn=MAXN;
    while(tn/4>=n) tn>>=1;
    ntt(a, tn, 1);
    ntt(b, tn, 1);
    rep(i, 0, tn)
        a[i] = a[i]*b[i]%MOD;
    ntt(a, tn, -1);
}

NTT wn=g(P−1)/n%P

• 一些更高级的操作或例题
  https://wenku.baidu.com/view/20c234cf581b6bd97f19eaea.html
  http://blog.csdn.net/samjia2000/article/details/65661468
  https://www.cnblogs.com/candy99/p/6738010.html