代码

#include <cstring>
#include <algorithm>
#define len 2097152
#define p 998244353
#define g 3

namespace number {
    inline int add(int x, int y) { return (x += y) >= p ? x - p : x; }
    inline int sub(int x, int y) { return (x -= y) < 0 ? x + p : x; }
    inline int mul(int x, int y) { return (long long)x * y % p; }
    inline int power(int x, int y) { int ans = 1; for (; y; y >>= 1) { if (y & 1) ans = mul(ans, x); x = mul(x, x); } return ans; }
}

using namespace number;

namespace poly {
    int N, l;
    int w[len], r[len], t[len];
    inline void init(int n) {
        N = 2, l = 1;
        while (N < n) N <<= 1, ++l;
        for (int i = 0; i < N; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
        int wn = power(g, (p - 1) >> l);
        w[N >> 1] = 1;
        for (int i = (N >> 1) + 1; i < N; ++i) w[i] = mul(w[i - 1], wn);
        for (int i = (N >> 1) - 1; i; --i) w[i] = w[i << 1];
    }
    inline void NTT(int *a, int n, int opt) {
        int shift = l - __builtin_ctz(n);
        for (int i = 0; i < n; ++i) t[r[i] >> shift] = a[i];
        memcpy(a, t, n << 2);
        for (int i = 1; i < n; i <<= 1)
            for (int j = 0; j < n; j += i << 1)
                for (int k = 0; k < i; ++k) {
                    int x = a[j + k], y = mul(a[i + j + k], w[i + k]);
                    a[j + k] = add(x, y);
                    a[i + j + k] = sub(x, y);
                }
        if (opt == -1) {
            int x = power(n, p - 2);
            for (int i = 0; i < n; ++i) a[i] = mul(a[i], x);
            std::reverse(a + 1, a + n);
        }
    }
}

int A[len], B[len];

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
    for (int i = 0; i <= n; ++i) A[i] = a[i];
    for (int i = 0; i <= m; ++i) B[i] = b[i];
    poly::init(n + m + 1);
    poly::NTT(A, poly::N, 1);
    poly::NTT(B, poly::N, 1);
    for (int i = 0; i < poly::N; ++i) A[i] = mul(A[i], B[i]);
    poly::NTT(A, poly::N, -1);
    for (int i = 0; i <= n + m; ++i) c[i] = A[i];
}

评测结果