因为刚学fft，想拿这题练练手，结果WA了个爽= =。
总结几点犯的错误：
1.要注意处理前导零的问题。
2.一定要注意数组大小的问题。（前一个fft的题因为没用到b数组，所以b就没管，这里使用了b数组，结果忘记给其大小乘以4倍了）
代码如下：
1 #include<bits/stdc++.h> 2 using namespace std; 3 const double pi = atan(1.0)*4; 4 const int N = 5e4 + 5; 5 typedef long long ll; 6 7 struct Complex { 8 double x,y; 9 Complex(double _x=0,double _y=0) 10 :x(_x),y(_y) {} 11 Complex operator + (Complex &tt) { return Complex(x+tt.x,y+tt.y); } 12 Complex operator - (Complex &tt) { return Complex(x-tt.x,y-tt.y); } 13 Complex operator * (Complex &tt) { return Complex(x*tt.x-y*tt.y,x*tt.y+y*tt.x); } 14 }; 15 Complex a[N*4],b[N*4]; 16 void fft(Complex *a, int n, int rev) { 17 // n是(大于等于相乘的两个数组长度)2的幂次 ； 比如长度是5 ,那么 n = 8 2^2 < 5 2^3 > 5 18 // 从0开始表示长度，对a进行操作 19 // rev==1进行DFT，==-1进行IDFT 20 for (int i = 1,j = 0; i < n; ++ i) { 21 for (int k = n>>1; k > (j^=k); k >>= 1); 22 if (i<j) std::swap(a[i],a[j]); 23 } 24 for (int m = 2; m <= n; m <<= 1) { 25 Complex wm(cos(2*pi*rev/m),sin(2*pi*rev/m)); 26 for (int i = 0; i < n; i += m) { 27 Complex w(1.0,0.0); 28 for (int j = i; j < i+m/2; ++ j) { 29 Complex t = w*a[j+m/2]; 30 a[j+m/2] = a[j] - t; 31 a[j] = a[j] + t; 32 w = w * wm; 33 } 34 } 35 } 36 if (rev==-1) { 37 for (int i = 0; i < n; ++ i) a[i].x /= n,a[i].y /= n; 38 } 39 } 40 41 char s[N], t[N]; 42 int c[N*2]; 43 44 int main(){ 45 /*a[0] = Complex(0,0); // a[0]: x的0次项。 46 a[1] = Complex(1,0); 47 a[2] = Complex(2,0); 48 a[3] = Complex(3,0); 49 50 b[0] = Complex(3,0); 51 b[1] = Complex(2,0); 52 b[2] = Complex(1,0); 53 b[3] = Complex(0,0); 54 fft(a,8,1); 55 fft(b,8,1); 56 for(int i = 0 ; i < 8 ; i ++){ 57 a[i] = a[i] * b[i]; 58 } 59 fft(a,8,-1); 60 for(int i = 0 ; i < 8 ; i ++){ 61 cout << i << " " << a[i].x << endl;; 62 }*/ 63 while(scanf("%s%s",s,t) == 2) 64 { 65 int n = strlen(s), m = strlen(t); 66 for(int i=0;i<n;i++) a[i] = Complex(s[n-i-1]-'0', 0); 67 for(int i=0;i<m;i++) b[i] = Complex(t[m-i-1]-'0', 0); 68 int len = n+m-1; 69 int LIM = 1; 70 while(LIM < len) LIM <<= 1; 71 for(int i=n;i<LIM;i++) a[i] = Complex(0, 0); 72 for(int i=m;i<LIM;i++) b[i] = Complex(0, 0); 73 fft(a, LIM, 1); 74 fft(b, LIM, 1); 75 for(int i=0;i<LIM;i++) a[i] = a[i] * b[i]; 76 fft(a, LIM, -1); 77 memset(c, 0, sizeof c); 78 for(int i=0;i<len-1;i++) 79 { 80 c[i] += (int)(a[i].x + 0.1); 81 c[i+1] += c[i] / 10; 82 c[i] %= 10; 83 } 84 c[len-1] += (int)(a[len-1].x + 0.1); 85 if(c[len-1] > 9) 86 { 87 c[len] = c[len-1] / 10; 88 c[len-1] %= 10; 89 len++; 90 } 91 for(int i=len-1;i>0;i--) if(c[i] == 0) len--; else break; // 0 * 345 = 0 instead of 000 92 for(int i=0;i<len/2;i++) swap(c[i], c[len-i-1]); 93 for(int i=0;i<len;i++) printf("%d",c[i]); 94 puts(""); 95 } 96 return 0; 97 }