bzoj千题计划166：bzoj2179: FFT快速傅立叶

http://www.lydsy.com/JudgeOnline/problem.php?id=2179
FFT做高精乘
#include<cmath>

#include<cstdio>

#include<complex>

using namespace std;

#define N 60001

const int M=(<<)+;

const double pi=acos(-);

typedef complex<double> E;

int n;

char s[N];

int r[M];

E a[M],b[M];

int res[M];

void fft(E *a,int f)

{

    for(int i=;i<n;++i)

        if(i<r[i]) swap(a[i],a[r[i]]);

    for(int i=;i<n;i<<=)

    {

        E wn(cos(pi/i),f*sin(pi/i));

        for(int p=i<<,j=;j<n;j+=p)

        {

            E w(,);

            for(int k=;k<i;++k,w*=wn)

            {

                E x=a[j+k],y=w*a[j+k+i];

                a[j+k]=x+y; a[j+k+i]=x-y;

            }

        }

    }

}

int main()

{

    int m;

    scanf("%d",&n);

    n--; m=n;

    scanf("%s",s);

    for(int i=n;i>=;--i) a[n-i]=s[i]-'';

    scanf("%s",s);

    for(int i=m;i>=;--i) b[m-i]=s[i]-'';

    m+=n; int bit=;

    for(n=;n<=m;n<<=) bit++;

    for(int i=;i<n;++i) r[i]=(r[i>>]>>)|((i&)<<bit-);

    fft(a,);

    fft(b,);

    for(int i=;i<n;++i) a[i]=a[i]*b[i];

    fft(a,-);

    for(int i=;i<=m;++i) res[i]=(int)(a[i].real()/n+0.5);

    for(int i=;i<=m;++i) res[i+]+=res[i]/,res[i]%=;

    if(res[m+]) m++;

    //while(m && !res[m]) --m;

    for(int i=m;i>=;--i) printf("%d",res[i]);

}