FFT/NTT 学习笔记

2024/7/27 OI 学习指南多项式

引入

我们在计算两个多项式的乘积的时候，最常见的做法也就是一位一位相乘，然后加到对应的位置，也就是： \[ f_{x}=\sum_{i+j=x}f_{i}\times f_{j} \] 这也就是乘法卷积。容易发现普通计算是 \(O(n^2)\) 的。可不可以优化呢？

FFT

首先，FFT 全称为：快速傅里叶变换。它的作用是将乘法卷积朴素做法的 \(O(n^2)\)，优化为 \(O(n\log{n})\)，速度快了不少。
首先，我们来讲解一些前置知识。

复数

引入

初中的时候，我们学过平方根运算，也就是 \(\sqrt{x}\)，我们知道，当 \(x\) 大于等于 \(0\) 时，\(\sqrt{x}\) 才是有意义的。
那我们要是硬要算 \(\sqrt{-1}\) 呢？数学家们定义了一种新的数：虚数。相对应的，我们一般用的数，称为实数，用 \(\mathbb{R}\) 表示。
虚数的单位是 \(\mathrm{i}\)，你可能会问。实数的单位是什么，其实是 \(1\)。所以你大概可以将 \(\mathrm{i}\) 当成虚数集的 \(1\)。因为 \(\sqrt{-1}=\mathrm{i}\)，所以有 \(\mathrm{i}^{2}=-1\)，这点很重要，记住。

虚数是有四则运算的，也就是：

\(a\mathrm{i}+b\mathrm{i}=(a+b)\mathrm{i}\)
\(a\mathrm{i}-b\mathrm{i}=(a-b)\mathrm{i}\)
\(a\mathrm{i}\times b\mathrm{i}=ab\mathrm{i}^{2}=-ab\)
\(a\mathrm{i}\div b\mathrm{i}=\dfrac{a}{b}\mathrm{i}\)

而复数则是一个实数加上一个虚数，一般表示为 \(a+b\mathrm{i}\)。其中，\(a\) 称为实部，\(b\mathrm{i}\) 称为虚部。
我们知道，一条数轴可以表示出所有实数，那么我们加上一条与之垂直的数轴，用来表示虚数，那么在这个二维平面上的点，都是一个复数，而这个点的 \(x\) 坐标则是这个复数的实部，\(y\) 坐标则是这个复数的虚部。一般用 \(z\) 来表示一个复数。用 \(\mathbb{C}\) 表示复数集。

比如上图中的 B 点，就可以表示 \(3+5i\) 这个复数，我们发现，其实这很像向量，也就是 \(\overrightarrow{OB}=(a,b)\)。

复数解

在初中求解一元二次方程的时候，假如方程是 \(ax^{x}+bx+c=d(a\not =0,a,b,c,d\in \mathbb{R})\) 我们有一个 \(\Delta=b^{2}-4ac\)，初中老师告诉我们，当 \(\Delta<0\) 时，没有实数根。但其实，是有复数根的。
比如 \(x^{2}+2x+2=0\) 这个方程。我们得出 \(\Delta=2^{2}-4\times2\times1=-4\)，如果我们强行带入求根公式中可以得到： \[ \begin{cases} x_{1}=\dfrac{-b+\sqrt{\Delta}}{2a}=\dfrac{-2+\sqrt{-4}}{2}=-1+\mathrm{i}\\ x_{2}=\dfrac{-b-\sqrt{\Delta}}{2a}=\dfrac{-2-\sqrt{-4}}{2}=-1-\mathrm{i} \end{cases} \] 这两个根，也被称为原方程的复数根，所以，你现在应该能明白为什么初中求解一元二次方程的时候，要说 没有实数根，而不说 没有根 了。

四则运算

复数是满足四则运算的。

\((a+c\mathrm{i})+(b+d\mathrm{i})=(a+b)+(c+d)\mathrm{i}\)
\((a+c\mathrm{i})-(b+d\mathrm{i})=(a-b)+(c-d)\mathrm{i}\)

容易发现，复数的加减法是满足交换律和结合律的。也就是：

