# 洛谷P1919 【模板】A*B Problem升级版（FFT快速傅里叶）

2018-02-12 18:55:21来源:cnblogs.com作者:自为风月马前卒人点击

`134`

`12`

## 说明

n<=60000

emmmm感觉学了FFT没什么乱用啊，，

`#include<iostream>#include<cstdio>#include<cmath>using namespace std;const int MAXN=1e5+10;const double Pi=acos(-1.0);int r[MAXN],l=0,limit=1,c[MAXN];char sa[MAXN],sb[MAXN];struct complex{    double x,y;    complex(double xx=0,double yy=0){x=xx,y=yy;}}a[MAXN],b[MAXN];complex operator + (complex a,complex b){return complex(a.x+b.x,a.y+b.y);}complex operator - (complex a,complex b){return complex(a.x-b.x,a.y-b.y);}complex operator * (complex a,complex b){return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}void FFT(complex *a,int type){    for(int i=0;i<limit;i++)        if(i<r[i])             swap(a[i],a[r[i]]);    for(int mid=1;mid<limit;mid<<=1)    {        complex Wn(cos(Pi/mid),type*sin(Pi/mid) );        for(int R=mid<<1,j=0;j<limit;j+=R)        {            complex w(1,0);            for(int k=0;k<mid;k++,w=w*Wn)            {                complex x=a[j+k],y=w*a[j+k+mid];                a[j+k]=x+y;                a[j+k+mid]=x-y;            }        }    }}int main(){    #ifdef WIN32    freopen("a.in","r",stdin);    #else     #endif    int N;    scanf("%d",&N);N--;    scanf("%s%s",sa,sb);    for(int i=0;i<=N;i++) a[i].x=sa[N-i]-'0',b[i].x=sb[N-i]-'0';    while(limit<=N*2)         limit<<=1,l++;    for(int i=0;i<=limit;i++) r[i]=(r[i>>1]>>1) | ((i&1)<<(l-1) );    FFT(a,1);    FFT(b,1);    for(int i=0;i<=limit;i++) a[i]=a[i]*b[i];    FFT(a,-1);    for(int i=0;i<=limit;i++) c[i]=(int)(a[i].x/limit+0.5);    //for(int i=1;i<=limit;i++) printf("%d ",c[i]);printf("/n");    for(int i=0;i<=limit;i++)    {        if(c[i]>10)        {            c[i+1]+=c[i]/10,c[i]%=10;            if(i+1>limit) limit++;        }    }    for(int i=limit;i>=0;i--)        if(c[i]==0) limit--;        else break;    for(int i=limit;i>=0;i--)        printf("%d",c[i]);    return 0;}`