FFT、NTT 算法浅析

FFT(快速傅里叶变换)和 NTT(快速数论变换)的浅显讲解。

更新于 2026年9月26日约 17 分钟阅读
由于笔者能力有限,NTT 和逆 FFT 的讲解由 AI 模仿我的写作风格生成,其余讲解和代码编写均由本人完成。文章已经过 AI 和人工的审核以保证正确性和易读性。

前言

FFT(快速傅里叶变换)和 NTT(快速数论变换),常用于高效解决多项式乘法问题。初次听见这两个名字时,你可能会觉得这两个算法很厉害,但是很难,我也是这么认为的。就让我来为你浅显易懂地讲解这两个算法(以理解为主,严谨证明较少)。

前置知识

你需要了解分治、多项式、函数、复数的相关概念。为了学习 NTT,还需了解数论中的素数、取模、同余等概念,之后便可进入本文的学习。

FFT 的目标

两个多项式 a0+a1x+a2x2+⋯+anxna_0+a_1x+a_2x^2+\dots+a_n x^n 和 b0+b1x+b2x2+⋯+bnxnb_0+b_1x+b_2x^2+\dots+b_n x^n 要相乘,朴素的做法是逐项分别相乘,时间复杂度 O(n2)O(n^2)。FFT 就是一种优化的算法,使得多项式相乘的时间复杂度降至 O(nlog⁡n)O(n\log n)。

FFT 的大致原理

先介绍以下几个基本结论或者定理:

  • 平面上给定 n+1n+1 个点(xx 坐标互不相同),可以唯一确定一个次数不超过 nn 的多项式。
  • 一个次数不超过 nn 的多项式 a0+a1x+a2x2+⋯+anxna_0+a_1x+a_2x^2+\dots+a_n x^n 可以被视作一个次数不超过 mm 的多项式 a0+a1x+a2x2+⋯+amxm(m≥n)a_0+a_1x+a_2x^2+\dots+a_m x^m(m\ge n),只要 an+1a_{n+1} 到 ama_m 均为 00 就行了。
  • 长度为 nn 和 mm 的多项式相乘,其结果长度不超过 n+m−1n+m-1。

FFT 的做法就是:对于两个多项式 A,BA,B,取 2k2^k 个不同的 xx 坐标(其中 2k≥n+m−12^k\ge n+m-1),对于每一个 xx 坐标求出其对应的多项式值 A(x)A(x) 和 B(x)B(x),这样我们就有了 2k+2k2^k+2^k 个点。然后把同样 xx 坐标的两个点的 yy 坐标相乘,产生乘积 2k2^k 个点,之后我们通过乘积的 2k2^k 个点还原出多项式,即为 A×BA\times B 的结果。

FFT 的高妙之处在于,通过选取合适的 xx 坐标,使得产生 2k+2k2^k+2^k 个点以及把 2k2^k 个点还原成多项式的过程都在 O(nlog⁡n)O(n\log n) 的时间内完成。

单位根

初次接触单位根,可能不知道它是干什么用的,但是这玩意确实在 FFT 中有很大用处。

一个数满足 zn=1z^n=1,就称它为 nn 次单位根。本文用 ωn=e2πi/n\omega_n=e^{2\pi i/n} 表示其中逆时针走一步的那个单位根,全部 nn 个单位根就是 ωn0,ωn1,…,ωnn−1\omega_n^0,\omega_n^1,\dots,\omega_n^{n-1}。当 n=2n=2 时,单位根为 1,−11,-1,当 n=4n=4 时,单位根为 1,i,−1,−i1,i,-1,-i。

单位根的分布在复平面上是有规律的,以 88 次单位根为例,如下图,88 个单位根都分布在单位圆上,且把这个圆平均分。

单位根有哪些性质呢?假设从 ωni\omega_n^i 开始,逆时针走到下一个单位根,叫做走一步。那么 ωni+n/2\omega_n^{i+n/2} 就是走半圈,数值会变成原来的相反数。走完整整一圈,我们又回到了起点。这些独特的性质正是 FFT 的关键。

那么什么运算可以从一个单位根走一步到达另一个单位根呢?把复数看成从原点出发的向量,你会发现复数的乘法运算就是模长相乘,辐角相加(前置知识中假设你已经了解复数相关运算,这里不再详细介绍)。因此乘以一个 ωn1\omega_n^1,相当于逆时针旋转 360∘n\frac{360^\circ}{n},就是所谓的走一步。

