代码

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define REP(i,n) for(int i=0;i<(n);++i)
using namespace std;
typedef vector<int> poly;
typedef long long ll;

namespace Poly{
	//const int mod=65537,g=3;
	const int mod=998244353,g=3;
	const int N=1<<23;
	inline int power(int x,int p){
		int res=1;
		for(;p;x=1ll*x*x%mod,p>>=1)
			if(p&1)res=1ll*res*x%mod;
		return res;
	}
	inline int fix(int x){return x>=mod?x-mod:x;}
	void dft(poly &A,int n){
		A.resize(1<<n); int *a=&(A.front());
		static int W[N],*last=W,*h[32],mx=0,R[N];
		for (;mx<n;++mx){
			h[mx]=last;
			ll w=1,wn=power(g,(mod-1)>>(mx+1));
			REP(i,1<<mx)*last++=w,w=1ll*w*wn%mod;
		}
		REP(i,1<<mx){
			R[i]=i&1?R[i^1]|1<<(n-1):R[i>>1]>>1;
			if(i<R[i])swap(a[i],a[R[i]]);
		}
		int *l,*r,*w,x,y;
		for(int k=0,d=1;k<n;k++,d<<=1)
			for (int i=0;i<(1<<n);i+=d<<1){
				l=a+i,r=a+i+d,w=h[k];
				for (int j=0;j<d;++j,++l,++r){
					x=*l,y=1ll*(*r)*(*w++)%mod;
					*l=fix(x+y),*r=fix(x-y+mod);
				}
			}
	}
	void idft(poly &a,int n){
		a.resize(1<<n);reverse(a.begin()+1,a.end());
		dft(a,n);ll inv=power(1<<n,mod-2);
		REP(i,1<<n)a[i]=1ll*a[i]*inv%mod;
	}
	void FIX(poly &a){
		while(a.size()&&!a.back())a.pop_back();
	}
	poly mul(poly a,poly b){
		int n=0,aim=a.size()+b.size();
		while((1<<n)<aim)++n;dft(a,n),dft(b,n);
		REP(i,1<<n)a[i]=1ll*a[i]*b[i]%mod;
		idft(a,n),a.resize(aim),FIX(a);
		return a;
	}
}
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c){
n++,m++;
poly A(n,0),B(m,0);
REP(i,n) A[i]=a[i];
REP(i,m) B[i]=b[i];
poly C=Poly::mul(A,B);
REP(i,n+m-1) c[i]=C[i];
}

评测结果