代码

#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 unsigned long long ll;

inline int read(){
	char ch=getchar();int x=0,op=0;
	while(!isdigit(ch))op|=(ch=='-'),ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return op?-x:x;
}

const int mod=998244353;
namespace Poly{
	const int N=(1<<21)+5,g=3;
	inline int power(int x,int p){
		int res=1;
		for(;p;p>>=1,x=(ll)x*x%mod)
			if(p&1)res=(ll)res*x%mod;
		return res;
	}
	void dft(poly &A,int n){
		static ll W[N<<1],*H[30],*las=W,mx=0;
		for(;mx<n;mx++){
			H[mx]=las;ll w=1,wn=power(g,(mod-1)>>(mx+1));
			REP(i,1<<mx)*las++=w,w=w*wn%mod;
		}
		static ll a[N];A.resize(1<<n);
		for(int i=0,j=0;i<(1<<n);++i){
			a[i]=A[j];
			for(int k=1<<(n-1);(j^=k)<k;k>>=1);
		}
		for(int k=0,d=1;k<n;k++,d<<=1)
			for(int i=0;i<(1<<n);i+=d<<1){
				ll *l=a+i,*r=a+i+d,*w=H[k],t;
				for(int j=0;j<d;++j,++l,++r){
					t=(*w++)*(*r)%mod;
					*r=*l+mod-t,*l+=t;
				}
			}
		REP(i,1<<n)A[i]=a[i]%mod;
	}
	void idft(poly &a,int n){
		a.resize(1<<n);
		reverse(a.begin()+1,a.end());
		dft(a,n);
		int inv=power(1<<n,mod-2);
		REP(i,1<<n)a[i]=(ll)a[i]*inv%mod;
	}
	poly mul(poly a,poly b){
		int aim=(a.size()+b.size()),n=1;
		while((1<<n)<=aim)n++;
		dft(a,n),dft(b,n);
		REP(i,1<<n)a[i]=(ll)a[i]*b[i]%mod;
		return idft(a,n),a.resize(aim),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];
}

评测结果