代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define io cin.tie(0)->sync_with_stdio(false),cin.tie(0)->sync_with_stdio(false);
const int N=4e6+5,mod=998244353,g=3,gi=(mod+1)/3;
int a[N],b[N],r[N];
int up2[N],lg2[N];
int w[2][N],w0,w1;
int qpow(int a,int b){int r=1;for(;b;b>>=1,a=a*a%mod)if(b&1)r=r*a%mod;return r;}
inline void initn(int n){for(int i=1,j=2,k=0;i<=n;i++){up2[i]=j,lg2[i]=k;if(i==j)j<<=1,k++;}}
inline void init(int nx)
{
	static int n,m;if(n==up2[nx])return;
	n=up2[nx],m=lg2[n];
	for(int i=0;i<n;i++)r[i]=(r[i>>1]>>1)|((i&1)<<m);
	w[0][n>>1]=w[1][n>>1]=1,w0=qpow(g,(mod-1)/n),w1=qpow(gi,(mod-1)/n);
	for(int i=(n>>1)+1;i<n;i++)w[0][i]=w[0][i-1]*w0%mod,w[1][i]=w[1][i-1]*w1%mod;
	for(int i=(n>>1)-1;i>=1;i--)w[0][i]=w[0][i<<1],w[1][i]=w[1][i<<1];
}
inline int in(int *a)
{
	string s;cin>>s;int n=s.size();
	for(int i=0;i<n;i++)a[i]=s[n-i-1]-'0';
	return n;
}
inline void out(int *a,int n){for(int i=n-1;~i;i--)cout<<a[i];}
inline void ntt(int *a,int n,int op=0)
{
	for(int i=0;i<n;i++)if(i<r[i])swap(a[i],a[r[i]]);
	for(int m=1,r,i;m<n;m=r)for(r=m<<1,i=0;i<n;i+=r)for(int k=0,x=i,y=i+m,z=m,t;k<m;k++,x++,y++,z++)
		t=w[!op][z]*a[y]%mod,a[y]=(a[x]-t+mod)%mod,a[x]=(a[x]+t)%mod;
	if(op)for(int i=0,ni=qpow(n,mod-2);i<n;i++)a[i]=a[i]*ni%mod;
}
void mul(int *a,int *b,int len)
{
	int n=up2[len];init(n);
	ntt(a,n);ntt(b,n);
	for(int i=0;i<n;i++)a[i]=a[i]*b[i]%mod;
	ntt(a,n,-1);
}
signed main()
{
	io;
	int n=in(a);
	int m=in(b);
	int len=n+m;
	initn(len<<1);
	mul(a,b,len);
	for(int i=0;i<len;i++)a[i+1]+=a[i]/10,a[i]%=10;
	if(!a[len-1])len--;
	out(a,len);
	return 0;
	
}

评测结果