代码

#include<bits/stdc++.h>
#define mod 998244353
using namespace std;
int powdv(int x,int y=mod-2){
	int ans=1;
	while(y){
		if(y&1)ans=1ll*ans*x%mod;
		y>>=1,x=1ll*x*x%mod;
	}
	return ans;
}
#define poly vector<int>
#define N 21
void output(poly a){
	for(auto cu:a)printf("%d ",cu);
	printf("\n");
}
poly mul(int k,poly a){
	int sz=a.size();
	poly b;
	for(int i=0;i<sz;++i)b.emplace_back(1ll*k*a[i]%mod);
	return b;
}
poly plu(poly a,poly b){
	poly c;
	int s1=a.size(),s2=b.size();
	c.resize(max(s1,s2));
	for(int i=0;i<s1;++i)c[i]=(c[i]+a[i])%mod;
	for(int i=0;i<s2;++i)c[i]=(c[i]+b[i])%mod;
	return c;
}
poly mns(poly a,poly b){
	poly c;
	int s1=a.size(),s2=b.size();
	c.resize(max(s1,s2));
	for(int i=0;i<s1;++i)c[i]=(c[i]+a[i])%mod;
	for(int i=0;i<s2;++i)c[i]=(c[i]-b[i]+mod)%mod;
	return c;
}
int a[1<<N],b[1<<N],ap[1<<N],bp[1<<N];
int rev[1<<N];
void getrev(int l){
	rev[0]=0;
	for(int i=1;i<=l;++i){
		for(int j=0;j<(1<<(i-1));++j){
			rev[j^(1<<(i-1))]=rev[j]^(1<<(l-i));
		}
	}
}
int cj[1<<N];
void ntt(int l,int *c,int *d,int cd){
	for(int i=0;i<(1<<l);++i)d[i]=c[rev[i]];
	for(int i=1;i<(1<<l);i<<=1){
		int o1=powdv(3,(mod-1)/i/2);cj[0]=1;
		if(cd==-1)o1=powdv(o1);
		for(int k=1;k<i;++k)cj[k]=1ll*cj[k-1]*o1%mod;
		for(int j=0;j<(1<<l);j+=i+i){
			for(int k=0;k<i;++k){
				int A=d[j+k],B=1ll*cj[k]*d[j+k+i]%mod;
				d[j+k]=A+(B>=mod-A?B-mod:B);d[j+k+i]=A+(B>A?mod-B:-B);
			}
		}
	}
	if(cd==-1){
		int ny=powdv(1<<l);
		for(int i=0;i<(1<<l);++i)d[i]=1ll*d[i]*ny%mod;
	}
}
void poly_multiply(unsigned *aa,int n,unsigned *bb,int m,unsigned *cc){
	int k=21;
	getrev(k);
	for(int i=0;i<=n;++i)a[i]=aa[i],b[i]=bb[i];
	ntt(k,a,ap,1);ntt(k,b,bp,1);
	for(int i=0;i<(1<<k);++i)bp[i]=1ll*bp[i]*ap[i]%mod;
	ntt(k,bp,b,-1);
	for(int i=0;i<=n+m;++i)cc[i]=b[i];
}

评测结果