代码

#include <algorithm>
#include <vector>
#include <cstdio>
#include <string.h>
#include <random>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll Q = 998244353, G = 3;
const int MaxN = 4e6 + 7;
ll qpow(ll a,int n)
{
    ll bas = 1;
    while (n)
    {
        if (n & 1)
            (bas *= a) %= Q;
        (a *= a) %= Q, n >>= 1;
    }
    return bas;
}
ll inv(ll a) { return qpow(a, Q - 2); }
const ll ivG = inv(G);
int tr[MaxN];
inline void tpre(int len)
{
    for(int i = 1; i < len; ++i)
    {
        tr[i] = tr[i >> 1] >> 1;
        if (i & 1)
            tr[i] |= len >> 1;
    }
}
template<class Tp>
inline void clr(Tp *f, int len) { memset(f, 0, sizeof(Tp) * len); }
template<class Tp>
inline void cpy(Tp *f, Tp *g, int len) { memcpy(f, g, sizeof(Tp) * len); }
void NTT(unsigned *f, bool tp, int len)
{
    static ull t1[MaxN], t2[MaxN];
    t2[0] = 1;
    tpre(len);
    for (int i = 0; i < len; ++i)
        t1[i] = f[tr[i]];
    for (int i = 1; i < len; i <<= 1)
    {
        ull wn = qpow(tp ? G : ivG, (Q - 1) / (i + i));
        for (int j = 1; j < i; ++j)
            t2[j] = t2[j - 1] * wn % Q;
        for (int j = 0; j < len; j += i)
            for (int k = 0; k < i; ++k)
            {
                ull t = t1[i | j | k] * t2[k] % Q;
                t1[i | j | k] = t1[j | k] + Q - t;
                t1[j | k] += t;
            }
        if (i == (1 << 10))
            for (int j = 0; j < len; ++j)
                t1[j] %= Q;
    }
    if (tp)
        for (int i = 0; i < len; ++i)
            f[i] = t1[i] % Q;
    else
    {
        ull ivl = inv(len);
        for (int i = 0; i < len; ++i)
            f[i] = t1[i] % Q * ivl % Q;
    }
}
void vmul(unsigned *f, unsigned *g, int len)
{
    for (int i = 0; i < len; ++i)
        f[i] = 1ll * f[i] * g[i] % Q;
}
void times(unsigned *f, unsigned *g, int m1, int m2)
{
    int len = 1 << (32 - __builtin_clz(m1 + m2 - 2));
    clr(f + m1, len - m1), clr(g + m2, len - m2);
    NTT(f, 1, len), NTT(g, 1, len);
    vmul(f, g, len);
    NTT(f, 0, len), NTT(g, 0, len);
}
void poly_multiply(unsigned *f, int n, unsigned *g, int m, unsigned *h) {
    times(f, g, n, m);
    for (int i = 0; i < n+m-1; ++i) h[i] = f[i];
}

评测结果