模版

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 的限制条件:

  1. 模数 $p$ 需要满足 $p = k \times 2^m + 1$,其中 $k, m \geq 1$,$p$ 为质数。
  2. 若 $p = k \times 2^m + 1$,则只能处理 $deg(h) \leq 2^m$ 的情况。

在发现了原根 $g$ 以后,我们会发现令 $g_n = g^{\frac{p-1}{n}}$,则 $g_n$ 拥有着 FFT 中,$\omega$ 的优秀性质:

  1. $g_n^n = 1$,且 $\forall k \in [1, n-1], g_n ^ k \neq 1$
  2. $g_n^{k+\frac{n}{2}} = -g_n^{k}$

证明:

  1. 根据原根的定义即可。
  2. 只要证 $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$$

参考链接

  1. https://blog.csdn.net/a_forever_dream/article/details/102469390
  2. https://oi-wiki.org/math/poly/ntt/