上面不是提到会选取 2k2^k 个 xx 坐标吗?傅里叶这个大佬非常的聪明,选取了复数集中的单位根作为上面提到的 xx 坐标。由于有 2k2^k 个 xx 坐标,就会选取 2k2^k 个 2k2^k 次单位根。并且单位根的特殊性质,可以使得它们大大减小 FFT 的计算量。

FFT 的分治思路

考虑求一个多项式 a0+a1x+a2x2+⋯+an−1xn−1a_0+a_1x+a_2x^2+\dots+a_{n-1} x^{n-1} 以 nn 次单位根作为 xx 输入的情况下,多项式的值(这里 nn 是 22 的幂)。把多项式按照下标的奇偶性拆成两部分:a0+a2x2+⋯+an−2xn−2a_0+a_2x^2+\dots+a_{n-2}x^{n-2} 以及 a1x+a3x3+⋯+an−1xn−1a_1x+a_3x^3+\dots+a_{n-1}x^{n-1}。

设三个函数 f(x)=a0+a1x+a2x2+⋯+an−1xn−1f(x)=a_0+a_1x+a_2x^2+\dots+a_{n-1} x^{n-1},g(x)=a0+a2x+⋯+an−2xn/2−1g(x)=a_0+a_2x+\dots+a_{n-2}x^{n/2-1},h(x)=a1+a3x+⋯+an−1xn/2−1h(x)=a_1+a_3x+\dots+a_{n-1}x^{n/2-1}。然后发现,这个 f(x)f(x) 可以由后面两个式子算出来,也就是 f(x)=g(x2)+xh(x2)f(x)=g(x^2)+xh(x^2)。你可以自己算一下,这个等式是成立的。这样我们就把求长度为 nn 的多项式的值转化成求两个长度为 n2\frac{n}{2} 的多项式的值,最后合并起来,这就是典型的分治思想。

你可能会疑惑:算一次 f(x)f(x) 要用 O(nlog⁡n)O(n\log n) 的时间复杂度,有 nn 个单位根要算,总时间复杂度 O(n2log⁡n)O(n^2\log n),不是反而更慢了吗?不是这样的,FFT 中不是逐个把单位根代入多项式去算,而是同时算这 nn 个单位根的值,时间复杂度也是 O(nlog⁡n)O(n\log n)。假设你知道两个长为 n2\frac{n}{2} 的子式子分别以 ωn/20…n/2−1\omega_{n/2}^{0\dots n/2-1} 作为 xx 的情况下,多项式的值,一共 n2+n2=n\frac{n}{2}+\frac{n}{2}=n 个,是有办法求出长为 nn 的父式子分别以 ωn0…n−1\omega_{n}^{0\dots n-1} 作为 xx 的情况下,多项式的值。求这个的时间复杂度是 O(n)O(n)。和归并排序类似,都是分成两个规模为一半的子问题,合并耗时 O(n)O(n),因此总时间复杂度依然为 O(nlog⁡n)O(n\log n)。

蝴蝶运算

蝴蝶运算是 FFT 最核心以及最难理解的操作,非常重要。上面提到 FFT 可以 O(n)O(n) 合并两个子问题的结果,就是通过蝴蝶运算进行的。

介绍以下基本的结论或定理:

  • ωn2k=ωn/2k\omega_n^{2k}=\omega_{n/2}^k(理由:根据图像,“分成 nn 份,走 2k2k 步”和“分成 n2\frac{n}{2} 份,走 kk 步”,走到的地方是一样的)
  • ωnk+n/2=−ωnk\omega_n^{k+n/2}=-\omega_{n}^k(理由:根据图像,从一半开始走 kk 步和从起点开始走 kk 步,走到的位置相反)

然后呢,把 x=ωnkx=\omega_n^k 和 x=ωnk+n/2x=\omega_n^{k+n/2} 分别代入上文提到的式子 f(x)=g(x2)+xh(x2)f(x)=g(x^2)+xh(x^2) 中。

第一个值代入:

f(ωnk)=g((ωnk)2)+ωnkh((ωnk)2)=g(ωn2k)+ωnkh(ωn2k)=g(ωn/2k)+ωnkh(ωn/2k)\begin{align*} f(\omega_n^k)&=g((\omega_n^k)^2)+\omega_n^kh((\omega_n^k)^2)\\ &=g(\omega_n^{2k})+\omega_n^kh(\omega_n^{2k})\\ &=g(\omega_{n/2}^{k})+\omega_n^kh(\omega_{n/2}^{k}) \end{align*}

