题解 P1919 【【模板】A*B Problem升级版（FFT快速傅里叶）】
斯德哥尔摩
2017-10-21 11:55:22
FFT 板子。。。
注意:
1.最好手写，不然会 TLE
2.FFT 正确食用姿势：系数 - >点值- > 系数
即：(1)如果是fft(a,1)相当于从系数转为点值
(2)如果是fft(b,-1)相当于从点值转为系数
3.利用蝴蝶变换实现迭代版，在代码里面的加速。。。
4.去掉前导零。。。
看代码吧（虽丑）：
```cpp
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<cmath>
#define N (1<<18)//如果不介意，可以开小点
using namespace std;
struct cmpx{//不一样的结构体，运算符重载
double r,i;
cmpx operator + (const cmpx &a)const{return (cmpx){r+a.r,i+a.i};}
cmpx operator - (const cmpx &a)const{return (cmpx){r-a.r,i-a.i};}
cmpx operator * (const cmpx &a)const{return (cmpx){r*a.r-i*a.i,r*a.i+i*a.r};}
};
int rev[N];
cmpx A[N],a[N],b[N],c[N];
int L,n;
void DFT(cmpx a[],int f){
int i,j,k;
for(i=0;i<L;i++)
A[i]=a[rev[i]];
for(i=0;i<L;i++)
a[i]=A[i];
for(i=2;i<=L;i<<=1){
cmpx wi=(cmpx){cos(2.0*M_PI/i),f*sin(2.0*M_PI/i)};
for(k=0;k<L;k+=i){
cmpx w=(cmpx){1.0,0.0},x,y;
for(j=0;j<i/2;j++){
x=a[k+j];
y=w*a[k+j+i/2];
a[k+j]=x+y;
a[k+j+i/2]=x-y;
w=w*wi;
}
}
}
if(f==-1)
for(i=0;i<L;i++)
a[i].r/=L;
}
void FFT(cmpx a[],cmpx b[],cmpx c[]){
int i;
DFT(a,1);
DFT(b,1);
for(i=0;i<L;i++)
c[i]=a[i]*b[i];
DFT(c,-1);
}
void init(int tmp){
int i,t,j;
for(n=0,L=1;L<tmp;L<<=1)
n++;
n++;
L<<=1;
for(i=0;i<L;i++)
for(t=i,j=0;j<n;j++){
rev[i]<<=1;
rev[i]|=t&1;
t>>=1;
}
}
int ans[N];
void DSC(){//开始处理问题，开始处理问题，开始处理问题，重要的事情说3遍！
int l1=0,l2=0,i;
char ch=getchar();
while(ch>'9'||ch<'0')
ch=getchar();
while(ch>='0'&&ch<='9'){
a[l1].r=ch-'0';
a[l1++].i=0.0;
ch=getchar();
}
while(ch>'9'||ch<'0')
ch=getchar();
while(ch>='0'&&ch<='9'){
b[l2].r=ch-'0';
b[l2++].i=0.0;
ch=getchar();
}
reverse(a,a+l1);
reverse(b,b+l2);
init(max(l1,l2));
FFT(a,b,c);
for(i=0;i<L;i++)
ans[i]=(int)(c[i].r+0.5);
for(i=0;i<L;i++){
ans[i+1]+=ans[i]/10;
ans[i]%=10;
}
L=l1+l2+1;
while(!ans[L]&&L>0)
L--;
for(i=L;~i;i--)
putchar(ans[i]+'0');
putchar('\n');
}
int main(){//主函数so easy
DSC();
return 0;
}
```