代码

/*+lmake
 * DEFINE += MDEBUG
 * STD = c++11
 */
#include <algorithm>
using namespace std;
#ifdef MDEBUG
#define debug(args...)                                                                             \
    {                                                                                              \
        dbg, args;                                                                                 \
        cerr << endl;                                                                              \
    }
#define massert(x) assert(x)
#else
#define debug(args...) // Just strip off all debug tokens
#define massert(x)
#endif
typedef long long LL;
typedef unsigned long long ULL;

#define MAXN 4000000
int rev[MAXN + 10];
const LL kcz=998244353;
LL qpow(LL x,LL n=kcz-2)
{
	LL ans=1;
	while(n) {
		if (n%2==1) ans=ans*x%kcz;
		x=x*x%kcz;
		n>>=1;
	}
	return ans;
}
void fft(int n, LL *a, int flag)
{
    rev[0] = 0;
    for (int i = 1; i < n; ++i)
        rev[i] = rev[i / 2] / 2 + (i % 2) * (n / 2);
    for (int i = 0; i < n; ++i)
        if (i < rev[i])
            swap(a[i], a[rev[i]]);
    for (int i = 1; i < n; i *= 2) {
        int nn = i * 2;
        LL wn = qpow(3,kcz-1+flag*(kcz-1)/nn);
        for (int j = 0; j < n; j += nn) {
            LL *a1 = a + j, *a2 = a1 + i;
            LL w = 1;
            for (int k = 0; k < i; ++k) {
                LL x = a1[k], y = w * a2[k]%kcz;
                a1[k] = (x + y)%kcz;
                a2[k] = (x - y)%kcz;
                w = w * wn%kcz;
            }
        }
    }
}
LL a[MAXN+10],b[MAXN+10];
void poly_multiply(unsigned *aa, int n, unsigned *bb, int m, unsigned *c)
{
	for(int i=0; i<=n; ++i) a[i]=aa[i];
	for(int i=0; i<=m; ++i) b[i]=bb[i];
    LL l = 1;
    for (; l <= n + m; l *= 2)
        ;
    fft(l, a, 1);
    fft(l, b, 1);
    for (int i = 0; i <= l; ++i) {
        a[i] = a[i] * b[i] %kcz;
    }
    fft(l, a, -1);
	LL t=qpow(l);
	for(int i=0; i<=n+m; ++i) {
		c[i]=(a[i]*t%kcz+kcz)%kcz;
	}
}

评测结果