第二个值代入:

先算 (ωnk+n/2)2=ωn2k+n=ωn2k×ωnn=ωn2k=ωn/2k(\omega_n^{k+n/2})^2=\omega_n^{2k+n}=\omega_n^{2k}\times \omega_n^{n}=\omega_n^{2k}=\omega_{n/2}^{k}。

f(ωnk+n/2)=g((ωnk+n/2)2)+ωnk+n/2h((ωnk+n/2)2)=g(ωn/2k)+ωnk+n/2h(ωn/2k)=g(ωn/2k)−ωnkh(ωn/2k)\begin{align*} f(\omega_n^{k+n/2})&=g((\omega_n^{k+n/2})^2)+\omega_n^{k+n/2}h((\omega_n^{k+n/2})^2)\\ &=g(\omega_{n/2}^{k})+\omega_n^{k+n/2}h(\omega_{n/2}^{k})\\ &=g(\omega_{n/2}^{k})-\omega_{n}^kh(\omega_{n/2}^{k}) \end{align*}

至此,对于任意 k∈[0,n/2−1]k\in[0,n/2-1],我们都能在计算完所有 n2\frac{n}{2} 规模的子问题的情况下,O(1)O(1) 同时计算出 f(ωnk)f(\omega_n^k) 和 f(ωnk+n/2)f(\omega_n^{k+n/2}) 的值。这样的 kk 一共有 n2\frac{n}{2} 个,因此合并过程的时间复杂度为 O(n)O(n)。

逆 FFT

我们已经解决了对于每一个 xx 坐标求出其对应的多项式值,还需解决通过每一个 xx 坐标对应的多项式值还原出多项式。这需要用到逆 FFT。

你可能会想:既然正向 FFT 是把系数变成点值,那么反过来还原系数,是不是得重新发明一种算法?其实不用。把单位根反过来走,再把每个结果除以 nn,就能用几乎同一套 FFT 算法完成还原。为什么这样做是对的呢?

设原来的多项式为 f(x)=a0+a1x+⋯+an−1xn−1f(x)=a_0+a_1x+\dots+a_{n-1}x^{n-1},正向 FFT 算出的第 kk 个点值记作 Fk=f(ωnk)F_k=f(\omega_n^k)。把多项式展开,就有:

Fk=∑j=0n−1ajωnjkF_k=\sum_{j=0}^{n-1}a_j\omega_n^{jk}

现在假设我们要找回第 tt 个系数 ata_t。把所有点值 FkF_k 分别乘以 ωn−tk\omega_n^{-tk},再加起来:

∑k=0n−1Fkωn−tk=∑j=0n−1aj(∑k=0n−1ωn(j−t)k)\sum_{k=0}^{n-1}F_k\omega_n^{-tk} =\sum_{j=0}^{n-1}a_j\left(\sum_{k=0}^{n-1}\omega_n^{(j-t)k}\right)

先看括号里的东西。如果 j=tj=t,每一项都是 11,加起来就是 nn;如果 j≠tj\ne t,这一项会沿着单位圆等间隔地转,转满一圈后总和为 00。比如走四个方向时,1+i+(−1)+(−i)=01+i+(-1)+(-i)=0。哪怕不是恰好把每个单位根都走一遍,只要不是一直待在 11,绕圈得到的数加起来仍然为 00。于是,别的系数全都互相抵消,只剩下 natna_t:

∑k=0n−1Fkωn−tk=nat,at=1n∑k=0n−1Fkωn−tk\sum_{k=0}^{n-1}F_k\omega_n^{-tk}=na_t, \qquad a_t=\frac{1}{n}\sum_{k=0}^{n-1}F_k\omega_n^{-tk}

这也解释了为什么单位根要反方向走:正向计算时,aja_j 对第 kk 个点值的贡献带着 ωnjk\omega_n^{jk};还原 ata_t 时乘上 ωn−tk\omega_n^{-tk},指数就变成了 (j−t)k(j-t)k。当 j=tj=t 时,两次旋转正好抵消;其他系数则沿圆周转动,相加后消失。如果还照着原来的方向走,指数就会变成 (j+t)k(j+t)k,不能按原来的下标把系数找回来。

