引入

前置知识：阶与原根

由于 FFT 使用了单位根，导致了精度误差，于是我们考虑用原根代替单位根。

过程和 FFT 是一样的，学过 FFT 的可以跳过，放个 FFT传送门。

取模数 $p = 998244353$，$g=3$（$p - 1 = 2^{23}\times 119$）。

设 $g_n = g^{\frac{(p - 1)}{n}}$。

原根的性质

• $g_n^k = g_n^{k-1} \cdot g_n$
• $g_n^0 = g_n^n = 1$
• $g_{2n}^{2k} = g_n^k$
• $g_n^{\frac{n}{2}} = g^{\frac{p - 1}{2}} = -1$
• $g_n^{\frac{n}{2} + k} = -g_n^k$

于是发现原根和单位根拥有同样的性质。

快速数论变换

使用 $g_n^k (0\leq k < n)$ 这 $n$ 个不同的数来当作点值表示法中的 $n$ 个 $x$ 。

已知

$$A(x) = \sum_{i=0}^{n-1} a_i * x^i$$

设

$$A_1(x) = a_0 + a_2 \cdot x + a_4 \cdot x^2 + \cdots + a_{n-2} x^{\frac{n}{2}-1}$$

$$A_2(x) = a_1 + a_3 \cdot x + a_5 \cdot x^2 + \cdots + a_{n-1} x^{\frac{n}{2}-1}$$

则

$$A(x) = A_1(x^2) + xA_2(x^2)$$

将 $g_n^k$ 和 $g_n^{\frac{n}{2} + k}(0 \leq k < \frac{n}{2})$ 代入

$$A(g_n^k) = A_1(g_{\frac{n}{2}}^{k}) + g_n^k A_2(g_{\frac{n}{2}}^{k})$$

$$A(g_n^{\frac{n}{2}+k}) = A_1(g_{\frac{n}{2}}^{k}) - g_n^k A_2(g_{\frac{n}{2}}^{k})$$

两个式子 $A_1()$ ，$A_2()$ 相同。

当计算 $[0,\frac{n}{2})$ 时，$[\frac{n}{2},n)$ 可以直接计算。

每次计算量减小一半，时间复杂度 $O(n\log n)$

快速数论逆变换

设 $C(x) = c_0 + c_1 x + c_2 x^2 + \cdots + c_{n - 1} x^{n-1}$

设 $b_i = g_n^i, y_i = C(b_i)$

$C(x)$ 经过 $n$ 个点，$(b_0, y_0) \dots (b_{n - 1}, y_{n - 1})$

引理1

设

$$S(x) = 1 + x + x^2 + \cdots + x^{n-1}$$

因为

$$S(g_n^k) = g_n^0 + g_n^k + g_n^{2k} + \cdots + g_n^{(n-1)k}$$

又

$$g_n^k S(g_n^k) = g_n^k + g_n^{2k} + \cdots + g_n^{(n-1)k} + g_n^{nk}$$

所以

若 $k\ne 0$

则

$$S(g_n^k) = \frac{0}{1 - g_n^k} = 0$$

若 $k=0$

则

$$S(g_n^k) = n$$

引理2

$$nc_k = \sum_{i=0}^{n-1} y_i (g_n^{-k})^i$$

证明

$$\sum_{i=0}^{n-1} y_i (g_n^{-k})^i$$

$$=\sum_{i=0}^{n-1} (\sum_{j=0}^{n-1} c_j {(g_n^i)}^{j}) (g_n^{-k})^i$$

$$=\sum_{i=0}^{n-1} (\sum_{j=0}^{n-1} c_j {(g_n^j)}^{i}) (g_n^{-k})^i$$

$$=\sum_{i=0}^{n-1} (\sum_{j=0}^{n-1} c_j {(g_n^{j - k})}^{i})$$

$$=\sum_{j=0}^{n-1} c_j \sum_{i=0}^{n-1} (g_n^{j-k})^{i}$$

$$=\sum_{j=0}^{n-1} c_j S(g_n^{j-k})$$

$$=nc_k$$

证毕

设

$$D(x) = \sum_{i=0}^{n-1} y_i x^i$$

则

$$c_k = \frac{D(g_n^{-k})}{n}$$

所以再做一次快速数论变换即可

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 4000010, M = 25, g = 3, gi = 332748118, mod = 998244353;
ll a[N], b[N];

int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return res;
}

struct Poly {
    int rev[1 << M];
    void init(int bit) {
        for (int i = 0; i < (1 << bit); i ++ )
            rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (bit - 1));
    } void ntt(ll *a, int n, int Inv = 0) {
        for (int i = 0; i < n; i ++ ) if (i < rev[i]) swap(a[i], a[rev[i]]);
        for (int i = 1; i < n; i <<= 1) {
            ll gn = qpow(Inv ? gi : g, (mod - 1) / (i << 1));
            for (int j = 0; j < n; j += (i << 1)) {
                ll gk = 1;
                for (int k = 0; k < i; k ++ , gk = gk * gn % mod) {
                    ll x = a[j + k], y = gk * a[i + j + k] % mod;
                    a[j + k] = (x + y) % mod, a[i + j + k] = (x - y + mod) % mod;
                }
            }
        } if (Inv) {
            ll inv = qpow(n, mod - 2);
            for (int i = 0; i < n; i ++ ) a[i] = a[i] * inv % mod;
        }
    }
} poly;

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n; i ++ ) scanf("%lld", &a[i]);
    for (int i = 0; i <= m; i ++ ) scanf("%lld", &b[i]);
    int bit = 0;
    while ((1 << bit) <= n + m) bit ++ ;
    poly.init(bit);
    poly.ntt(a, 1 << bit);
    poly.ntt(b, 1 << bit);
    for (int i = 0; i < (1 << bit); i ++ ) a[i] = a[i] * b[i] % mod;
    poly.ntt(a, 1 << bit, 1);
    for (int i = 0; i <= n + m; i ++ ) printf("%lld ", a[i]);
    return 0;
}