代码

#pragma GCC target("avx512f")
#include <vector>
#include <algorithm>

using namespace std;

unsigned brev[2097160];

constexpr unsigned long long qpow(unsigned long long x, unsigned long long y)
{
    unsigned long long p = x, ans = 1;
    do
    {
        if(y & 1) ans = ans * p % 998244353;
        p = p * p % 998244353;
    } while (y >>= 1);
    return ans;
}

void FFT(unsigned n, unsigned long long *F, bool vv)
{
    for(unsigned i=0;i<n;i++)
    {
        swap(F[i], F[brev[i]]);
    }
    unsigned long long gr = vv ? 3 : 332748118;
    for(unsigned i=1;i<n;i<<=1)
    {
        unsigned long long cp = qpow(gr, 998244352 / (i * 2));
        for(unsigned j=0;j<n;j+=i*2)
        {
            unsigned long long v = 1;
            for(unsigned k=0;k<i;k++)
            {
                const unsigned long long x = F[j + k], y = v * F[j + k + i] % 998244353;
                F[j + k] = (x + y) % 998244353;
                F[j + k + i] = (x - y + 998244353) % 998244353;
                v = v * cp % 998244353;
            }
        }
    }
}
void poly_multiply(unsigned *F, int n, unsigned *G, int m, unsigned *c)
{
    unsigned pl = __lg(n + m + 2), p = (1 << pl) == n + m + 2 ? 1 << pl : (1 << ++pl);
    for(unsigned i=0;i<p;i++)
    {
        brev[i] = (brev[i >> 1] >> 1) | ((i & 1) << (pl - 1));
    }
    for(unsigned i=0;i<p;i++)
    {
        if(i > brev[i]) brev[i] = i;
    }
    FFT(p, F, 1);
    FFT(p, G, 1);
    for(unsigned i=0;i<p;i++)
    {
        c[i] = F[i] * G[i] % 998244353;
    }
    FFT(p, c, 0);
    unsigned long long pr = qpow(p, 998244351);
    for(unsigned i=0;i<=n+m;i++)
    {
        c[i] = c[i] * pr % 998244353;
    }
}