题目大意:
给定l,输入两个位数为l的数A B
输出两者的乘积
FFT讲解 这个讲解蛮好的 就是讲解里面贴的模板是错误的
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
struct cpx { double x,y; cpx(double _x=0.0,double _y=0.0) { x=_x; y=_y; } cpx operator -(const cpx &b) const { return cpx(x-b.x,y-b.y); } cpx operator +(const cpx &b) const { return cpx(x+b.x,y+b.y); } cpx operator *(const cpx &b) const { return cpx(x*b.x-y*b.y,x*b.y+y*b.x); } }; void change(cpx a[],int len) /// 位置互换 len必须是2的幂 { for(int i=1,j=len/2;i<len-1;i++) { if(i<j) swap(a[i],a[j]); int k=len/2; while(j>=k) j-=k, k>>=1; if(j<k) j+=k; } } #define PI acos(-1) void fft(cpx a[],int len,int on)/// len必须是2的幂 on为1时dft -1时idft { change(a,len); for(int i=1;i<len;i <<= 1) { cpx wn(cos(PI/i),on*sin(PI/i)); for(int j=0;j<len;j+=(i<<1)) { cpx w(1,0); for(int k=0;k<i;k++,w=w*wn) { cpx u=a[j+k], v=w*a[j+k+i]; a[j+k]=u+v, a[j+k+i]=u-v; } } } if(on==-1) { for(int i=0;i<len;i++) a[i].x/=len; } }
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
struct cpx { double x,y; cpx(double _x=0.0,double _y=0.0) { x=_x; y=_y; } cpx operator - (const cpx &b)const { return cpx(x-b.x,y-b.y); } cpx operator + (const cpx &b)const { return cpx(x+b.x,y+b.y); } cpx operator * (const cpx &b)const { return cpx(x*b.x-y*b.y,x*b.y+y*b.x); } }; void fft(cpx a[],int on) { for(int i=0;i<len;i++) if(i<r[i]) swap(a[i],a[r[i]]); for(int i=1;i<len;i<<=1) { cpx wn(cos(PI/i),on*sin(PI/i)); for(int j=0;j<len;j+=(i<<1)) { cpx w(1,0); for(int k=0;k<i;k++,w=w*wn) { cpx u=a[j+k], v=w*a[j+k+i]; a[j+k]=u+v, a[j+k+i]=u-v; } } } } int main() { ...... while(len<d*2) len <<= 1, l++; // 将长度补到2的幂 for(int i=0;i<len;i++) r[i]=( r[i>>1]>>1 )|( (i&1)<<(l-1) ); ...... }
这题是把两个数看成
A=a1*10^0+a2*10^1+a3*10^2...+al*10^(l-1)
B=b1*10^0+b2*10^1+b3*10^2...+bl*10^(l-1)
的形式
这样就变成了多项式相乘
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <bits/stdc++.h> #define PI acos(-1) #define MAXN 300004 using namespace std; struct cpx{ double x,y; cpx(double _x=0.0,double _y=0.0) { x=_x; y=_y; } cpx operator-(const cpx &b)const { return cpx(x-b.x,y-b.y); } cpx operator+(const cpx &b)const { return cpx(x+b.x,y+b.y); } cpx operator*(const cpx &b)const { return cpx(x*b.x-y*b.y,x*b.y+y*b.x); } }x1[MAXN/2], x2[MAXN/2]; char str1[MAXN/2], str2[MAXN/2]; int sum[MAXN], l; void change(cpx a[],int len) /// 位置互换 len必须是2的幂 { for(int i=1,j=len/2;i<len-1;i++) { if(i<j) swap(a[i],a[j]); int k=len/2; while(j>=k) { j-=k, k >>= 1; } if(j<k) j+=k; } } void fft(cpx a[],int len,int on)/// len必须是2的幂 on为1时dft -1时idft { change(a,len); for(int i=1;i<len;i <<= 1) { cpx wn(cos(PI/i),on*sin(PI/i)); for(int j=0;j<len;j+=(i<<1)) { cpx w(1,0); for(int k=0;k<i;k++,w=w*wn) { cpx u=a[j+k], t=w*a[j+k+i]; a[j+k]=u+t, a[j+k+i]=u-t; } } } if(on==-1) { for(int i=0;i<len;i++) a[i].x/=len; } } int main() { while(~scanf("%d",&l)) { scanf("%s%s",str1,str2); int len=1; while(len<l*2) len <<= 1; // 将长度补到2的幂 for(int i=0;i<l;i++) x1[i]=cpx(str1[l-1-i]-'0',0), x2[i]=cpx(str2[l-1-i]-'0',0); for(int i=l;i<len;i++) x1[i]=x2[i]=cpx(0,0); // 不足补0 fft(x1,len,1); fft(x2,len,1); /// dft转为点值表达 for(int i=0;i<len;i++) x1[i]=x1[i]*x2[i]; // 计算 fft(x1,len,-1); /// idft转为系数表达 for(int i=0;i<len;i++) sum[i]=(int)(x1[i].x+0.1); // 四舍五入 for(int i=0;i<len;i++) sum[i+1]+=sum[i]/10, sum[i]%=10; // 进制 while(sum[len]==0 && len>0) len--; // 去前导0 for(int i=len;i>=0;i--) printf("%d",sum[i]); printf(" "); } return 0; }
两种模板的细节区别在于
(2)在四舍五入时除len ,而(1)是在FFT中判断开关on再除len
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <bits/stdc++.h> #define PI acos(-1.0) const int MAXN=200100; using namespace std; struct cpx { double x,y; cpx(double _x=0.0,double _y=0.0) { x=_x; y=_y; } cpx operator - (const cpx &b)const { return cpx(x-b.x,y-b.y); } cpx operator + (const cpx &b)const { return cpx(x+b.x,y+b.y); } cpx operator * (const cpx &b)const { return cpx(x*b.x-y*b.y,x*b.y+y*b.x); } }x1[MAXN], x2[MAXN]; int n, m, len=1; int l, r[MAXN], sum[MAXN]; char str1[MAXN],str2[MAXN]; void fft(cpx a[],int on) { for(int i=0;i<len;i++) if(i<r[i]) swap(a[i],a[r[i]]); for(int i=1;i<len;i<<=1) { cpx wn(cos(PI/i),on*sin(PI/i)); for(int j=0;j<len;j+=(i<<1)) { cpx w(1,0); for(int k=0;k<i;k++,w=w*wn) { cpx u=a[j+k], v=w*a[j+k+i]; a[j+k]=u+v, a[j+k+i]=u-v; } } } } int main() { int d; while(~scanf("%d",&d)) { scanf("%s%s",str1,str2); while(len<d*2) len <<= 1, l++; // 将长度补到2的幂 for(int i=0;i<d;i++) x1[i]=cpx(str1[d-1-i]-'0',0), x2[i]=cpx(str2[d-1-i]-'0',0); for(int i=0;i<len;i++) r[i]=( r[i>>1]>>1 )|( (i&1)<<(l-1) ); fft(x1,1); fft(x2,1); /// dft转为点值表达 for(int i=0;i<len;i++) x1[i]=x1[i]*x2[i]; // 计算 fft(x1,-1); /// idft转为系数表达 for(int i=0;i<len;i++) sum[i]=(int)(x1[i].x/len+0.1); // 四舍五入 for(int i=0;i<len;i++) sum[i+1]+=sum[i]/10, sum[i]%=10; // 进制 while(sum[len]==0 && len>0) len--; // 去前导0 for(int i=len;i>=0;i--) printf("%d",sum[i]); printf(" "); } return 0; }