代码

#include <algorithm>
#include <cstring>

typedef unsigned int uint;
typedef long long unsigned int uint64;

constexpr uint Max_size = 1 << 21 | 5;
constexpr uint g = 3, Mod = 998244353;

inline uint norm_2(const uint x) {
    return x < Mod * 2 ? x : x - Mod * 2;
}

inline uint norm(const uint x) {
    return x < Mod ? x : x - Mod;
}

inline uint Mod_mult(const uint x, const uint y) { // 32-bit computing
    uint64 t = (unsigned long long)x*y;
    unsigned h = (t>>29) * 2309898375ULL >> 32;
    unsigned z = t-(uint64)h*Mod;
    return norm(z);
}

struct Z {
    uint v;
    Z() { }
    Z(const uint _v) : v(_v) { }
};

inline Z operator+(const Z &x1, const Z &x2) {
    return x1.v + x2.v < Mod ? x1.v + x2.v : x1.v + x2.v - Mod;
}
inline Z operator-(const Z &x1, const Z &x2) {
    return x1.v >= x2.v ? x1.v - x2.v : x1.v + Mod - x2.v;
}
inline Z operator*(const Z &x1, const Z &x2) {
    return Mod_mult(x1.v, x2.v);
}
inline Z &operator*=(Z &x1, const Z &x2) {
    x1.v = Mod_mult(x1.v, x2.v);
    return x1;
}
Z Power(Z Base, int Exp) {
    Z res = 1;
    for (; Exp; Base *= Base, Exp >>= 1)
        if (Exp & 1)
            res *= Base;
    return res;
}
void fft(Z* a, uint n) {
    for (uint i=n; i>>=1; ) {
		Z w=Power(941749573, 4194304/2/i);
        for (uint j=0; j<n; j+=i<<1) {
            Z *b=a+j, *c=b+i, ptr=1;
            for (uint k=0; k<i; ++k) {
                Z s=b[k], t=c[k];
                b[k] = s+t; c[k] = (s-t)*ptr;
                ptr *= w;
            }
        }
    }
}
void ifft(Z* a, uint n) {
    for (uint i=1; i<n; i<<=1) {
		Z w=Power(749268343, 4194304/2/i);
        for (uint j=0; j<n; j+=i<<1) {
            Z* b=a+j, *c=b+i, ptr=1;
            for (uint k=0; k<i; ++k) {
                Z s=b[k], t=c[k]*ptr;
                b[k] = s+t; c[k] = s-t;
                ptr *= w;
            }
        }
    }
}

Z A[Max_size], B[Max_size];

void poly_multiply(uint _A[], int N, uint _B[], int M, uint _C[]) {
    memcpy(reinterpret_cast<uint *>(A), _A, (N + 1) * sizeof(uint));
    memcpy(reinterpret_cast<uint *>(B), _B, (M + 1) * sizeof(uint));

    int L;
    for (L = 2; L <= N + M; L <<= 1)
        ;

    fft(A, L), fft(B, L);
    Z ms = Power(L, Mod-2);
    for (int i = 0; i != L; ++i)
        A[i] *= B[i] * ms;
    ifft(A, L);

    memcpy(_C, reinterpret_cast<uint *>(A), (N + M + 1) * sizeof(uint));
}

评测结果