NTT 模板。模数为 998244353 的情形，998244353 的最小原根为 3

模板-NTT.cpp

using poly = vector<int>;


void bit_reverse_swap(poly &a) {
    int n = SZ(a);
    for (int i = 1, j = n >> 1, k; i < n - 1; i++) {
        if (i < j) swap(a[i], a[j]);
        //tricky
        for (k = n >> 1; j >= k; j -= k, k >>= 1);    //inspect the highest "1"
        j += k;
    }
}

const int g = 3; // mod 998244353 下的最小原根
void FFT(poly &a, int type) {
    bit_reverse_swap(a);
    int n = SZ(a);
    for (int i = 2; i <= n; i *= 2) {
        const auto wi = fp(g, type * (mod - 1) / i); // fp(g, (mod - 1) / i) 是 i 次单位根
        for (int j = 0; j < n; j += i) {
            auto w(1);
            for (int k = j, h = i / 2; k < j + h; k++) {
                auto t = Mul(w, a[k + h]), u = a[k];
                a[k] = Add(u, t);
                a[k + h] = Sub(u, t);
                mul(w, wi);
            }
        }
    }
    const int inv = fp(n, -1);
    if (type == -1) for (auto &x : a) mul(x, inv);
}


void mul(poly &a, const poly &b) {
    int n = pow2(SZ(a) + SZ(b) - 1);
    auto _b = b;
    a.resize(n), _b.resize(n);
    FFT(a, 1), FFT(_b, 1);
    rng (i, 0, n) mul(a[i], _b[i]);
    FFT(a, -1);
}


void fp(poly &a, const int n) {
    a.resize((ul)pow2((SZ(a)-1) * n + 1));
    FFT(a, 1);
    for(auto &x: a) x = fp(x, n);
    FFT(a, -1);
}