fft模板 HDU 1402

  1 // fft模板 HDU 1402
  2 
  3 #include <iostream>
  4 #include <cstdio>
  5 #include <cstdlib>
  6 #include <algorithm>
  7 #include <vector>
  8 #include <math.h>
  9 #include <memory.h>
 10 #include <bits/stdc++.h>
 11 using namespace std;
 12 #define LL long long
 13 typedef pair<int,int> pii;
 14 const LL inf = 0x3f3f3f3f;
 15 const LL MOD =100000000LL;
 16 const int N = 150010;
 17 const double eps = 1e-8;
 18 void fre() {freopen("in.txt","r",stdin);}
 19 void freout() {freopen("out.txt","w",stdout);}
 20 inline int read() {int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();}while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;}
 21 
 22 
 23 const double PI = acos(-1.0);
 24 //复数结构体
 25 struct Complex{
 26     double r,i;
 27     Complex(double _r = 0.0,double _i = 0.0){
 28         r = _r; i = _i;
 29     }
 30     Complex operator +(const Complex &b){
 31         return Complex(r+b.r,i+b.i);
 32     }
 33     Complex operator -(const Complex &b){
 34         return Complex(r-b.r,i-b.i);
 35     }
 36     Complex operator *(const Complex &b){
 37         return Complex(r*b.r-i*b.i,r*b.i+i*b.r);
 38     }
 39 };
 40 /*
 41  * 进行FFT和IFFT前的反转变换。
 42  * 位置i和 （i二进制反转后位置）互换
 43  * len必须去2的幂
 44  */
 45 void change(Complex y[],int len){
 46     int i,j,k;
 47     for(i = 1, j = len/2;i < len-1; i++){
 48         if(i < j)swap(y[i],y[j]);
 49         //交换互为小标反转的元素，i<j保证交换一次
 50         //i做正常的+1，j左反转类型的+1,始终保持i和j是反转的
 51         k = len/2;
 52         while( j >= k){
 53             j -= k;
 54             k /= 2;
 55         }
 56         if(j < k) j += k;
 57     }
 58 }
 59 /*
 60  * 做FFT
 61  * len必须为2^k形式，
 62  * on==1时是DFT，on==-1时是IDFT
 63  */
 64 void fft(Complex y[],int len,int on){
 65     change(y,len);
 66     for(int h = 2; h <= len; h <<= 1){
 67         Complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h));
 68         for(int j = 0;j < len;j+=h){
 69             Complex w(1,0);
 70             for(int k = j;k < j+h/2;k++){
 71                 Complex u = y[k];
 72                 Complex t = w*y[k+h/2];
 73                 y[k] = u+t;
 74                 y[k+h/2] = u-t;
 75                 w = w*wn;
 76             }
 77         }
 78     }
 79     if(on == -1)
 80         for(int i = 0;i < len;i++)
 81             y[i].r /= len;
 82 }
 83 
 84 Complex a[N],b[N];
 85 char s1[N/2],s2[N/2];
 86 int ans[N];
 87 int main(){
 88     while(~scanf("%s%s",s1,s2)){
 89          int len1=strlen(s1);
 90          int len2=strlen(s2);
 91          int l1=0,l2=0;
 92          while((1<<l1)<len1) l1++;
 93          while((1<<l2)<len2) l2++;
 94          int len=(1<<(max(l1,l2)+1));
 95          for(int i=0;i<len;i++){
 96             if(i<len1) a[i]=Complex(s1[len1-i-1]-'0',0);
 97             else a[i]=Complex(0,0);
 98             if(i<len2) b[i]=Complex(s2[len2-i-1]-'0',0);
 99             else b[i]=Complex(0,0);  
100          }
101          fft(a,len,1);
102          fft(b,len,1);
103          for(int i=0;i<len;i++)
104             a[i]=a[i]*b[i];
105          fft(a,len,-1);
106          for(int i=0;i<len;i++)
107             ans[i]=(int)(a[i].r+0.5);
108          for(int i=0;i<len-1;i++){
109             ans[i+1]+=ans[i]/10;
110             ans[i]%=10;
111          }
112          bool flag=false;
113          for(int i=len-1;i>=0;i--){
114             if(ans[i]) printf("%d",ans[i]),flag=true;
115             else if(flag||i==0)printf("0");
116         }
117         printf("
");
118     }
119     return 0;
120 }