1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<complex> 6 #include<cmath> 7 #define pi acos(-1) 8 using namespace std; 9 const int mxn=(1<<17)+7;10 typedef complex<double>cd;11 char sa[mxn],sb[mxn];12 cd a[mxn],b[mxn];13 int rev[mxn],c[mxn];14 int n,l=0;15 double FFT(cd* a,int flag){16     int i,j;17     for(i=0;i<n;i++)18         if(i<rev[i])swap(a[i],a[rev[i]]);19     for(i=1;i<n;i<<=1){20 //        cd wn(cos((2*pi)/(2*i),flag*sin((2*pi)/(2*i)));21         cd wn(cos(pi/i),flag*sin(pi/i));22         for(j=0;j<n;j+=(i<<1)){23             cd w(1,0);24             for(int k=0;k<i;k++,w*=wn){25                 cd x=a[j+k],y=w*a[j+k+i];26                 a[j+k]=x+y;27                 a[j+k+i]=x-y;28             }29         }30     }31     if(flag==-1)for(int i=0;i<n;i++)a[i]/=n;32 }33 void multi(){for(int i=0;i<n;i++)a[i]*=b[i];return;}34 int main(){35     int i,j;36     scanf("%d%s%s",&n,sa,sb);37     for(i=0;i<n;i++){38         a[i]=sa[n-i-1]-‘0‘;    b[i]=sb[n-i-1]-‘0‘;39     }40     int m=n<<1;41     for(n=1;n<m;n<<=1)l++;42     for(i=0;i<n;i++){//预处理反转数组 43         rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));44     }45     FFT(a,1);FFT(b,1);//系数表达式转为点阵表达式 46     multi();47     FFT(a,-1);//点阵表达式转为系数表达式48     for(i=0;i<m;i++)c[i]=(int)(a[i].real()+0.1);49     for(i=0;i<m;i++)50         if(c[i]>=10){c[i+1]+=c[i]/10;c[i]%=10;}51         else if(!c[i] && i==m-1)m--;52     for(i=m-1;i>=0;i--)printf("%d",c[i]);53     return 0;54 }