\(z_{1}+z_{2}+z_{3}=z_{1}+z_{3}+z_{2}\)
\(z_{1}+z_{2}+z_{3}=z_{1}+(z_{2}+z_{3})\)

联系一下向量。我们发现这也同样满足向量的加减法。（也就是四边形法则）

上图表示了 \(z_{1}=3+5\mathrm{i},z_{2}=4-2\mathrm{i}\) 两个复数的加法，我们知道其等于 \(z_{3}=7+3\mathrm{i}\)，我们又知道 \(\overrightarrow{OB}+\overrightarrow{OF}=\overrightarrow{OE}\)。而这几个向量又刚好分别对应了 \(z_{1},z_{2},z_{3}\)。
减法同理。

在讲乘除法前，我们先引入另一个东西：共轭复数。一个复数 \(z\) 的共轭复数用 \(\overline{z}\) 来表示。具体是什么呢？也就是 \(z\) 的虚部取反，比如 \(z_{1}=3+5\mathrm{i}\)，\(\overline{z_{1}}=3-5\mathrm{i}\)。
乘法是很简单的：

\((a+c\mathrm{i})\times(b+d\mathrm{i})=ab+ad\mathrm{i}+bc\mathrm{i}+cd\mathrm{i}^{2}=(ab-cd)+(ad+bc)\mathrm{i}\)

这个同样是和向量乘法相同的，也就是幅角相加，辐长相乘

上图表示了 \(z_{1}=3+5\mathrm{i},z_{2}=4-2\mathrm{i}\) 两个复数的乘法，我们知道其等于 \(z_{3}=22+14\mathrm{i}\)。我们又知道 \(\overrightarrow{OB}\times\overrightarrow{OF}=\overrightarrow{OK}\)。而这几个向量又刚好分别对应了 \(z_{1},z_{2},z_{3}\)。（\(\alpha+\gamma=\delta,OB\times OF=OK\)）

除法相对比较复杂：

\(\dfrac{a+c\mathrm{i}}{b+d\mathrm{i}}=\dfrac{(a+c\mathrm{i})(b-d\mathrm{i})}{(b+d\mathrm{i})(b-d\mathrm{i})}=\dfrac{(ab+cd)+(bc-ad)\mathrm{i}}{b^{2}+d^{2}}=\dfrac{ab+cd}{b^{2}+d^{2}}+\dfrac{bc-ad}{b^{2}+d^{2}}\mathrm{i}\)

共轭复数的加入非常的巧妙。因为向量没有除法，所以也就不说了。

单位根

抄自 OI-Wiki：

单位根：称 \(x^n=1\) 在复数意义下的解是 \(n\) 次复根。显然，这样的解有 \(n\) 个，称这 \(n\) 个解都是 \(n\) 次单位根或单位复根（the n-th root of unity）。根据复平面的知识，\(n\) 次单位根把单位圆 \(n\) 等分。

简单点说，我们现在有一个单位圆，我们从 \((1,0)\) 这个点开始，将其等分为 \(n\) 等分，将平面直角坐标系看作复平面，那么等分点对应的复数，也就是对应的 \(n\) 次单位根中的一个，也就是 \(x^n=1\) 的所有复数根构成的集合。一般用 \(\omega_{n}^{k}\) 表示 \(n\) 次单位根中的第 \(k\) 个。

从上图可以看出，是从 \(\omega_{n}^{0}\) 开始的，而不是从 \(\omega_{n}^{1}\) 开始，\(k\) 是可以大于 \(n\) 的，\(k\) 也可以是负数。

我们可以结合图发现一些性质：

\(\omega_{n}^{k}=\omega_{n}^{k+n}\)
\(\omega_{n}^{k+\frac{n}{2}}=-\omega_{n}^{k}\)
\(\omega^{k}_{n}=\omega^{k}_{\frac{n}{2}}\)
\(\sum_{i=0}^{n-1}\omega_{n}^{i}=-1\times[n \bmod 2=1]\)
\(\sum_{i=0}^{n-1}(\omega_{n}^{i})^{k}=(-1)^{\gcd(n,k)}\times[n \bmod 2=1]\)

