#include<bits/stdc++.h>
#define n 131072
using namespace std;
struct apple
{
double a,b;
apple(double a=0,double b=0):a(a),b(b){}
void operator+=(apple other)
{
a+=other.a;
b+=other.b;
}
void operator-=(apple other)
{
a-=other.a;
b-=other.b;
}
void operator*=(apple other)
{
double aa=a*other.a-b*other.b,bb=a*other.b+b*other.a;
a=aa,b=bb;
}
}ans[n],ans2[n],ans3[n],d1[n],d2[n],d[n],dd[n],f1[n],f2[n],cj[n+1];
char s1[n],s2[n];
int ff[n];
double pi=2*acos(-1);
void fft(apple d[],int nn,int cz,int cs)
{
apple cs2;
if(nn==1)
{
ans[cs]=d[cs];
return;
}
int bb=nn>>1;
for(int i=0;i<bb;i++)dd[cs+i]=d[cs+(i<<1)];
for(int i=0;i<bb;i++)dd[cs+bb+i]=d[cs+(i<<1|1)];
for(int i=cs;i<cs+nn;i++)d[i]=dd[i];
fft(d,bb,cz,cs);
fft(d,bb,cz,cs+bb);
for(int i=0;i<bb;i++)
{
cs2=cj[n/nn*i];
apple ccs=cs2;
if(cz==-1)
{
cs2.a=ccs.a/(ccs.a*ccs.a+ccs.b*ccs.b);
cs2.b=-ccs.b/(ccs.a*ccs.a+ccs.b*ccs.b);
}
cs2*=ans[cs+bb+i];
ans3[cs+i]=ans[cs+i];
ans3[cs+i]+=cs2;
}
for(int i=bb;i<nn;i++)
{
cs2=cj[n/nn*i];
apple ccs=cs2;
if(cz==-1)
{
cs2.a=ccs.a/(ccs.a*ccs.a+ccs.b*ccs.b);
cs2.b=-ccs.b/(ccs.a*ccs.a+ccs.b*ccs.b);
}
cs2*=ans[cs+i];
ans3[cs+i]=ans[cs+i-bb];
ans3[cs+i]+=cs2;
}
for(int i=cs;i<cs+nn;i++)ans[i]=ans3[i];
}
int main()
{
cj[0]=apple(1,0),cj[1]=apple(cos(pi/n),sin(pi/n));
for(int i=2;i<=n;i++)cj[i]=cj[i-1],cj[i]*=cj[1];
int pppp;
cin>>pppp;
scanf("%s%s",s1,s2);
int l1=strlen(s1),l2=strlen(s2);
for(int i=0;i<l1;i++)f1[l1-i-1].a=s1[i]-'0';
for(int i=0;i<l2;i++)f2[l2-i-1].a=s2[i]-'0';
fft(f1,n,1,0);
for(int i=0;i<n;i++)d1[i]=ans[i];
fft(f2,n,1,0);
for(int i=0;i<n;i++)d2[i]=ans[i];
for(int i=0;i<n;i++)d1[i]*=d2[i],d[i]=d1[i];
fft(d,n,-1,0);
for(int i=0;i<n;i++)ff[i]=(ans[i].a+0.5)/n;
for(int i=0;i<n;i++)ff[i+1]+=ff[i]/10,ff[i]%=10;
int aa=0;
for(int i=n-1;i>=0;i--)if(ff[i])
{
aa=i;
break;
}
for(int i=aa;i>=0;i--)printf("%d",ff[i]);
return 0;
}
这份代码在 darkbzoj 上WA了(bzoj2179),但在你谷上A了,能hack一下吗?