#include<bits/stdc++.h>
#define I inline
#define RI register int
#define rep(i,a,b) for(RI i=a;i<=b;++i)
#define dow(i,a,b) for(RI i=a;i>=b;--i)
using namespace std;
const int N=8000005;
const double PI=acos(-1.0);
struct comp{
double x,y;
comp(double xx=0,double yy=0){ x=xx,y=yy; }
} a[N],b[N];
comp operator + (comp a,comp b){ return comp(a.x+b.x,a.y+b.y); }
comp operator - (comp a,comp b){ return comp(a.x-b.x,a.y-b.y); }
comp operator * (comp a,comp b){ return comp(a.x*b.x-a.y*b.y,a.x*b.y+b.x*a.y); }
int n,m,lim=1,cnt,lenc,lens,r[N];
char c[N],s[N],ans[N];
I void FFT(comp a[],int len,int op){
rep(i,1,lim) if(r[i]>i) swap(a[r[i]],a[i]);
for(RI l=1;l<len;l<<=1){
comp now=comp(cos(PI/l),op*sin(PI/l));
for(RI j=0;j<len;j+=(l<<1)){
comp pw=comp(1,0);
rep(k,0,l-1){
comp x=a[j+k],y=pw*a[j+k+l];
a[j+k]=x+y,a[j+k+l]=x-y;pw=pw*now;
}
}
}
}
int main(){
freopen("P1919_1.in","r",stdin);
scanf("%s%s",c+1,s+1);lenc=strlen(c+1),lens=strlen(s+1);lenc--,lens--;
while(lim<=(lenc+lens)) lim<<=1,cnt++;
rep(i,1,N-1) r[i]=((r[i>>1]>>1)|((i&1)*(lim>>1)));
dow(i,lenc,1) a[lenc-i+1].x=c[i]-'0';a[0].x=c[lenc+1]-'0';FFT(a,lim,1);
dow(i,lens,1) b[lens-i+1].x=s[i]-'0';b[0].x=s[lens+1]-'0';FFT(b,lim,1);
rep(i,0,lim) a[i]=a[i]*b[i];FFT(a,lim,-1);
// rep(i,0,lim) printf("%d %lf\n",(int)(a[i].x/lim+0.5),a[i].y);
rep(i,0,lim) ans[i]+=(int)(a[i].x/lim+0.5),ans[i+1]+=ans[i]/10,ans[i]%=10;
bool flag=0;
dow(i,lim,0){ if(!flag&&ans[i]) flag=1;if(flag) printf("%d",ans[i]);}
return 0;
}
个人认为 FFT 那部分没问题,不知道哪里 WA 掉了。