第五点为什么是正确的？
对于 \(0\le i<n,k>0,i,k\in\mathbb{Z}\)，我们知道 \(ik\bmod n\) 是有循环节的，而且必定有长度为 \(n\) 的循环节，而最短的循环节则恰好是 \(\dfrac{n}{\gcd(n,k)}\)。

那我们怎么求单位根呢？
我们知道，单位根是将单位圆等分后的点。每个点又可以对应一条向量，那么 \(\omega_{n}^{k}\) 对应的向量的幅角也就是 \(\dfrac{k}{n}2\pi\)，那么根据简单的三角函数我们可以得到，\(\omega_{n}^{k}\) 对应的点为 \((\cos\dfrac{k}{n}2\pi,\sin\dfrac{k}{n}2\pi)\)，根据前文所讲，我们便求出了 \(\omega_{n}^{k}\) 对应的复数 \(\cos\dfrac{k}{n}2\pi+\sin\dfrac{k}{n}2\pi \mathrm{i}\)。

系数表示法和点值表示法

我们现在有一个多项式 \(f(x)=x^{2}+5x-3\)。现在 \(f(x)\) 的表示方法则称为系数表示法。
我们又知道，两点可以确定一条直线，也就是一次函数；三个点可以确认一个二次函数，那么同理，有 \(n+1\) 个点，就可以表示出一个 \(n\) 次多项式。
比如我现在给你三个点 \(A(-2,-9),B(0,-3),C(1,3)\) 我们会发现，同时过这三个点的二次函数，有且仅有一个，也就是 \(f(x)=x^{2}+5x-3\)。

我们要将一个系数表示的多项式，转化为点值表示是非常容易的。直接取 \(x=x_{0},x_{1},\dotsb,x_{n}\) 依次带进原函数计算就行了，我们来算算时间复杂度：

一共要算 \(n+1\) 个点，每次计算代回去要计算 \(n+1\) 次，总的时间复杂度便是 \(O(n^{2})\) 的。

那我们我们现在有了已经转化为点值表示的多项式，我们怎么把它转化为系数表示呢？
我们可以使用一种叫做拉格朗日插值法的方法，但是我也不会，重点也不在这里，毕竟我们要讲的是 FFT。但你可以知道的是，这个方法的时间复杂度也是 \(O(n^{2})\) 的。（虽然有个东西叫做多项式快速插值，但时间复杂度也是 \(O(n\log^{2}{n})\) 的。）

你可能会说了，那这复杂度不还是 \(O(n^2)\) 的吗？和暴力有什么区别，还麻烦的多。你先别急，我们要讲的 FFT，便是优化这一过程的。

快速傅里叶变换（FFT）

FFT 的全称，准确说应该叫做快速离散傅里叶变换。离散傅里叶变换：DFT。FFT 可以在 \(O(n\log n)\) 的时间复杂度下，将一个系数表示的多项式，转化为点值表示。

我们现在有一个多项式 \(f(x)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\dotsb+a_{n-1}x^{n-1}\)。
我们现在又有两个多项式： \[ \begin{aligned} g(x)&=(a_{0}+a_{2}x+a_{4}x^{2}+\dots +a_{n-2}x^{\frac{n}{2}})\\ h(x)&=(a_{1}+a_{3}x+a_{5}x^{2}+\dots +a_{n-1}x^{\frac{n}{2}})\\ \end{aligned} \] 可以得到： \[ \begin{aligned} g(x^{2})&=(a_{0}+a_{2}x^{2}+a_{4}x^{4}+\dots +a_{n-2}x^{n-2})\\ h(x^{2})&=(a_{1}+a_{3}x^{2}+a_{5}x^{4}+\dots +a_{n-1}x^{n-2})\\ \end{aligned} \] 我们发现 \(f(x)=g(x^{2})+xh(x^{2})\)。
我们要求 \(f(x)\) 的点值表示，我们尝试将 \(n\) 个 \(n\) 次单位根依次代入进去。

