代码

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=1e6,maxf=1<<21;
const int mod=998244353;
namespace usual{
	int add(int ta,int tb){ return ta+tb>=mod?ta+tb-mod:ta+tb; }
	int sub(int ta,int tb){ return ta<tb?ta-tb+mod:ta-tb; }
	int ksm(ll ta,int tp){
		int s=1;
		for(;tp;ta=ta*ta%mod,tp>>=1) if(tp&1) s=ta*s%mod;
		return s;
	}
}
using namespace usual;
namespace poly{
	int pa[maxf+5],pb[maxf+5];
	int rev[maxf+5],g[maxf+5],invg[maxf+5];
	void Cpy(int *A,int *B,int len){
		for(int i=0;i<len;i++) A[i]=B[i];
	}
	void Cl(int *A,int len){
		memset(A,0,len*4);
	}
	void make_tt(int *T,int len,int da){
		int tmp=ksm(da,(mod-1)/len); T[len>>1]=1;
		for(int i=(len>>1)+1;i<len;i++) T[i]=(0ll+T[i-1])*tmp%mod;
		for(int i=(len>>1)-1;i;i--) T[i]=T[i<<1];
	}
	void pre_poly(int len){
		make_tt(g,len,3); make_tt(invg,len,332748118);
	}
	void make_rev(int len){
		for(int i=1;i<len;i++) rev[i]=(rev[i>>1]>>1)|(i&1?len>>1:0);
	}
	void NTT(int *T,int len,bool ok){
		static unsigned long long s[maxf+5];
		int *tt=ok?g:invg,ny;
		for(int i=0;i<len;i++) s[rev[i]]=T[i];
		for(int i=1;i<len;i<<=1)
			for(int j=0;j<len;j+=i<<1)
				for(int l=0;l<i;l++){
					ny=s[i+j+l]*tt[i+l]%mod;
					s[i+j+l]=s[j+l]+mod-ny; s[j+l]+=ny;
				}
		for(int i=0;i<len;i++) T[i]=s[i]%mod;
	}
	void Mult(int *A,int *B,int *C,int len){
		Cpy(pa,A,len); Cpy(pb,B,len);
		make_rev(len);
		NTT(pa,len,1); NTT(pb,len,1);
		for(int i=0;i<len;i++) pa[i]=(0ll+pa[i])*pb[i]%mod;
		NTT(pa,len,0);
		int invn=ksm(len,mod-2);
		for(int i=0;i<len;i++) C[i]=(0ll+pa[i])*invn%mod;
	}
}
using namespace poly;
int n,m;
int F[maxf+5],G[maxf+5];
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c){
	for(int i=0;i<=n;i++) F[i]=a[i];
	for(int i=0;i<=m;i++) G[i]=b[i];
	n++; m++;
	int len=1;
	while(len<m+n) len<<=1;
	pre_poly(len);
	Mult(F,G,F,len);
	for(int i=0;i<n+m-1;i++) c[i]=F[i];
}

评测结果