代码

#include <algorithm>

typedef long long ll;

const int N = 2100000, S = N;
const int cIz = 998244353, g_cIz = 3;

inline int _(int a) { return a + ((a >> 31) & cIz); }

inline int __(int a) { return a - (((cIz - 1 - a) >> 31) & cIz); }

inline int Pow(int a, int b) {
    int ans = 1;
    for (; b; b >>= 1) {
        if (b & 1)
            ans = (ll)ans * a % cIz;
        a = (ll)a * a % cIz;
    }
    return ans;
}
inline int Inv(int a) { return Pow(a, cIz - 2); }

inline int getn(int m) {
    int n = 1;
    while (n < m) n <<= 1;
    return n;
}

int rev[S];
inline void init_rev(int n) {
    rev[0] = 0;
    for (int i = 1; i < n; ++i) {
        rev[i] = rev[i >> 1] >> 1 | ((i & 1) * n) >> 1;
    }
}

void NTT(int *f, int n, bool flag) {
    for (int i = 0; i < n; ++i) {
        if (i < rev[i])
            std::swap(f[i], f[rev[i]]);
    }
    const int g = flag ? Inv(g_cIz) : g_cIz;
    for (int i = 1; i < n; i <<= 1) {
        const int e = Pow(g, (cIz - 1) / (i << 1));
        for (int j = 0; j < n; j += i << 1) {
            int w = 1;
            for (int k = 0; k < i; ++k) {
                int tmp = (ll)w * f[j | k | i] % cIz;
                f[j | k | i] = _(f[j | k] - tmp);
                f[j | k] = __(f[j | k] + tmp);
                w = (ll)w * e % cIz;
            }
        }
    }
    if (flag) {
        const int inv_n = Inv(n);
        for (int i = 0; i < n; ++i) f[i] = (ll)f[i] * inv_n % cIz;
    }
}

void poly_mul(const int *A, const int *B, int *C, int n) {
    static int a[S], b[S];
    init_rev(n);
    std::copy(A, A + n, a);
    std::copy(B, B + n, b);
    NTT(a, n, 0);
    NTT(b, n, 0);
    for (int i = 0; i < n; ++i) C[i] = (ll)a[i] * b[i] % cIz;
    NTT(C, n, 1);
}

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c)
{
    ++n;
    ++m;
    poly_mul(a, b, c, getn(n + m - 1));
}

评测结果