本节点所需要的前置研发项目:多项式基础FFT(快速傅里叶变换)

FFT 的局限性

上一篇文章讲了 FFT。那么 FFT 有什么局限性呢?

  • 精度不够高
  • 复数运算常数大
  • 不能取模

那么有什么东西能在取模意义下替代单位根呢?

原根

这种东西叫做原根,记为 $g$

设m是正整数,a是整数,若a模m的阶等于φ(m),则称a为模m的一个原根。

如果模数 p 为素数,那么 $g^i \mod p(0<i<p)$ 的结果两两不同

Q:原根怎么求?

A:这不在本文研究的范围内。写 NTT 不需要求原根,只需要背原根(一般都是 3)。

NTT

于是这东西和单位根有相同的性质。如果把 FFT 里面的单位根全都换成原根就可以了。

由于我们需要求出 $2^k$ 次原根,所以 NTT 对模数的要求很严格,NTT 模数必须是形如 $k\times2^n+1$ 的素数。

比较常见 NTT 模数有 998244353、1004535809 等。这两个数的原根都是 3。

然后改一下板子。你会发现这玩意比 FFT 好写且好用得多。

注意随时取模。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
#define int long long
using namespace std;

int get() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}

const int N = 3e6 + 5, P = 998244353, G = 3, iG = 332748118;
// P:模数,G:原根,iG:原根的逆元
int n, m;
int a[N], b[N];
int lim = 1, l, r[N];

int qpow(int x, int y) {
int res = 1;
while(y) {
if(y & 1) res = (res * x) % P;
x = (x * x) % P;
y >>= 1;
}
return res;
}

void NTT(int *A, int type) {
for(int i = 0; i < lim; i++) if(i < r[i]) swap(A[i], A[r[i]]);
for(int mid = 1; mid < lim; mid <<= 1) {
int Wn = qpow(type == 1? G : iG, (P - 1) / (mid << 1)); // 本原单位根
for(int i = 0; i < lim; i += (mid << 1)) {
int w = 1;
for(int j = 0; j < mid; j++, w = (w * Wn) % P) {
int x = A[i + j], y = (w * A[i + mid + j]) % P;
A[i + j] = (x + y) % P;
A[i + mid + j] = (x - y + P) % P;
}
}
}
}

signed main() {
n = get(), m = get();
for(int i = 0; i <= n; i++) a[i] = get();
for(int i = 0; i <= m; i++) b[i] = get();
while(lim <= n + m) lim <<= 1, l++;
for(int i = 0; i < lim; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
NTT(a, 1), NTT(b, 1);
for(int i = 0; i < lim; i++) a[i] = (a[i] * b[i]) % P;
NTT(a, -1);
int inv = qpow(lim, P - 2);
for(int i = 0; i <= n + m; i++) printf("%d ", (inv * a[i]) % P);
return 0;
}

对比

FFT 和 NTT 的对比

项目 运行速度 代码长度 内存 取模 实数运算 精度
FFT 2.11s 1.68k 161.76MB 不支持 支持 一般
NTT 2.06s 1.40k 53.23MB 支持 不支持 较高

其中运行速度是通过模板的速度,不开启 O2 优化,代码长度以我的码风为准。