代码

#include <bits/stdc++.h>
using namespace std;
using u32 = unsigned;
using u64 = unsigned long long;
const u32 S = 1 << 22, Mod = 998244353;

inline constexpr u32 Ub(u32 x) { return 1 << (__lg(x) + 1); }
inline constexpr u32 Mt(u32 x) { return x >= Mod ? x - Mod : x; }
inline constexpr u32 Mul(u32 x, u32 y) { return (u64)x * y % Mod; }
inline constexpr u32 Pw(u32 x, u32 y) {
    u32 r = 1;
    for(; y; x = Mul(x, x), y >>= 1)
        if(y & 1) r = Mul(r, x);
    return r;
}

u32 w[S];
inline void Init(const u32 N) {
    u32 p[23] = { 31 }, *q = p + 22;
    for(u32 i = 1; i <= 28; ++i) p[i] = Mul(p[i - 1], p[i - 1]);
    for(u32 len = 1, i; len < N; len <<= 1, --q)
        for(w[i = len] = 1, ++i; i < (len << 1); ++i) w[i] = Mul(w[i - 1], *q);
}
inline void DIF0(u32 &x, u32 &y, const u32 w) {
    const u32 u = x, v = y;
    x = Mt(u + v), y = Mul(u - v + Mod, w);
}
inline void DIT0(u32 &x, u32 &y, const u32 w) {
    const u32 u = x, v = Mul(y, w);
    x = Mt(u + v), y = Mt(u - v + Mod);
}
template<void (*Trans)(u32&, u32&, u32)>
inline void Work(u32 A[], const u32 N, const u32 len) {
    const u32 R = len << 1;
    for(u32 i = 0, *p = A; i < N; i += R, p = A + i)
        for(u32 j = len; j < R; ++j, ++p) Trans(*p, p[len], w[j]);
}
void DIF(u32 A[], const u32 N) {
    for(u32 len = N >> 1; len; len >>= 1) Work<DIF0>(A, N, len);
}
inline void DIT(u32 A[], const u32 N) {
    for(u32 len = 1; len < N; len <<= 1) Work<DIT0>(A, N, len);
    reverse(A + 1, A + N);
    const u32 v = Pw(N, Mod - 2);
    for(u32 i = 0; i < N; ++i) A[i] = Mul(A[i], v);
}

u32 A[S], B[S], n, m;
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c)
{
	for(u32 i = 0; i <= n; ++i) A[i]=a[i];
    for(u32 i = 0; i <= m; ++i) B[i]=b[i];
    const u32 N = Ub(n + m + 2);
    Init(N), DIF(A, N), DIF(B, N);
    for(u32 i = 0; i < N; ++i) A[i] = Mul(A[i], B[i]);
    DIT(A, N);
    for(u32 i = 0; i <= n + m; ++i) c[i]=A[i];
}

评测结果