BZOJ-2179: FFT快速傅立叶

Description

给出两个n位10进制整数x和y，你需要计算x*y。n<=60000

FFT模板题。自虐狂学多项式，没错就是我。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N (1<<20)
const double pi=acos(-1.0);
struct cp 
{
    double x,i;
    cp(double _x=0,double _i=0):x(_x),i(_i){}
    cp operator+(const cp z)const {return cp(x+z.x,i+z.i);}
    cp operator-(const cp z)const {return cp(x-z.x,i-z.i);}
    cp operator*(const cp z)const {return cp(x*z.x-i*z.i,x*z.i+i*z.x);}
};
int n,ans[N];
char st[61000];
cp n1[N],n2[N];
void FFT(cp a[],int len,int fl)
{
    int i,j,k; cp t;
    for(i=k=0;i<len;i++)
    {
        if(i>k) swap(a[i],a[k]);
        for(j=(len>>1);(k^=j)<j;j>>=1);
    }
    for(i=2;i<=len;i<<=1)
    {
        cp wn(cos(2*pi*fl/i),sin(2*pi*fl/i));
        for(j=0;j<len;j+=i)
        {
            cp w(1,0);
            for(k=j;k<j+i/2;k++,w=w*wn)
                t=w*a[k+(i>>1)],a[k+(i>>1)]=a[k]-t,a[k]=a[k]+t;
        }
    }
    if(fl==-1) for(i=0;i<len;i++) a[i].x=a[i].x/len;
}
void conv(cp a[],cp b[],int len)
{
    FFT(a,len,1); FFT(b,len,1);
    for(int i=0;i<len;i++) a[i]=a[i]*b[i];
    FFT(a,len,-1);
    for(int i=0;i<len;i++) ans[i]=int(a[i].x+0.1);
}
int main()
{
    int i,j,M=1;
    scanf("%d%s",&n,st);
    while(M<(n<<1)) M<<=1;
    for(i=0;i<n;i++) n1[n-i-1]=cp(st[i]-'0',0);
    scanf("%s",st);
    for(i=0;i<n;i++) n2[n-i-1]=cp(st[i]-'0',0);
    for(i=n;i<M;i++) n1[i]=n2[i]=cp(0,0);
    conv(n1,n2,M); M=2*n-1;
    for(i=0;i<=M;i++) ans[i+1]+=ans[i]/10,ans[i]%=10;
    while(ans[M]<=0&&M) M--;
    for(i=M;i>=0;i--) putchar('0'+ans[i]); putchar('\n');
    return 0;
}