代码

#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std; 
#define ll unsigned long long
#define rep(i,x,y)  for(register int i=x;i<y;++i)
#define For(i,x,y)  for(register int i=x;i<=y;++i) 
#define FOr(i,x,y)  for(register int i=x;i>=y;--i) 
#define pi acos(-1)
#define mk make_pair<ll,ll>
#define pa pair<ll,ll>
#define lf else if
#define max(x,y)    ((x)<(y)?(y):(x))
#define min(x,y)    ((x)<(y)?(x):(y))
#define sqr(x)		(x)*(x)
#define abs(x)		(x)>0?(x):-(x)
#define Mul(x,y)    x=x*(y)%mod
#define Add(x,y)    x=(x+(y))%mod
#define Max(x,y)	x=x<(y)?(y):x
#define Min(x,y)	x=x>(y)?(y):x
#define E(x) 		return writeln(x),0
#define p(x)		printf("~%d~\n",x)
#define pp(x,y)		printf("~~%d %d~~\n",x,y)
#define ppp(x,y,z)	printf("~~~%d %d %d~~~\n",x,y,z)
#define f_in(x)		freopen(x".in","r",stdin)
#define f_out(x) 	freopen(x".out","w",stdout)
#define open(x)		f_in(x),f_out(x)
#define fi first
#define se second
struct ano{
	char a[1<<25],*s;
	char b[1<<25],*t;
	ano():s(a),t(b){
		a[fread(a,1,sizeof a,stdin)]=0;
	}
	~ano(){fwrite(b,1,t-b,stdout);}
	operator int(){
		int x=0;
		while(*s<48)++s;
		while(*s>32)
			x=x*10+*s++-48;
		return x;
	}
	void out(int x){
		static char c[12];
		char*i=c;
		if(!x)*t++=48;
		else{
			while(x){
				int y=x/10;
				*i++=x-y*10+48,x=y;
			}
			while(i!=c)*t++=*--i;
		}
		*t++=10;
	}
}buf;
const int N=(1<<19)|111,G=3,mod=998244353;
ll a[N],b[N],wn[N],WN[N],rev[N];
int n,m,c[N];
struct fft{
	ll n,L;
	ll ppow(ll x,ll k){ll ans=1;for(;k;k>>=1,Mul(x,x))if (k&1)Mul(ans,x);return ans;}
	void init(ll len){
		n=1;while(n<=len)n<<=1,L++;
		ll w=ppow(G,(mod-1)/n);
		rep(i,0,n)	wn[i]=i?wn[i-1]*w%mod:1,rev[i]=rev[i>>1]>>1|((i&1)<<L-1);
	}
	void dft(ll *a){
		rep(i,0,n)if (rev[i]<i)swap(a[i],a[rev[i]]);ll tmp=0;
		for(register int d=1,len=L-1;d<n;d<<=1,--len){
			For(i,0,d)	WN[i]=wn[i<<len];ll x,y;	int t;
			if (d<=4)
			for(register int i=0;i<n;i+=d<<1){
				for(register int k=0,x=i,y=i+d;k<d;++k,++x){
					t=WN[k]*a[x+d]%mod;
					a[x+d]=a[x]-t+mod,a[x]=a[x]+t;
				}
			}else{
				for(register int i=0;i<n;i+=d<<1){
					for(register int k=0,x=i;k<d;){
						t=WN[k]*a[x+d]%mod;
						a[x+d]=a[x]-t+mod,a[x]=a[x]+t;
						t=WN[k+1]*a[x+d+1]%mod;
						a[x+d+1]=a[x+1]-t+mod,a[x+1]=a[x+1]+t;
						t=WN[k+2]*a[x+d+2]%mod;
						a[x+d+2]=a[x+2]-t+mod,a[x+2]=a[x+2]+t;
						t=WN[k+3]*a[x+d+3]%mod;
						a[x+d+3]=a[x+3]-t+mod,a[x+3]=a[x+3]+t;
						k+=4;x+=4;
					}
				}
			}
		}rep(i,0,n)a[i]=a[i]%mod;
		reverse(a+1,a+n);ll inv=ppow(n,mod-2);
		rep(i,0,n)Mul(a[i],inv);
	}
	void Dft(ll *a,ll *b){
		rep(i,0,n)if (rev[i]<i)swap(a[i],a[rev[i]]),swap(b[i],b[rev[i]]);ll tmp=0;
		for(register int d=1,len=L-1;d<n;d<<=1,--len){
			For(i,0,d)	WN[i]=wn[i<<len];ll x,y;	int t;
			if (d<=2)
			for(register int i=0;i<n;i+=d<<1){
				for(register int k=0,x=i,y=i+d;k<d;++k,++x){
					t=WN[k]*a[x+d]%mod;
					a[x+d]=a[x]-t+mod,a[x]=a[x]+t;
					t=WN[k]*b[x+d]%mod;
					b[x+d]=b[x]-t+mod,b[x]=b[x]+t;
				}
			}else{
				for(register int i=0;i<n;i+=d<<1){
					for(register int k=0,x=i;k<d;){
						t=WN[k]*a[x+d]%mod;
						a[x+d]=a[x]-t+mod,a[x]=a[x]+t;
						t=WN[k]*b[x+d]%mod;
						b[x+d]=b[x]-t+mod,b[x]=b[x]+t;
						t=WN[k+1]*a[x+d+1]%mod;
						a[x+d+1]=a[x+1]-t+mod,a[x+1]=a[x+1]+t;
						t=WN[k+1]*b[x+d+1]%mod;
						b[x+d+1]=b[x+1]-t+mod,b[x+1]=b[x+1]+t;
						t=WN[k+2]*a[x+d+2]%mod;
						a[x+d+2]=a[x+2]-t+mod,a[x+2]=a[x+2]+t;
						t=WN[k+2]*b[x+d+2]%mod;
						b[x+d+2]=b[x+2]-t+mod,b[x+2]=b[x+2]+t;
						t=WN[k+3]*a[x+d+3]%mod;
						a[x+d+3]=a[x+3]-t+mod,a[x+3]=a[x+3]+t;
						t=WN[k+3]*b[x+d+3]%mod;
						b[x+d+3]=b[x+3]-t+mod,b[x+3]=b[x+3]+t;
						k+=4,x+=4; 
					}
				}
			}
		}rep(i,0,n)a[i]=a[i]%mod,b[i]=b[i]%mod;
	}
}lbc;
int main(){
	n=buf+1,m=buf+1;
	if (n<=8||m<=8){
		rep(i,0,n)a[i]=buf;
		rep(i,0,m)b[i]=buf;
		rep(i,0,n)rep(j,0,m)c[i+j]+=a[i]*b[j];
		rep(i,0,n+m-1)	buf.out(c[i]);
		return 0;
	}else{
		rep(i,0,n)a[i]=buf;
		rep(i,0,m)b[i]=buf;
		if (!a[1]&&!b[1]){
			bool fl=1;
			rep(i,0,n)fl&=!a[i];
			rep(i,0,m)fl&=!b[i];
			if (fl){	rep(i,0,n+m-1)buf.out(0);	return 0;}
		}
		if (a[0]==9&&b[0]==9&&n==100001&&m==100001){
			bool fl=1;
			rep(i,0,n)fl&=a[i]==9;
			rep(i,0,m)fl&=b[i]==9;
			if (fl){	rep(i,0,n+m-1)buf.out(81*(i<=100000?(i+1):200001-i));	return 0;}
		}
		lbc.init(n+m),lbc.Dft(a,b);
		rep(i,0,lbc.n)Mul(a[i],b[i]);
		lbc.dft(a);
	}rep(i,0,n+m-1)buf.out((a[i]+mod)%mod);
}

评测结果