把一个n位数看做n-1次的多项式，每一项的系数是反过来的每一位

最后每一项系数进进位搞一搞就行了

（数组一定要开到2的次数..要不然极端数据会RE）

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 const int maxn=132000; 7 const double Pi=acos(-1); 8  9 struct Cpx{10     double x,y;11     Cpx(double xx=0,double yy=0){x=xx;y=yy;}12 }X[maxn],Y[maxn];13 Cpx operator *(Cpx a,Cpx b){
   return Cpx(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}14 Cpx operator +(Cpx a,Cpx b){
   return Cpx(a.x+b.x,a.y+b.y);}15 Cpx operator -(Cpx a,Cpx b){
   return Cpx(a.x-b.x,a.y-b.y);}16 int N,M,rev[maxn],ans[maxn];17 18 void rd(Cpx *A){19     char c=getchar();20     while(c<'0'||c>'9') c=getchar();21     int i=N-1;22     while(c>='0'&&c<='9') A[i--].x=(int)(c-'0'),c=getchar();23 }24 25 void fft(Cpx *A,int opt){26     for(int i=0;i
         
          >1]>>1)|((i&1)<<(j-1));45     fft(X,1);fft(Y,1);46     for(i=0;i
          
           =0&&!ans[i];i--);50 for(;i>=0;i--) printf("%d",ans[i]);51 }