专栏文章
NTT 入门
个人记录参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @miqeiprg
- 此快照首次捕获于
- 2025/12/04 03:30 3 个月前
- 此快照最后确认于
- 2025/12/04 03:30 3 个月前
牢记目标：对于一个给定的 次的多项式（），我们要求出 个点 代进去的点值，有了点值我们可以进行多项式乘法等内容。
把多项式奇偶分类，。
由于我们递归下去要规模减半，考虑对点值分成两半，显然 ，所以偶次多项式的后一半点值等价于前一半点值，奇次多项式的后一半点值是前一半点值取反。
把点值还原成多项式（）时，结论是指数上多一个负号，得到的结果应除以长度。
考虑构造一个多项式 ，然后对其推式子。
\\&=\sum_{(i,j)}a_j\omega_m^{i(j-k)}\end{aligned}$$
这里实质是一个单位根反演，我们发现 $j=k$ 时每个 $i$ 的贡献均为 $1$，$j\ne k$ 时所有 $i$ 的贡献和为 $0$，所以 $G(\omega^{-k})=ma_k$，所以求解 $\rm IDFT$ 时只需把 $\omega$ 换成 $\omega^{-1}$ 并在最后除掉总长度即可。
值得注意的是，如果我们并不把指数取反，而是代入原来的指数，那根据单位根的性质，其实我们相当于倒着代入了负指数，所以最后加一个 `reverse` 即可。
注意是从 $1$ 开始的 $\rm reverse$，因为 $\omega^0=\omega^{-0}$。
单位根换成原根后我们可以得到一个递归写法：
```cpp
const int g=3,p=998244353;
ll ksm(ll a,ll n=p-2,ll res=1) {
for(;n;n>>=1,a=a*a%p) if(n&1) res=res*a%p;
return res;
}
void NTT(ll w,vec<ll> &a) {
if(sz(a)==1) return;
int n=sz(a);
vec<ll> b[2]{vec<ll>(n/2),vec<ll>(n/2)};
F(i,0,n-1) b[i&1][i>>1]=a[i];
NTT(w*w%p,b[0]);NTT(w*w%p,b[1]);
ll r=1;
F(i,0,n/2-1) {
a[i]=(b[0][i]+r*b[1][i])%p;
a[i+(n/2)]=(b[0][i]+(p-r)*b[1][i])%p;
(r*=w)%=p;
}
}
void DFT(vec<ll> &a) {NTT(ksm(g,(p-1)/sz(a)),a);}
void IDFT(vec<ll> &a) {
NTT(ksm(ksm(g,(p-1)/sz(a))),a);
ll iv=ksm(sz(a));
for(ll &x:a) (x*=iv)%=p;
}
```
为了减小常数，我们通常要将分治的过程循环化，我们发现我们先从上往下进行了奇偶分类，再自底向上合并。
如果我们要用循环代替递归，此时我们如何处理“奇偶分类”？
我们发现，奇偶分类恰恰是把最低位提到了最高位，所有奇偶分类都做完之后相当于二进制 $\rm reverse$。
这个过程叫蝴蝶变换，我们可以用 $\frac i 2$ 的 $\rm reverse$ 推出 $i$ 的 $\rm reverse$，由此我们可以求出蝴蝶变换的位置：
```c_cpp
F(i,0,(1<<n)-1) r[i]=r[i>>1]>>1|((i&1)<<n-1);
```
处理完奇偶分类后，我们就从底向上进行合并过程，这部分就直接抄过来即可。
```cpp
void NTT(vec<ll> &a,bool type) {
int n=sz(a),l=__lg(n);
vec<int> r(n);
F(i,0,n-1) r[i]=r[i>>1]>>1|(i&1)<<l-1;
F(i,0,n-1) if(i<r[i]) swap(a[i],a[r[i]]);
for(int m=1;m<n;m*=2) {
ll w=ksm(type?g:ksm(g),(p-1)/(m*2));
for(int j=0;j<n;j+=m*2) {
ll r=1;
F(i,j,j+m-1) {
ll x=a[i],y=r*a[i+m]%p;
a[i]=(x+y)%p;a[i+m]=(x+p-y)%p;
(r*=w)%=p;
}
}
}
if(!type) {
ll iv=ksm(n);
F(i,0,n-1) (a[i]*=iv)%=p;
}
}
void DFT(vec<ll> &a) {NTT(a,1);}
void IDFT(vec<ll> &a) {NTT(a,0);}
```
这是一份符合大多数人刻板印象的 NTT 模板。
## DIT 与 DIF
上文所述的 $\rm DFT$ 方式属于 $\rm DIT$，按时域抽取，这里的按时域抽取指的是把多项式系数进行奇偶分类。
事实上，我们存在另一种 $\rm DFT$ 方式：$\rm DIF$，按频域抽取，指的是把代入的点进行奇偶分类。
考虑 $\omega$ 的奇偶性，也就是把多项式按照前后劈开：
$$\begin{aligned}\text{DFT}(a)_k&=\sum_{i=0}^{n-1}\omega_{n}^{ki}a_i
\\&=\sum_{i=0}^{n/2-1}(a_i+(-1)^ka_{i+n/2})\omega_{n}^{ki}\end{aligned}$$
当 $2\mid k$ 时：
$$\begin{aligned}\text{DFT}(a)_k&=\sum_{i=0}^{n/2-1}(a_i+a_{i+n/2})\omega_{n}^{ki}
\\&=\sum_{i=0}^{n/2-1}(a_i+a_{i+n/2})\omega_{n/2}^{(k/2)i}
\\&=\text{DFT}(a\text{ 前后对应位置相加})_{k/2}\end{aligned}$$
$2\nmid k$ 时略有不同：
$$\begin{aligned}\text{DFT}(a)_k&=\sum_{i=0}^{n/2-1}(a_i-a_{i+n/2})\omega_{n}^{ki}
\\&=\sum_{i=0}^{n/2-1}(a_i-a_{i+n/2})\omega_{n/2}^i\omega_{n/2}^{[k/2]i}
\\&=\text{DFT}(\{(a_i-a_{i+n/2})\omega_{n/2}^i\})_{k/2}\end{aligned}$$
想象它的递归写法，我们在向下递归时进行值的变换（实质是乘上范德蒙德矩阵），在回溯时进行蝴蝶变换，刚好与 $\rm DIT$ 的过程是相反的。
那么，只要我们在 $\rm DFT$ 时使用 $\rm DIF$，$\rm IDFT$ 时使用 $\rm DIT$，就可以免去蝴蝶变换了。
```cpp
void DIF(vec<ll> &a) {
int n=sz(a);
for(int m=n/2;m;m/=2) {
ll w=ksm(g,(p-1)/(m*2));
for(int j=0;j<n;j+=m*2) {
ll r=1;
F(i,j,j+m-1) {
ll x=a[i],y=a[i+m];
a[i]=(x+y)%p;a[i+m]=(x+p-y)*r%p;
(r*=w)%=p;
}
}
}
}
void DIT(vec<ll> &a) {
int n=sz(a);
for(int m=1;m<n;m*=2) {
ll w=ksm(ksm(g),(p-1)/(m*2));
for(int j=0;j<n;j+=m*2) {
ll r=1;
F(i,j,j+m-1) {
ll x=a[i],y=r*a[i+m]%p;
a[i]=(x+y)%p;a[i+m]=(x+p-y)%p;
(r*=w)%=p;
}
}
}
ll iv=ksm(n);
F(i,0,n-1) (a[i]*=iv)%=p;
}
```
看上去代码长，实际上二者逻辑相似，复制粘贴就很容易敲出。
比较简单的卡常方法：预处理单位根幂次，[提交记录](https://www.luogu.com.cn/record/200479629)。
虽然经过仔细卡常，$10^6$ 规模的数据还可以把速度提升至原来的 [两倍](https://www.luogu.com.cn/record/196677422)，但具体内容已脱离有趣的理论范畴，且实战中并无用处，所以舍弃。
### MTT
也就是任意模数 $\rm NTT$。
给一个使用 $5$ 次 $\rm FFT$ 的做法，较为舒服。
首先我们把系数变小，$F(x)=A(x)+cB(x),G(x)=C(x)+cD(x)$，其中 $c=\sqrt V$，取 $2^{15}$ 即可。
然后多项式相乘展开，相当于我们要求 $A(x)C(x),A(x)D(x),B(x)C(x),B(x)D(x)$，构造 $T(x)=C(x)+iD(x)$，则我们能在 $A(x)T(x)$ 与 $B(x)T(x)$ 中找到所需的项。
只需三次 $\rm DFT$，两次 $\rm IDFT$ 即可。
由于我们要做很多次 $\rm FFT$，所以预处理单位根就能很大程度上提高效率。
### 三次变两次优化
也就是只需要一遍 $\rm DFT$ 一遍 $\rm IDFT$ 求出 $f*g$，它利用了 $(f+gi)^2=f^2-g^2+2fgi$，所以我们只需对 $(f+gi)$ 进行 $\rm DFT$ 即可。这玩意跑的比 $\rm NTT$ 快。
但是能 $\rm FFT$ 还无需 $\rm MTT$ 的场合太少了。
## 参考资料
[再探 FFT – DIT 与 DIF，另种推导和优化](https://charleswu.site/archives/3065)
[模板 P4245题解 - Prean](https://www.luogu.com.cn/article/0q83s0oh)相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...