这里的 ωn−1\omega_n^{-1} 就是 ωn\omega_n 的倒数,也就是它的共轭复数。在单位圆上乘以它,相当于顺时针走一步。所以实现逆 FFT 时,只要把正向 FFT 中用到的单位根换成反方向的单位根,再对输出的每个数除以 nn 即可。除以 nn 不是额外的技巧:目标系数在上面的求和中被保留了 nn 次,所以必须除以 nn,才能从 natna_t 得到 ata_t。

FFT 的具体实现

上面我们提到的分治做法用递归做起来比较容易理解,但是时间和空间常数较大,可以把它改成自底向上递推的形式。

看一个序列 0,1,2,3,4,5,6,70,1,2,3,4,5,6,7,按照奇偶性分成两组,分别是 0,2,4,60,2,4,6 和 1,3,5,71,3,5,7。接着分,是 0,40,4、2,62,6、1,51,5、3,73,7。再分一次得到单个元素,顺序就是 0,4,2,6,1,5,3,70,4,2,6,1,5,3,7。

转换成二进制形式,原始序列:000,001,010,011,100,101,110,111000,001,010,011,100,101,110,111。

最终序列:000,100,010,110,001,101,011,111000,100,010,110,001,101,011,111。

发现什么规律了吗?每个数在二进制下都前后反转了!因此我们可以通过这个快速求出原始序列对应的最终序列。

for(int i=1,j=0;i<n;i++){
    int bit=n>>1;
    for(;j&bit;bit>>=1)j^=bit;
    j^=bit;//这是一种计算出二进制下反转后数字的神奇方式
    if(i<j)swap(a[i],a[j]);//把原数字和反转后数字调换位置
}

从 2,4,82,4,8 一直到 nn 枚举多项式的长度,先算小规模问题,之后根据小规模问题的答案合并出大规模问题的答案。代码中的 a 数组就是暂存答案用的。

以下是完整参考代码:

#include<bits/stdc++.h>
using namespace std;
using cd=complex<double>;
const double pi=acos(-1.0);
const int N=3e6+5;
int n,m,a[N],b[N],siz=1;
cd aa[N],bb[N],c[N<<1];
void fft(cd *a,int f){
    for(int i=1,j=0;i<siz;i++){//奇偶拆分
        int bit=siz>>1;
        for(;j&bit;bit>>=1)j^=bit;
        j^=bit;
        if(i<j)swap(a[i],a[j]);
    }
    for(int len=2;len<=siz;len<<=1){
        double angle=pi*2/len*f;//一次旋转的角度
        cd wlen(cos(angle),sin(angle));//单位根
        //这里的cos和sin相当于在x和y轴上投影
        for(int i=0;i<siz;i+=len){//起始位置
            cd w(1,0);//旋转因子
            int mid=len>>1;
            for(int j=0;j<mid;j++){//蝴蝶运算
                cd u=a[i+j];
                cd v=a[i+j+mid]*w;
                a[i+j]=u+v;
                a[i+j+mid]=u-v;
                w*=wlen;//走一步
            }
        }
    }
    if(f==-1)//逆FFT
        for(int i=0;i<siz;i++)
            a[i]/=siz;
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    n++,m++;
    while(siz<n+m-1)siz<<=1;
    for(int i=0;i<n;i++)cin>>a[i],aa[i]=cd(a[i],0);
    for(int i=0;i<m;i++)cin>>b[i],bb[i]=cd(b[i],0);
    fft(aa,1);
    fft(bb,1);
    for(int i=0;i<siz;i++)
        c[i]=aa[i]*bb[i];
    fft(c,-1);
    for(int i=0;i<n+m-1;i++)
        cout<<(int)(c[i].real()+0.5)<<' ';
    return 0;
}

模意义下的改进:NTT

前面我们已经讲完了 FFT,现在来看 NTT。你可能会觉得,名字都变了,算法是不是也要从头学一遍?其实不用。NTT 可以理解成把 FFT 中的复数运算,换成模一个质数后的整数运算。奇偶拆分、蝴蝶运算、最后的逆变换,思路几乎一样。最大的疑问反而是:FFT 用复平面上的单位根转圈,模意义下哪来的圆?

先别管圆长什么样。回想一下,前面推蝴蝶运算时,我们真正用到的是单位根的几个性质:走 nn 步回到 11,中途不提前回到 11;走半圈到 −1-1;每走两步相当于小一半问题中的一步。如果模意义下也能找出满足这些性质的数,那么原来的推导就仍然成立。NTT 中的数不是真的排在复平面的圆上,“走一步”只是一种帮助理解乘方和取模的比喻。