当 \(0\le k<\dfrac{n}{2}\) 时： \[ \begin{aligned} f(x)&=g(x^{2})+xh(x^{2})\\ f(\omega^{k}_{n})&=g(\omega^{2k}_{n})+\omega_{n}^{k}h(\omega^{2k}_{n})\\ &=g(\omega^{k}_{\frac{n}{2}})+\omega_{n}^{k}h(\omega^{k}_{\frac{n}{2}})\\ \end{aligned} \] 当 \(\dfrac{n}{2}\le k<n\) 时： \[ \begin{aligned} f(\omega_{n}^{k})&=g(\omega_{n}^{2k})+\omega_{n}^{k}h(\omega_{n}^{2k})\\ &=g(\omega^{2k-n}_{n}\cdot\omega^{n}_{n})-\omega_{n}^{k-\frac{n}{2}}h(\omega^{2k-n}_{n}\cdot\omega^{n}_{n})\\ &=g(\omega_{\frac{n}{2}}^{k-\frac{n}{2}})-\omega_{n}^{k-\frac{n}{2}}h(\omega_{\frac{n}{2}}^{k-\frac{n}{2}})\\ \end{aligned} \] 我们不妨令 \(p=g(\omega^{k}_{\frac{n}{2}}),q=h(\omega^{k}_{\frac{n}{2}})\)，可以得到： \[ f(\omega_{n}^{k})= \begin{cases} p+q,0\le k<\dfrac{n}{2}\\ p-q,\dfrac{n}{2}\le k<n \end{cases} \] 得益于单位根的性质，我们计算 \(f(x)\) 时，只需要计算 \(g(x)\) 和 \(h(x)\) ，而他们都是把问题规模缩小了一半。于是我们便可以一直递归下去处理，直到问题规模为 \(1\) 的时候，直接计算即可，再一路回溯回去即可。
注意因为问题规模一直除以 \(2\)，为了防止出现小数，一开始应该将多项式项数补充至 \(2\) 的整数次幂。

根据主定理 \(T(n)=T(\dfrac{n}{2})+O(n)\) 可得时间复杂度为 \(O(n\log n)\)。

快速傅里叶逆变换（IFFT）

和 FFT 很像，FFT 的全称准确说应该是：快速离散傅里叶逆变换。而离散傅里叶逆变换，则是 IDFT。

我们先来尝试证明一个定理：

我们现在有多项式 \(f(x)=\sum_{i=0}^{n-1}a_{i}x^{i}\) 进行 FFT 后的结果：\((\omega_{n}^{0},f(\omega_{n}^{0})),(\omega_{n}^{1},f(\omega_{n}^{1})),\dotsb,(\omega_{n}^{n-1},f(\omega_{n}^{n-1}))\)。把 \(f(\omega_{n}^{0}),f(\omega_{n}^{1}),\dotsb,f(\omega_{n}^{n-1})\) 分别作为系数，组成一个新的多项式 \(g(x)=\sum_{i=0}^{n-1}f(\omega_{n}^{i})x^{i}\)。再取单位根的倒数即 \(\omega^{0}_{n},\omega^{-1}_{n},\dots,\omega^{-(n-1)}_{n}\) 作为 \(x\) 依次代入 \(g(x)\)。将得到的每个 \(g(\omega_{n}^{-k})\) 除以 \(n\) ，得到的值便对应的是原来 \(f(x)\) 的各项系数。

证明大致如下：

我们选择一个 \(\omega_{n}^{-k}(0\le k<n,k\in\mathbb{Z})\) 代入 \(g(x)\)，得到: \[ \begin{aligned} g(\omega_{n}^{-k})&=\sum_{i=0}^{n-1}f(\omega_{n}^{i})(\omega_{n}^{-k})^{i}\\ &=\sum_{i=0}^{n-1}\left(\sum_{j=0}^{n-1}a_{j}(\omega_{n}^{i})^{j}\right)(\omega_{n}^{-k})^{i}\\ &=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}a_{j}(\omega_{n}^{i})^{j}(\omega_{n}^{-k})^{i}\\ &=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}a_{j}(\omega_{n}^{j-k})^{i}\\ &=\sum_{j=0}^{n-1}a_{j}\left(\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\dfrac{(\omega_{n}^{j})^{i}}{(\omega_{n}^{k})^{i}}\right)\\ \end{aligned} \] 对于 \(j=k\) 的时候，总和为 \(na_{k}\)。对于 \(j\not =k\) 的时候，我们知道 \((\omega_{n}^{j})^{i}=0\) 因此总和也为 \(0\)，综上 \(\dfrac{g(\omega_{n}^{-k})}{n}=a_{k}\)，得证。

