代码

#include<bits/stdc++.h>
#define M_PI		3.14159265358979323846
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define de(x) cerr << #x << " = " << x << endl;
#define rep(i, a, b) for(int i=(a); i<=(b); i++)
#define per(i, a, b) for(int i=int(b)-1; i>=(a); i--)
const int _p=998244353;
ll Pow(ll x,ll k) { ll ans=1; for (;k;k>>=1,x=x*x%_p) if (k&1) (ans*=x)%=_p; return ans; } 

template <class V>
struct FT{
	static const int N=1<<21; V w[2][N*2+5],rev[N*2+5],tmp;
	void Init() {
		V w0=Pow(3,(_p-1)/N),m; w[0][0]=w[1][0]=1;
		rep(i,1,N-1) w[0][i]=w[1][N-i]=(ll)w[0][i-1]*w0%_p;
		for (m=0; (1<<m)!=N; m++);
		rep(i,1,N-1) rev[i]=(rev[i>>1]>>1)|(i&1)<<m-1;
	}
	void FFT(V A[],int op){
		rep(i,0,N-1) if (i<rev[i]) swap(A[i],A[rev[i]]);
		for (int i=1; i<N; i<<=1)
			for (int j=0,t=N/(i<<1); j<N; j+=i<<1)
				for (int k=j,l=0; k<j+i; k++,l+=t) {
					V x=A[k],y=(ll)w[op][l]*A[k+i]%_p;
					A[k]=(x+y)%_p,A[k+i]=(x-y+_p)%_p;
				}
		if (op) { tmp=Pow(N,_p-2); rep(i,0,N-1) A[i]=1ll*A[i]*tmp%_p; }
	}
	void Solve(V A[],V B[],V C[],int op=0) {
		if (op) reverse(B,B+N); FFT(A,0),FFT(B,0); 
		rep(i,0,N-1) C[i]=(ll)A[i]*B[i]%_p; FFT(C,1); if (op) reverse(C,C+N);
	}
};
const int N=1<<21;//2097152
int a[N],b[N],c[N];
void poly_multiply(unsigned *ax, int n, unsigned *bx, int m, unsigned *cx)
{
	n++,m++;
	FT<int> F;
	for(int i=0;i<n;++i){
		a[i]=ax[i];
	}
	for(int i=0;i<m;++i){
		b[i]=bx[i];
	}
	F.Init();
	F.Solve(a,b,c);
	for(int i=0;i<n+m+1;++i)
	cx[i]=c[i];
}

评测结果