代码

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define fo(i,a,b)for(int i=a,_e=b;i<=_e;i++)
#define fd(i,a,b)for(int i=b,_e=a;i>=_e;i--)
#define ll long long
#define flush()(fwrite(out,1,os-out,stdout),os=out)
#define put(x)(*os++=x,os==ot?flush():0)
#define gc()(it==is?it=(is=in)+fread(in,1,P,stdin),(it==is?EOF:*is++):*is++)
using namespace std;
const int N=1e6+5,M=(1<<21)+1,mo=998244353,P=(1<<21)+1;
char in[P],*is=in,*it=in,out[P],*os=out,*ot=out+P-1,o[20],c;
int n,m,Q;
int a[M],b[M],w[M],h[M],ny;
ll A;
int ksm(int x,int y){
	int t=1;
	for(;y;y>>=1,x=(ll)x*x%mo)if(y&1)t=(ll)t*x%mo;
	return t;
}
void dft(int *a){
	fo(i,1,Q-1)if(i<h[i])swap(a[i],a[h[i]]);
	for(int i=2,j,k,m,g=Q>>1;m=i>>1,i<=Q;i<<=1,g>>=1)for(j=0;j<Q;j+=i){
		int *p=w,*l=a+j,*r=a+j+m;
		for(k=0;k<m;p+=g,l++,r++,k++)A=(ll)*p* *r,*r=(-A+*l)%mo,*l=(A+*l)%mo;
	}
}
int main(){
	for(;(c=gc())<='9'&&c>='0';)a[++n]=c-48;
	for(;(c=gc())<'0'||c>'9';);
	for(;b[++m]=c-48,(c=gc())<='9'&&c>='0';);
	fo(i,0,n>>1)swap(a[i],a[n-i]);
	fo(i,0,m>>1)swap(b[i],b[m-i]);
	for(Q=1;Q<=n+m;Q<<=1);
	w[0]=1;w[1]=ksm(3,(mo-1)/Q);ny=ksm(Q,mo-2);
	fo(i,2,Q)w[i]=(ll)w[i-1]*w[1]%mo;
	fo(i,1,Q)h[i]=(h[i>>1]>>1)|(i&1?Q>>1:0);
	dft(a);dft(b);
	fo(i,0,Q)a[i]=(ll)a[i]*b[i]%mo;
	fo(i,1,Q>>1)swap(a[i],a[Q-i]);
	dft(a);
	ll y=0;
	n+=m-2;
	fo(i,0,n){
		a[i]=(ll)(a[i]+mo)*ny%mo+y;
		y=a[i]/10;
		a[i]=a[i]%10;
	}
	if(y)a[++n]=y;
	fd(i,0,n)put(a[i]+48);
	flush();
}

评测结果