FFT快速傅里叶变换 [模板]

文章目录

• $FFT的作用$
• $FFT的前置$
• 单位根
• $FFT的内容$
• $结论:$
• $FFT的实现$
• $蝴蝶变换$
• $FFT的应用$
• $FFT 魔改-> NTT$

• $FFT的作用$

$O(logN)$ 计算两个多项式的卷积 .

• $FFT的前置$

1. 单位根

$单位根为在单位圆上的点.\ 横坐标为实部, 纵坐标为虚部的复数 .$

如图, 图中落在 $x$ 正半轴的那个红点称为 $w_{n}^0$, 被称为 $n$ 次单位根, 其余的点从 $w_n^0$ 逆时针顺序分别称为 $w_n^1, w_n^2...w_n^7$ .

从图中可以 感性 得到 单位根 的 $2$ 个性质 $downarrow$

• $性质1:$ $w_{2n}^{2k}=w_n^k$

• $性质2:$ $w_n^{k+frac{n}{2}} = -w_n^k$

---

下面给出 理性 证明, 首先要知道

$欧拉公式:w_n^k=cos(k*frac{2 pi}{n}) + i*sin(k*frac{2 pi}{n})$

其中 $i$ 为 $sqrt{-1}$ .

---

• $性质1:$ $w_{2n}^{2k}=w_n^k$
  $证:$
  $w_{2n}^{2k} = cos(2k*frac{2 pi}{2n}) + i*sin(2k*frac{2 pi}{2n})=w_n^k$

---

• $性质2:$ $w_n^{k+frac{n}{2}} = -w_n^k$
  $证:$
  $w_n^{k+frac{n}{2}}\ =cos[(k+frac{n}{2})*frac{2pi}{n}]+i*sin[(k+frac{n}{2})*frac{2pi}{n})]\ =-w_n^k$

---

• $FFT的内容$

• 有多项式 $A(x)=a_0 + a_1x+a_2x^2+dotsi+a_{n-1}x^{n-1}$

$ecause 一个n次多项式可以被n+1个点唯一确定.$
$herefore 将 w_n^0 dotsi w_n^{n-1} 代入可以确定该多项式.$

这里默认 $n$ 为 $2$ 的整数次幂, 所以 $n-1$ 为奇数 .

• 对于上方多项式 $A(x)$, 将其 系数 按奇偶分开, 得 $↓$
  $A(x) = (a_0+a_2*x^2+ dotsi + a_{n-2}*x^{n-2})+(a_1*x+a_3*x^3+ dotsi + a_{n-1}*x^{n-1})$
  $设$
  $A_1(x)=a_0+a_2x+a_4x^2+ dotsi+a_{n-2}x^{frac{n}{2}-1}\ \ A_2(x)=a_1+a_3x+a_5x^2+ dotsi+a_{n-1}x^{frac{n}{2}-1}$
  $则$
  $A(x)=A_1(x^2)+x*A_2(x^2)$

---

$代入 w_n^k (k < frac{n}{2}) 得$
$A(w_n^k) = A_1(w_n^{2k})+w_n^kA_2(w_n^{2k})=A_1(w_{frac{n}{2}}^k)+w_n^kA_2(w_{frac{n}{2}}^k)$

$代入 w_n^{k+frac{n}{2}} 得$
$A(w_n^{k+frac{n}{2}})\ \=A_1(w_n^{2k+n})+w_n^{k+frac{n}{2}}A_2(w_n^{2k+n})\ \ =A_1(w_n^{2k}*w_n^n)-w_n^kA_2(w_n^{2k}w_n^n)\ \ =A_1(w_n^{2k})-w_n^kA_2(w_n^{2k}) \ \ =A_1(w_{frac{n}{2}}^k)-w_n^kA_2(w_{frac{n}{2}}^k)$

$结论:$

• $A(w_n^k) = A_1(w_{frac{n}{2}}^k)+w_n^kA_2(w_{frac{n}{2}}^k)$

• $A(w_n^{k+frac{n}{2}})=A_1(w_{frac{n}{2}}^k)-w_n^kA_2(w_{frac{n}{2}}^k)$

可以观察到第二个式子与第一个式子的唯一区别就是正负号 .

根据上方式子分治处理出每个子项, 再向上合并, 时间复杂度 $O(NlogN)$ .

---

$总结:$

$FFT$是先将多项式转换为 点值表示, 然后进行分治处理, 再转变为多项式的 $O(nlogn)$ 算法 .