模意义下怎样转圈

先用小一点的模数看看。模 77 时,取 33,不断乘 33 并取模:

31,32,33,34,35,36≡3,2,6,4,5,1(mod7)3^1,3^2,3^3,3^4,3^5,3^6 \equiv 3,2,6,4,5,1\pmod 7

发现了吗?它把 11 到 66 都走了一遍,第 66 步才回到 11。我们称 33 为模 77 的原根。一般地,对于质数 pp,如果 gg 的幂模 pp 后能遍历 1,2,…,p−11,2,\dots,p-1,也就是说最早在第 p−1p-1 步回到 11,那么 gg 就是模 pp 的原根。这个“最早在第几步回到 11”也叫做 gg 的阶。

这里有个很像 FFT 的现象:上面序列的前半段是 3,2,63,2,6,后半段是 4,5,14,5,1,对应的数相加都是 77。在模 77 下,它们的和就是 00,所以后半段正好是前半段的相反数。这可不是巧合:

33≡6≡−1(mod7),3k+3≡−3k(mod7)3^3\equiv6\equiv-1\pmod7, \qquad 3^{k+3}\equiv-3^k\pmod7

为什么走到一半一定是 −1-1 呢?设 gg 是模奇质数 pp 的原根,令 x=g(p−1)/2x=g^{(p-1)/2}。再走半圈就回到 11,因此 x2≡1(modp)x^2\equiv1\pmod p。因为 pp 是质数,(x−1)(x+1)≡0(modp)(x-1)(x+1)\equiv0\pmod p 只能说明 x≡1x\equiv1 或 x≡−1x\equiv-1。但如果半圈就走回 11,gg 就不配叫原根了,因此只能是 x≡−1x\equiv-1。这和复数单位根走半圈变成相反数,是同一个蝴蝶运算需要的性质。

原根和模数的来历

模 77 的例子虽好,却没法做很长的 NTT。实际写代码时常选模数 p=998244353p=998244353,它是质数,而且:

p−1=998244352=119×223p-1=998244352=119\times2^{23}

33 是模 pp 的原根,它转完整一圈需要 p−1p-1 步。假设我们只需要长度为 nn 的变换,也就是想要一个“走 nn 步一圈”的单位根,该怎么办?每一步不要只走原来的 11 步,而是跳 (p−1)/n(p-1)/n 步:

ωn=3(p−1)/n mod p\omega_n=3^{(p-1)/n}\bmod p

这样走 nn 步,就是把 33 乘了 p−1p-1 次,正好回到 11。而且中途不会提前回去:假如走了 kk 步就回到 11,那么 3k(p−1)/n≡1(modp)3^{k(p-1)/n}\equiv1\pmod p;由于 33 原本必须走满 p−1p-1 步才能回到 11,只能有 n∣kn\mid k。所以 ωn\omega_n 的阶恰好是 nn,而不只是“走 nn 步时碰巧回来了”。

注意这里要求 nn 能整除 p−1p-1,否则“每次跳 (p−1)/n(p-1)/n 步”就没法这样构造。例如长度 n=1024n=1024 时,直接取 3(p−1)/1024 mod p3^{(p-1)/1024}\bmod p,不必非要用 2232^{23} 步的大圈。又因为 p−1p-1 中有 2232^{23} 这个因子,前面讲的二分蝴蝶运算可以支持 n=2kn=2^k,其中 k≤23k\le23。2232^{23} 是这个模数下二的幂长度的上限,不是每次都必须取的长度。做多项式乘法时,仍然选取不小于结果长度的最小的二的幂,只是这个长度还不能超过 2232^{23}。

你可能会继续问:上面说的几个性质真的都有吗?当 nn 是大于 11 的二的幂时,由于 3(p−1)/2≡−1(modp)3^{(p-1)/2}\equiv-1\pmod p,有:

ωnn/2≡−1(modp),ωnk+n/2≡−ωnk(modp)\omega_n^{n/2}\equiv-1\pmod p, \qquad \omega_n^{k+n/2}\equiv-\omega_n^k\pmod p

另外,把大圈每两步合成一步,就有:

ωn2≡(3(p−1)/n)2≡3(p−1)/(n/2)≡ωn/2(modp)\omega_n^2 \equiv\left(3^{(p-1)/n}\right)^2 \equiv3^{(p-1)/(n/2)} \equiv\omega_{n/2}\pmod p

