NTT
Contents
模版
NTT
const int mod = 998244353;
const int maxn = (1<<22) + 5;
struct NTT {
const ll g = 3, invg = inv(g); // mod = 998244353
inline ll qpow(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
inline ll inv(ll a) {
return qpow(a, mod-2);
}
void rearrange(ll a[], const int n) {
static int rev[maxn]; // maxn > deg(h) 且 maxn 为 2的k次方 + 5
for (int i = 1; i <= n; i++) {
rev[i] = rev[i >> 1] >> 1;
if (i & 1) rev[i] |= (n >> 1);
}
for (int i = 1; i < n; i++) {
if (i < rev[i]) swap(a[i], a[rev[i]]); // 保证每对数字只翻转一次
}
}
void ntt(ll a[], const int n, int on) {
rearrange(a, n);
for (int k = 2; k <= n; k <<= 1) { // 模拟分治的合并过程
ll wn = qpow(on == 1 ? g : invg, (mod-1)/k);
for (int i = 0; i < n; i += k) {
ll w = 1;
for (int j = i; j < i + (k>>1); j++) {
ll x = a[j], y = w * a[j+(k>>1)] % mod;
a[j] = (x + y) % mod;
a[j+(k>>1)] = (x - y + mod) % mod;
w = w * wn % mod;
}
}
}
if (on == -1) {
ll invn = inv(n);
for (int i = 0; i < n; i++) a[i] = a[i] * invn % mod;
}
}
} ntt;
// calculate h(x) = f(x) * g(x), n1 = deg(f) + 1, n2 = deg(g) + 1
void poly_multiply(ll f[], int n1, ll g[], int n2, ll h[]) {
int n = 1;
n1--, n2--;
while (n <= n1 + n2) n <<= 1; // deg(h) = n1 + n2
memset(h, 0, sizeof(ll) * n);
ntt.ntt(f, n, 1); // 注意这里用的是 n (不是 n1)
ntt.ntt(g, n, 1);
for (int i = 0; i < n; i++) h[i] = f[i] * g[i] % mod;
ntt.ntt(h, n, -1);
}
int n1, n2;
ll f[maxn/2], g[maxn/2], h[maxn];
int main() {
cin >> n1 >> n2; // deg(f) = n1 - 1, deg(g) = n2 - 1
for (int i = 0; i < n1; i++) cin >> f[i];
for (int i = 0; i < n2; i++) cin >> g[i];
poly_multiply(f, n1, g, n2, h);
for (int i = 0; i <= n1+n2-2; i++) cout << h[i] << " ";
}
介绍
NTT（快速数论变换）和 FFT 一样，都是用来解决多项式乘法问题。
NTT可以处理在 $mod ~ p$ 意义下的多项式乘法，并且不需要处理复数和小数。
在开始介绍 NTT 之前，我们需要一些基本的前置知识。
原根
对于一个质数 $p$，在 $mod ~ p$ 意义下，原根 $g$ 满足：
$$ord(g) = |Z_p^{\times}| = \phi(p)$$
• 注意 $\phi(p)$ 是 $p$ 的欧拉函数，代表 $[1,p]$ 中与 $p$ 互质的数的数量。
• $ord(g)$ 代表一个最小的数字 $r = ord(g)$ 使得 $g^r \equiv 1(mod ~ p)$，且 $\forall k \in [1,r-1], g^k \neq 1(mod ~ p)$
NTT原理
使用 NTT 的限制条件：
- 模数 $p$ 需要满足 $p = k \times 2^m + 1$，其中 $k, m \geq 1$，$p$ 为质数。
- 若 $p = k \times 2^m + 1$，则只能处理 $deg(h) \leq 2^m$ 的情况。
在发现了原根 $g$ 以后，我们会发现令 $g_n = g^{\frac{p-1}{n}}$，则 $g_n$ 拥有着 FFT 中，$\omega$ 的优秀性质：
- $g_n^n = 1$，且 $\forall k \in [1, n-1], g_n ^ k \neq 1$
- $g_n^{k+\frac{n}{2}} = -g_n^{k}$
证明：
- 根据原根的定义即可。
- 只要证 $g_n^{\frac{n}{2}} = -1$ 即可。因为 $g_n^n = 1$，所以 $g_n^{\frac{n}{2}} = \pm 1$，而因为 $\forall k \in [1, n-1], g_n ^ k \neq 1$，所以 $g_n^{\frac{n}{2}} = -1$
剩下的就和 FFT 一样了，只不过把 $\omega$ 换成 $g_n = g^{\frac{p-1}{n}}$ 而已。
当然注意到，由于 $n$ 需要是 $2^k$，所以 $p-1$ 需要是 $2^k$ 的倍数，故我们需要满足 $p = k \times 2^m + 1$。
常用的组合：
$$p = 998244353, ~~g = 3$$