推导过程:

1. $把系数按奇偶分开$
2. 代入 单位根 .
3. 得到 “分治向上递推式” .

---

• $FFT的实现$

• $蝴蝶变换$

借用 这位大佬 的一个图,

所谓蝴蝶变换, 就是将原序列进行二进制翻转的变换 .

$rev[i] = (rev[i>>1]>>1) | ((i&1) << bit\_num-1)$

详解点击 这里 .

---

下面是 模板 代码 .

#include<bits/stdc++.h>

#define reg register

const int maxn = 1e6 + 5;
const double Pi = acos(-1);

struct complex{
        double x, y;
        complex(double x = 0, double y = 0):x(x), y(y) {}
} A[maxn<<2], B[maxn<<2];

complex operator + (complex a, complex b){ return complex(a.x+b.x, a.y+b.y); }
complex operator - (complex a, complex b){ return complex(a.x-b.x, a.y-b.y); }
complex operator * (complex a, complex b){ return complex(a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x); }

int N, M;
int rev[maxn<<2];

void FFT(complex *F, short Opt){
        for(int i = 0; i < N; i ++)
                if(i < rev[i]) std::swap(F[i], F[rev[i]]);
        for(int p = 2; p <= N; p <<= 1){
                int len = p >> 1;
                complex tmp(cos(Pi/len), Opt*sin(Pi/len));
                for(int i = 0; i < N; i += p){
                        complex Buf(1, 0);
                        for(reg int k = i; k < i+len; k ++){
                                complex Temp = Buf * F[k+len];
                                F[k+len] = F[k] - Temp;
                                F[k] = F[k] + Temp;
                                Buf = Buf * tmp;
                        }
                }
        }
}

int main(){
        N = read(), M = read();
        for(int i = 0; i <= N; i ++) A[i].x = read();
        for(int i = 0; i <= M; i ++) B[i].x = read();
        int bit_num = 0;
        for(M += N, N = 1; N <= M; N <<= 1) bit_num ++;
        for(int i = 0; i < N; i ++) rev[i] = (rev[i>>1]>>1)|((i&1)?N>>1:0);
        // for(int i = 0; i < N; i ++) rev[i] = (rev[i>>1]>>1) | ((i&1) << bit_num-1);
        FFT(A, 1), FFT(B, 1);
        for(int i = 0; i < N; i ++) B[i] = A[i] * B[i];
        FFT(B, -1);
        for(reg int i = 0; i <= M; i ++) printf("%.0lf ", fabs(B[i].x/N));
        return 0;
}

• $FFT的应用$

$万径人踪灭$

$力$

$礼物$

---

• $FFT 魔改-> NTT$

1. 将单位根 $w_n$ 替换为原根 $g^{frac{mod-1}{len}}$
2. 最后乘的是 $T\_len$ 的逆元 .

其中 $g$ 在 模数 $998244353$下取 $3$ .

void FFT(complex *F, int opt){
        for(reg int i = 0; i < FFT_Len; i ++)
                if(i < rev[i]) std::swap(F[i], F[rev[i]]);
        for(reg int p = 2; p <= FFT_Len; p <<= 1){
                int half = p >> 1;
                complex t = complex(cos(Pi/half), opt*sin(Pi/half));
                for(reg int i = 0; i < FFT_Len; i += p){
                        complex buf = complex(1, 0);
                        for(reg int k = i; k < i+half; k ++){
                                complex Tmp = buf * F[k + half];
                                F[k + half] = F[k] - Tmp;
                                F[k] = F[k] + Tmp;
                                buf = buf * t;
                        }
                }
        }
}

---

void NTT(int *f, int opt){
        for(reg int i = 0; i < T_len; i ++)
                if(i < rev[i]) std::swap(f[i], f[rev[i]]);
        for(reg int p = 2; p <= T_len; p <<= 1){
                int half = p >> 1;
                int wn = Ksm(3, (mod-1)/p);
                if(opt == -1) wn = Ksm(wn, mod-2);
                for(reg int i = 0; i < T_len ; i += p){
                        int buf = 1;
                        for(reg int k = i; k < i+half; k ++){
                                int Tmp_1 = 1ll*buf*f[k+half] % mod;
                                f[k+half] = (f[k] - Tmp_1 + mod) % mod;
                                f[k] = (f[k] + Tmp_1) % mod;
                                buf = 1ll*buf*wn % mod;
                        }
                }
        }
}