代码

#include<bits/stdc++.h>
using namespace std;
using cp=complex<double>;
#define io cin.tie(0)->sync_with_stdio(false),cin.tie(0)->sync_with_stdio(false);
const double pi=acos(-1.0);
const int N=4e6+5,mod=998244353,g=3,gi=(mod+1)/3;
int a[N],b[N];
int up2[N],lg2[N],r[N];
cp 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=cp(cos(2.0*pi/n),sin(2.0*pi/n)),w1=conj(w0);
	for(int i=(n>>1)+1;i<n;i++)w[0][i]=w[0][i-1]*w0,w[1][i]=w[1][i-1]*w1;
	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--)putchar(a[i]+'0');}
inline void fft(cp *a,int n,int op=0)
{
	cp t;
	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;k<m;k++,x++,y++,z++)
		t=w[!op][z]*a[y],a[y]=a[x]-t,a[x]+=t;
	if(op)for(int i=0;i<n;i++)a[i]=a[i]/(double)n;
}
void mul(int *a,int *b,int len)
{
	int n=up2[len];init(n);
	static cp A[N];
	for(int i=0;i<n;i++)A[i]=cp(a[i],b[i]);
	fft(A,n);
	for(int i=0;i<n;i++)A[i]*=A[i];
	fft(A,n,-1);
	for(int i=0;i<n;i++)a[i]=(imag(A[i]))*0.5+0.5;
}
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;
	
}

评测结果