所以说我们现在本质上也是将插值，转化成了求值，因此时间复杂度也是 \(O(n\log n)\) 的。

乘起来

我们现在既可以将系数表示法转化为点值表示法，也可以将点值表示法转化为系数表示法，而且都是很快速的 \(O(n\log n)\)。那么我们怎么把两个多项式乘起来呢？

如果我们有两个系数表示的多项式，那么我们就只能像最开始那样挨个挨个枚举，然后乘起来，加起来。复杂度是 \(O(n^2)\) 的。
但我们现在有的是两个点值表示的多项式，我们便只需要将对应的点值乘起来就行了，也就是 \(h_{i}=f_{i}\times g_{i}\)。这个为什么是正确的，你们可以自行思考一下。复杂度显然是 \(O(n)\) 的。

那么我们现在就已经可以在 \(O(n\log n)\) 的时间内完成乘法卷积了！
那么，结束了吗？

优化

我们发现原先是一个递归的过程，那么必然常数较大，那么可以怎么优化呢？

蝶形优化

我们发现递归时转移是这样的。（以 \(n=8\) 为例）

我们要计算下面这些的值： \[ f(\omega^{0}_{8}),f(\omega^{1}_{8}),f(\omega^{2}_{8}),f(\omega^{3}_{8}),f(\omega^{4}_{8}),f(\omega^{5}_{8}),f(\omega^{6}_{8}),f(\omega^{7}_{8}) \] 根据前文，我们会将其分成两组继续计算： \[ f(\omega^{0}_{8}),f(\omega^{2}_{8}),f(\omega^{4}_{8}),f(\omega^{6}_{8})\;\;\;\;f(\omega^{1}_{8}),f(\omega^{3}_{8}),f(\omega^{5}_{8}),f(\omega^{7}_{8}) \] 然后继续拆下去，直到处理的数量为 \(1\)： \[ f(\omega^{0}_{8}),f(\omega^{4}_{8})\;\;\;\;f(\omega^{2}_{8}),f(\omega^{6}_{8})\;\;\;\;f(\omega^{1}_{8}),f(\omega^{5}_{8})\;\;\;\;f(\omega^{3}_{8}),f(\omega^{7}_{8}) \] \[ f(\omega^{0}_{8})\;\;\;\;f(\omega^{4}_{8})\;\;\;\;f(\omega^{2}_{8})\;\;\;\;f(\omega^{6}_{8})\;\;\;\;f(\omega^{1}_{8})\;\;\;\;f(\omega^{5}_{8})\;\;\;\;f(\omega^{3}_{8})\;\;\;\;f(\omega^{7}_{8}) \] 最后依次代回去，就可以得出结果。

但我们似乎没找到什么规律呀。我们把编号换成二进制试试？ \[ 000,001,010,011,100,101,110,111 \] \[ 000,010,100,110\;\;\;\;001,011,101,111 \] \[ 000,100\;\;\;\;010,110\;\;\;\;001,101\;\;\;\;011,111 \] \[ 000\;\;\;\;100\;\;\;\;010\;\;\;\;110\;\;\;\;001\;\;\;\;101\;\;\;\;011\;\;\;\;111 \] 可能有人发现，最终的位置刚好就是二进制翻转后的值。注意！是翻转，而不是反转。
那么怎么进行二进制翻转呢？

二进制翻转

对于每一个数，我们一位一位进行翻转。
但这样的时间复杂度是多少呢？一个数有 \(O(log n)\) 位二进制位，总共 \(O(n)\) 个数，因此时间复杂度是 \(O(n\log n)\)，你这不但没有优化常数，反倒有可能增加了常数。