这不就是前面推 FFT 蝴蝶运算用到的两个式子吗?因此,在 NTT 中照样先算 g(ωn/2k)g(\omega_{n/2}^k) 和 h(ωn/2k)h(\omega_{n/2}^k),再通过一加一减得到父问题的两个值。只不过现在每次加、减、乘都要对 pp 取模。

逆 NTT

逆 FFT 用反方向的单位根,最后除以 nn;逆 NTT 也是一样的。模意义下的“反方向走一步”就是乘以 ωn\omega_n 的乘法逆元,记作 ωn−1\omega_n^{-1},它满足 ωnωn−1≡1(modp)\omega_n\omega_n^{-1}\equiv1\pmod p。由于 ωnn≡1\omega_n^n\equiv1,也可以把它写成 ωnn−1\omega_n^{n-1}。

不过在模 pp 下,“除以 nn”可不能直接用普通整数除法,而应该乘以 nn 的模 pp 逆元。因为 n<pn<p 且 pp 是质数,费马小定理给出:

n−1≡np−2(modp),xn(modp)  =  x⋅n−1(modp)n^{-1}\equiv n^{p-2}\pmod p, \qquad \frac{x}{n}\pmod p\;=\;x\cdot n^{-1}\pmod p

原理和前面的逆 FFT 完全一致:反方向走使其他系数相互抵消,目标系数剩下 nn 份;乘以 n−1n^{-1},才能把它还原成一份。这里也能用前文的等比数列验证:对于非目标系数,取 q=ωnj−t≠1q=\omega_n^{j-t}\ne1,则 qn=1q^n=1,因此 (1−q)(1+q+⋯+qn−1)=1−qn=0(1-q)(1+q+\dots+q^{n-1})=1-q^n=0。因为模质数时非零的 1−q1-q 有逆元,所以括号中的和仍是 00。

NTT 的具体实现

如果你已经写过 FFT,实现 NTT 时保留位反转和蝴蝶运算的框架,把 complex<double> 改成模 pp 的整数,把按角度计算的单位根改成快速幂计算的单位根,再把所有运算改成取模即可。下面这段代码的输入和常见 FFT 乘法模板一样:先输入两个多项式的次数,再输入系数;输出的每个系数都是模 998244353998244353 的结果。

#include<bits/stdc++.h>
using namespace std;
const int N=3e6+5,P=998244353;
int n,m,a[N],b[N],c[N<<1],siz=1,inv;
int qpow(int a,int b){//快速幂
    long long res=1;
    while(b){
        if(b&1)res=(res*a)%P;
        a=(1ll*a*a)%P;
        b>>=1;
    }
    return res;
}
void fft(int *a,int f){
    for(int i=1,j=0;i<siz;i++){//奇偶拆分
        int bit=siz>>1;
        for(;j&bit;bit>>=1)j^=bit;
        j^=bit;
        if(i<j)swap(a[i],a[j]);
    }
    for(int len=2;len<=siz;len<<=1){
        int omega=qpow(3,(P-1)/len);//单位根
        if(f==-1)omega=qpow(omega,P-2);//逆单位根
        for(int i=0;i<siz;i+=len){//起始位置
            int w=1,mid=len>>1;
            for(int j=0;j<mid;j++){//蝴蝶运算
                int u=a[i+j];
                int v=(1ll*a[i+j+mid]*w)%P;
                a[i+j]=u+v;
                if(a[i+j]>=P)a[i+j]-=P;
                a[i+j+mid]=u-v;
                if(a[i+j+mid]<0)a[i+j+mid]+=P;
                w=(1ll*w*omega)%P;
            }
        }
    }
    if(f==-1)
        for(int i=0;i<siz;i++)
            a[i]=(1ll*a[i]*inv)%P;
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    n++,m++;
    while(siz<n+m-1)siz<<=1;
    inv=qpow(siz,P-2);//计算P的逆元
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<m;i++)cin>>b[i];
    fft(a,1);
    fft(b,1);
    for(int i=0;i<siz;i++)
        c[i]=(1ll*a[i]*b[i])%P;
    fft(c,-1);
    for(int i=0;i<n+m-1;i++)
        cout<<c[i]<<' ';
    return 0;
}

后记

至此,你已经理解了 FFT(快速傅里叶变换)和 NTT(快速数论变换),可以去做题了。

Vector Log · 算法竞赛学习笔记

Built with Nuxt UI & Nuxt MDC