快速数论变换(NTT)

OI-算法

部分内容参考文献
本文作者$\operatorname{dxbdly}$，引用或转载请注明原文链接

1. 前言

上篇文章，我们介绍了求解多项式乘法的一种算法 $\text{FFT}$，不清楚的读者请阅读文章

但 $\text{FFT}$ 需要用到复数类，常数较大且容易出现精度误差。

而 $\text{NTT}$ 可以很好的解决这两个问题，它是一种基于 原根 进行 $\text{DFT}$ 的算法。

2. 原根

$\text{NTT}$ 仍采取点值表示，研究数值表示转点值表示，点值表示转数值表示两个问题。

解决这两个问题的方法，与 $\text{FFT}$ 完全一样，只不过 $\text{NTT}$ 改变了点值表示中取的点。

它采取 原根 代替单位复根，以此避免复数计算

$1^o$ 阶

若 $a \perp p$ ，且 $p > 1$ ，则称满足 $a ^ n \equiv 1 \pmod p$ 的最小的 $n$ 为 $a$ 在模 $p$ 意义下的阶，记为 $\delta_p(a)$

$2^o$ 原根的定义

对于正整数 $p$ ，整数 $a$ ，若满足 $\delta_p(a) = \Phi(p)$ ，则称 $a$ 为模 $p$ 意义下的原根

注意：

原根个数不唯一，且如果模数 $p$ 有原根，则必有 $\Phi(\Phi(p))$ (不重要，不证了)

后文 $g$ 均指模 $p$ 意义下的原根

$3 ^ o$ 原根的性质

前面提到了，我们希望用原根代替单位根，那么，先要构造一个不重复的 $n + 1$ 项序列。

重要性质：

若 $p$ 为质数，那么 $g^i \bmod p(1 < g < p, 0 < i < p)$ 各不相同
证明：考虑费马小定理：$g^{p - 1} \equiv 1\pmod p$

所以只要取 $g_n^i$ 即可满足，但我们在 $\text{FFT}$ 中还用到了关于单位复根的几个性质。

可以发现原根均可满足：

所以：

$w_n$ 在模 $p$ 意义下有：

3. $\text{NTT}$ 实现 $\text{DFT}$ 与 $\text{IDFT}$

由于 $\text{NTT}$ 要在模意义下进行，所以我们得先选好模数。

我们一般选择模数为 $998244353$ ，它的原根是 $3$ ，逆元是 $332748118$

对于 $\text{DFT}$ ，将所有 $w_n$ 换为 $g_n$ 即可，记得每一步操作都需要取模。

对于 $\text{IDFT}$ ，还是构造逆矩阵，将 $g_n$ 的底数改为逆元，可同理与 $\text{DFT}$ 一起进行，注意输出时要乘 $n$ 的逆元

4. 模板

模板题

代码：

//The code is from dxbdly
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 3e6 +5, mod = 998244353, g = 3, gi = 332748118;
int n, m;
int g1[maxn], g2[maxn], rev[maxn];
inline int Ksm(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;
        a = a * a % mod, b >>= 1;
    }
    return res;
}
inline void Change(int f[], int len) {
    for(register int i = 0; i < len; ++i) {
        rev[i] = (rev[i >> 1] >> 1);
        if(i & 1) rev[i] |= (len >> 1);
    }
    for(register int i = 0; i < len; ++i) 
        if(i < rev[i]) swap(f[i], f[rev[i]]);
}
inline void NTT(int f[], int len, int op) {
    Change(f, len);
    for(register int h = 2; h <= len; h <<= 1) {
        int wn = Ksm((op == 1 ? g : gi), (mod - 1) / h);
        for(register int i = 0; i < len; i += h) {
            int w = 1;
            for(register int k = i; k < i + h / 2; ++k) {
                int G = f[k], H = (w * f[k + h / 2]) % mod;
                f[k] = (G + H) % mod , f[k + h / 2] = (G - H + mod) % mod;
                w = (w * wn) % mod;
            }
        }
    }
}
signed main() {
    n = read() + 1, m = read() + 1;
    for(register int i = 0; i < n; ++i) g1[i] = (read() + mod) % mod;
    for(register int i = 0; i < m; ++i) g2[i] = (read() + mod) % mod;
    int len = 1;
    while(len < n * 2 || len < m * 2) len <<= 1;
    NTT(g1, len, 1), NTT(g2, len, 1);
    for(register int i = 0; i < len; ++i) g1[i] = (g1[i] * g2[i]) % mod;
    NTT(g1, len, -1);
    int inv = Ksm(len, mod - 2);
    for(register int i = 0; i < m + n - 1; ++i) printf("%d ", (g1[i] * inv) % mod);
    return 0;
}

注意：
全部都需取模，中间运算可能爆 $\text{int}$，要开 $\text{longlong}$ 。

5. $\text{The End}$

$\text{NTT}$ 是一种从 $\text{FFT}$ ，发展而来的算法，需要读者对 $\text{FFT}$ 有比较清晰的了解。

$\text{NTT}$ 的缺点与优点很明显：

优点：$\text{NTT}$ 常数更小，且不需要进行复数运算，精度误差小。

缺点：$\text{NTT}$ 十分依赖模数，如果题目对模数有限制，则只能考虑 $\text{FFT}$ 或 $\text{MTT}$ (任意模数 $\text{NTT}$ )

作为多项式乘法中可以说最常用的算法，需要大家仔细了解。

希望此文章能给您带来帮助，感谢观看。

部分内容参考文献
本文作者$\text{dxbdly}$，引用或转载请注明原文链接

$$\text{Q.E.D}$$