我们不妨令 \(rev(i)\) 表示将数字 \(i\) 在二进制下翻转后的值。我们在求 \(rev(i)\) 的时候，因为是一个数一个数递推的，因此我们已经算过了 \(rev(\left\lfloor\frac{i}{2}\right\rfloor)\)。我们知道 \(\left\lfloor\dfrac{i}{2}\right\rfloor\) 在代码中，是可以通过将 \(i\) 右移一位得到的。所以说这个数翻转后的值再右移一位，也就刚好是原来的数字 \(i\) 除去最低位后反转的值，而对于最低位，特殊处理一下即可。
没太懂的话，可以看一下下面的图。

实现起来代码也很短：

n=(1<<BIT);
for(int i=0;i<n;i++) rev[i]=(rev[i>>1]>>1)|(i&1<<BIT-1);

那么，因为是递推，所以时间复杂度也就是 \(O(n)\) 的，而且我们可以将原先的计算形式从递归改成递推，常数还能更小。

合并答案

根据 FFT 的过程，我们知道它是从小区间贡献到大的区间 \((2\to 4\to 8\to \dots \to n)\)

所以我们利用区间DP的思想（可以这么说吧）。
回顾先前的式子：

\[ f(\omega_{n}^{k})= \begin{cases} p+q,0\le k<\dfrac{n}{2}\\ p-q,\dfrac{n}{2}\le k<n \end{cases} \]

我们便可以写出代码如下：

for(int k=2;k<=n;k*=2){
    fs omega=fs(cos(2*pi/k),sin(z*2*pi/k));
    for(int i=0;i<n;i+=k){
        fs w=fs(1,0);
        for(int j=i;j<i+k/2;j++){
            fs zs=w*c[j+k/2];
            c[j+k/2]=c[j]-zs;
            c[j]+=zs;
            w*=omega;
        }
    }
}

在进行 IFFT 的时候，因为我们用的是单位根的倒数，也就是 \(\omega_{n}^{-k}=\cos\dfrac{k}{n}2\pi-\sin\dfrac{k}{n}2\pi \mathrm{i}\) 可以画图思考一下为什么只需要将 \(\sin\) 的部分变成负的就行了。最后别忘记除以 \(n\)。

三次变两次

不会xwx

代码

P3803 【模板】多项式乘法（FFT）

// Problem: P3803 【模板】多项式乘法（FFT）
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3803
// Memory Limit: 500 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
typedef complex<double> fs;
const int MAXN=4e6+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double pi=acos(-1);
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int N,M,BIT,rev[MAXN];
fs a[MAXN],b[MAXN];

void FFT(fs *s,int opt,int bit){
    int n=(1<<bit);
    for(int i=0;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<bit-1);
    for(int i=0;i<n;i++) if(i<rev[i]) swap(s[i],s[rev[i]]);
    for(int i=2;i<=n;i*=2){
        fs omega=fs(cos(2*pi/i),sin(opt*2*pi/i));
        for(int j=0;j<n;j+=i){
            fs z=fs(1,0);
            for(int k=j;k<j+i/2;k++){
                fs p=s[k],q=z*s[k+i/2];
                s[k]=p+q;
                s[k+i/2]=p-q;
                z*=omega;
            }
        }
    }
    if(opt==-1) for(int i=0;i<n;i++) s[i].real(s[i].real()/n);
}

signed main(){
    read(N,M);
    for(int i=0,A;i<=N;i++) read(A),a[i].real(A);
    for(int i=0,B;i<=M;i++) read(B),b[i].real(B);
    while((1<<BIT)<N+M+1) BIT++;
    FFT(a,1,BIT);FFT(b,1,BIT);
    for(int i=0;i<(1<<BIT);i++) a[i]*=b[i];
    FFT(a,-1,BIT);
    for(int i=0;i<=N+M;i++) cout<<(int)(a[i].real()+0.5)<<" ";
    cout<<endl;
    return 0;
}

其实 NTT 大概就是把单位根改成了 模数对应的原根。

LOADING