Description

给出两个n位10进制整数x和y，你需要计算x*y。

Input

第一行一个正整数n。 第二行描述一个位数为n的正整数x。 第三行描述一个位数为n的正整数y。

Output

输出一行，即x*y的结果。

Sample Input

1

3

4

Sample Output

12

数据范围：

n<=60000

Solution

FFT模板题，做的时候注意处理一下进位和前导零就好

Code

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define N (240000+100) 6 using namespace std; 7 double pi=acos(-1.0); 8 struct complex 9 {10     double x,y;11     complex (double xx=0,double yy=0)12     {13         x=xx; y=yy;14     }15 }a[N],b[N];16 int n=-1,m=-1,t,fn,l,r[N];17 char ch;18 19 complex operator + (complex a,complex b){
   return complex(a.x+b.x,a.y+b.y);}20 complex operator - (complex a,complex b){
   return complex(a.x-b.x,a.y-b.y);}21 complex operator * (complex a,complex b){
   return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}22 complex operator / (complex a,double b){
   return complex(a.x/b,a.y/b);}23 24 void FFT(int n,complex *a,int opt)25 {26     for (int i=0; i
         
          '9') ch=getchar();52         if (n==-1 && ch=='0') continue;53         a[++n].x=ch-'0';54     }55     for (int i=0; i<=t; ++i)56     {57         ch=getchar();58         while (ch<'0' || ch>'9') ch=getchar();59         if (m==-1 && ch=='0') continue;60         b[++m].x=ch-'0';61     }62     if (m==-1) m=0;63     if (n==-1) n=0;64     fn=1;65     while (fn<=n+m) fn<<=1, l++;66     for (int i=0;i
          
           >1]>>1) | ((i&1)<<(l-1));68 69 FFT(fn,a,1); FFT(fn,b,1);70 for (int i=0;i<=fn;++i)71 a[i]=a[i]*b[i];72 FFT(fn,a,-1);73 for (int i=n+m;i>=1;--i)74 {75 a[i-1].x+=(int)(a[i].x+0.5)/10;76 a[i].x=(int)(a[i].x+0.5)%10;77 }78 int p=0;79 while ((int)(a[p].x+0.5)==0 && p