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

文章目录

$FFT的作用$
$FFT的前置$
$FFT的内容$
$FFT的实现$
$FFT的应用$
$FFT\ 魔改-> NTT$

$F F T 的作用$

$O (l o g N)$ 计算两个多项式的卷积 .

$F F T 的前置$

单位根

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

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

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

$性质 1 :$ $w_{2 n}^{2 k} = w_{n}^{k}$
$性质 2 :$ $w_{n}^{k + \frac{n}{2}} = - w_{n}^{k}$

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

$欧拉公式 : w_{n}^{k} = c o s (k * \frac{2 π}{n}) + i * s i n (k * \frac{2 π}{n})$

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

$性质 1 :$ $w_{2 n}^{2 k} = w_{n}^{k}$
$证 :$
$w_{2 n}^{2 k} = c o s (2 k * \frac{2 π}{2 n}) + i * s i n (2 k * \frac{2 π}{2 n}) = w_{n}^{k}$

$性质 2 :$ $w_{n}^{k + \frac{n}{2}} = - w_{n}^{k}$
$证 :$
$w_{n}^{k + \frac{n}{2}} = c o s [(k + \frac{n}{2}) * \frac{2 π}{n}] + i * s i n [(k + \frac{n}{2}) * \frac{2 π}{n})] = - w_{n}^{k}$

$F F T 的内容$
有多项式 $A (x) = a_{0} + a_{1} x + a_{2} x^{2} + &NegativeThinSpace; \dots + a_{n - 1} x^{n - 1}$

$∵ 一个 n 次多项式可以被 n + 1 个点唯一确定 .$
$∴ 将 w_{n}^{0} &NegativeThinSpace; \dots w_{n}^{n - 1} 代入可以确定该多项式 .$

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

对于上方多项式 $A (x)$ , 将其系数按奇偶分开, 得 $↓$
$A (x) = (a_{0} + a_{2} * x^{2} + &NegativeThinSpace; \dots + a_{n - 2} * x^{n - 2}) + (a_{1} * x + a_{3} * x^{3} + &NegativeThinSpace; \dots + a_{n - 1} * x^{n - 1})$
$设$
$A_{1} (x) = a_{0} + a_{2} x + a_{4} x^{2} + &NegativeThinSpace; \dots + a_{n - 2} x^{\frac{n}{2} - 1} <mtext> </mtext> A_{2} (x) = a_{1} + a_{3} x + a_{5} x^{2} + &NegativeThinSpace; \dots + a_{n - 1} x^{\frac{n}{2} - 1}$
$则$
$A (x) = A_{1} (x^{2}) + x * A_{2} (x^{2})$

$代入 <mtext> </mtext> w_{n}^{k} <mtext> </mtext> (k < \frac{n}{2}) <mtext> </mtext> 得$
$A (w_{n}^{k}) = A_{1} (w_{n}^{2 k}) + w_{n}^{k} A_{2} (w_{n}^{2 k}) = A_{1} (w_{\frac{n}{2}}^{k}) + w_{n}^{k} A_{2} (w_{\frac{n}{2}}^{k})$

$代入 <mtext> </mtext> w_{n}^{k + \frac{n}{2}} <mtext> </mtext> 得$
$A (w_{n}^{k + \frac{n}{2}}) <mtext> </mtext> = A_{1} (w_{n}^{2 k + n}) + w_{n}^{k + \frac{n}{2}} A_{2} (w_{n}^{2 k + n}) <mtext> </mtext> = A_{1} (w_{n}^{2 k} * w_{n}^{n}) - w_{n}^{k} A_{2} (w_{n}^{2 k} w_{n}^{n}) <mtext> </mtext> = A_{1} (w_{n}^{2 k}) - w_{n}^{k} A_{2} (w_{n}^{2 k}) <mtext> </mtext> = A_{1} (w_{\frac{n}{2}}^{k}) - w_{n}^{k} A_{2} (w_{\frac{n}{2}}^{k})$

$结论 :$

$A (w_{n}^{k}) = A_{1} (w_{\frac{n}{2}}^{k}) + w_{n}^{k} A_{2} (w_{\frac{n}{2}}^{k})$
$A (w_{n}^{k + \frac{n}{2}}) = A_{1} (w_{\frac{n}{2}}^{k}) - w_{n}^{k} A_{2} (w_{\frac{n}{2}}^{k})$

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

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

$总结 :$

$F F T$ 是先将多项式转换为 <stron>, 然后进行分治处理, 再转变为多项式的 $O (n l o g n)$ 算法 .</stron>

推导过程:

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

$F F T 的实现$
$蝴蝶变换$

借用这位大佬的一个图,

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

$r e v [i] = (r e v [i > > 1] > > 1) ∣ ((i & 1) < < b i t_n u m - 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;
}

$F F T 的应用$

$万径人踪灭$

$力$

$礼物$

$F F T <mtext> </mtext> 魔改 - > N T T$

将单位根 $w_{n}$ 替换为原根 $g^{\frac{m o d - 1}{l e n}}$
最后乘的是 $T_l e n$ 的逆元 .

其中 $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;
                        }
                }
        }
}

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

文章目录

F F T 的 作 用 FFT的作用 FFT的作用

F F T 的 前 置 FFT的前置 FFT的前置

单位根

F F T 的 内 容 FFT的内容 FFT的内容

结 论 : 结论: 结论:

F F T 的 实 现 FFT的实现 FFT的实现

蝴 蝶 变 换 蝴蝶变换 蝴蝶变换

F F T 的 应 用 FFT的应用 FFT的应用

F F T <mtext> </mtext> 魔 改 − &gt; N T T FFT\ 魔改-&gt; NTT FFT 魔改−>NTT

$F F T 的作用$

$F F T 的前置$

$F F T 的内容$

$结论 :$

$F F T 的实现$

$蝴蝶变换$

$F F T 的应用$

$F F T <mtext> </mtext> 魔改 - > N T T$