代码

#pragma GCC optimize("-Ofast","-funroll-all-loops","-ffast-math")
#pragma GCC optimize("-fno-math-errno")
#pragma GCC optimize("-funsafe-math-optimizations")
#pragma GCC optimize("-freciprocal-math")
#pragma GCC optimize("-fno-trapping-math")
#pragma GCC optimize("-ffinite-math-only")
#pragma GCC optimize("-fno-stack-protector")
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
#include <assert.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 2345678
const int MOD=998244353;
ll qp(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%MOD;
		a=a*a%MOD; b>>=1;
	}
	return ans;
}
int getK(int n)
{int s=1; while(s<n) s<<=1; return s;}
typedef unsigned us;
typedef unsigned long long ull;
us pool[SZ*4] __attribute__ ((aligned(64))),*ptr=pool;
us *p0[SZ],*p1[SZ],*q0[SZ],*q1[SZ];
__attribute__((always_inline)) void bit_flip(us*p,int t)
{
	for(int i=0,j=0;i<t;++i)
	{
		if(i>j) swap(p[i],p[j]);
		for(int l=t>>1;(j^=l)<l;l>>=1);
	}
}
void prep(int n)
{
	static int t=1;
	for(;t<n;t<<=1)
	{
		int g=qp(3,(MOD-1)/(t*2));
		us*p,*q;
		p=p0[t]=ptr; ptr+=max(t,16); p[0]=1;
		for(int m=1;m<t;++m)
			p[m]=p[m-1]*(ull)g%us(MOD);
		bit_flip(p,t);
		q=q0[t]=ptr; ptr+=max(t,16);
		for(int i=0;i<t;++i)
			q[i]=(ull(p[i])<<32)/MOD;
		g=qp(g,MOD-2);
		p=p1[t]=ptr; ptr+=max(t,16); p[0]=1;
		for(int m=1;m<t;++m)
			p[m]=p[m-1]*(ull)g%us(MOD);
		bit_flip(p,t);
		q=q1[t]=ptr; ptr+=max(t,16);
		for(int i=0;i<t;++i)
			q[i]=(ull(p[i])<<32)/MOD;
	}
}
typedef unsigned long long ull;
__attribute__((always_inline)) us my_mul(us a,us b,us c)
{
	return b*(ull)a-((ull(a)*c)>>32)*ull(998244353);
}
void ntt(us* x,int n,bool f=true)
{
	prep(n); int t=n;
	for(int m=1;m<n;m<<=1)
	{
		t>>=1;
		us* p=p0[m];
		us* q=q0[m];
		us *xa=x,*xb=x+t;
		for(int i=0;i<m;++i,xa+=t+t,xb+=t+t)
			for(int j=0;j<t;++j)
			{
				us u=xa[j]-(xa[j]>=us(MOD+MOD))*us(MOD+MOD);
				us v=my_mul(xb[j],p[i],q[i]);
				xa[j]=u+v;
				xb[j]=u-v+us(MOD+MOD);
			}
	}
	for(int i=0;i<n;++i)
		x[i]-=(x[i]>=us(MOD+MOD))*us(MOD+MOD),
		x[i]-=(x[i]>=us(MOD))*us(MOD);
	if(f) bit_flip(x,n);
}
void intt(us* x,int n,bool f=true)
{
	prep(n); int t=1;
	if(f) bit_flip(x,n);
	for(int m=(n>>1);m;m>>=1)
	{
		us* p=p1[m];
		us* q=q1[m];
		us *xa=x,*xb=x+t;
		for(int i=0;i<m;++i,xa+=t+t,xb+=t+t)
			for(int j=0;j<t;++j)
			{
				us u=xa[j],v=xb[j];
				xa[j]=u+v-(u+v>=us(MOD+MOD))*us(MOD+MOD);
				xb[j]=my_mul(u-v+us(MOD+MOD),p[i],q[i]);
			}
		t<<=1;
	}
	us rn=qp(n,MOD-2);
	for(int i=0;i<n;++i)
		x[i]=x[i]*(ull)rn%MOD;
}
//modint wrapper
struct mi
{
us w;
mi() {}
mi(us u) {w=u;}
mi(int u) {u%=MOD; w=u+((u<0)?MOD:0);}
explicit operator us() {return w;}
explicit operator int() {return w;}
};
mi operator + (const mi& a,const mi& b)
{return mi{a.w+b.w-((a.w+b.w>=MOD)?(MOD):0)};}
mi operator - (const mi& a,const mi& b)
{return mi{a.w-b.w+((a.w<b.w)?(MOD):0)};}
mi operator * (const mi& a,const mi& b)
{return mi{us((ull)a.w*b.w%MOD)};}
mi operator / (const mi& a,const mi& b)
{return mi{us((ull)a.w*qp(b.w,MOD-2)%MOD)};}
mi inv(const mi& a)
{return mi{us(qp(a.w,MOD-2))};}
//what could possibly go wrong?
void ntt(mi* x,int n,bool f=true) {ntt((us*)x,n,f);}
void intt(mi* x,int n,bool f=true) {intt((us*)x,n,f);}

mi x[2345678] __attribute__ ((aligned(64)));
mi y[2345678] __attribute__ ((aligned(64)));

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c)
{
	int K=getK(n+m+1); prep(K);
	for(int i=0;i<=n;++i) x[i]=a[i];
	for(int i=n+1;i<K;++i) x[i]=0;
	for(int i=0;i<=m;++i) y[i]=b[i];
	for(int i=m+1;i<K;++i) y[i]=0;
	ntt(x,K,0); ntt(y,K,0);
	for(int i=0;i<K;i++) x[i]=x[i]*y[i];
	intt(x,K,0); for(int i=0;i<=n+m;i++) c[i]=(us)x[i];
}

评测结果