BZOJ-2179: FFT快速傅立叶

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2179

题目大意：n<=60000的高精度乘法。

第一次写FFT，本来想照着算导敲的，然后ORZ X姐的时候听说里面的代码会很慢，所以滚去YY了个渣渣的非递归版如下。。。

代码：

8b82b9014a90f6035a9b73f53b12b31bb051ed5d.jpg.png

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <complex>

  

using namespace std ;

  

#define cd complex <double>

#define PI acos(0.0)*2.0

#define maxn 32768

#define check( ch )( ch >='0'&& ch <='9')

#define base 10000

#define ll long long

  

int s[ maxn ];

cd A[ maxn ];

  

void FFT( cd *a ,int n ,bool flag ){

    for(int i =0; i < n ;++ i ) s[ i ]=0;

    for(int i =1, j = n ; i < n ; i <<=1, j >>=1)for(int h = j >>1; h < j ;++ h ) s[ h ]|= i ;

    for(int i =1; i < n ; i <<=1)for(int j =0; j < i ;++ j ) s[ j + i ]|= s[ j ];

    for(int i =0; i < n ;++ i ) A[ i ]= a[ s[ i ]];

    double pi = flag ? PI :- PI ;

    for(int step =1; step < n ; step <<=1){

        cd e =exp(cd(0,2.0* pi /double( step <<1))), w =cd(1,0);

        for(int pos =0; pos < step ;++ pos , w *= e ){

            int temp = step <<1;

            for(int i = pos ; i < n ; i += temp ){

                cd ret = A[ i ], rec = w * A[ i + step ];

                A[ i ]= ret + rec , A[ i + step ]= ret - rec ;

            }

        }

    }

    if(! flag )for(int i =0; i < n ;++ i ) A[ i ]/= n ;

    for(int i =0; i < n ;++ i ) a[ i ]= A[ i ];

}

 

int m , len , n1[ maxn ], n2[ maxn ], st[ maxn ];

 

void getnum(int*N ){

    memset( st ,0,sizeof( st ));

    int ch ;for( ch =getchar(  );!check( ch ); ch =getchar(  ));

    st[ m ]= ch -'0';

    for(int i = m -1; i ;-- i ) st[ i ]=getchar(  )-'0';

    len =0;

    for(int i =1; i <= m ; i +=4){

        int temp =0;

        for(int j = i +3; j >= i ;-- j ) temp = temp *10+ st[ j ];

        N[ len ++]= temp ;

    }

}

 

cd a[ maxn ], b[ maxn ], c[ maxn ];

ll ans[ maxn ], ansn =0;

 

void getint(int&t ){

    int ch ;for( ch =getchar(  );!check( ch ); ch =getchar(  ));

    t = ch -'0';

    for( ch =getchar(  );check( ch ); ch =getchar(  )){

        t = t *10+ ch -'0';

    }

}

 

int o[20];

 

void putint(int t ){

    if( t ){

        o[0]=0;

        for(; t ; t /=10) o[++ o[0]]= t %10;

        while( o[0]--)putchar('0'+ o[ o[0]+1]);

    }else putchar('0');

}

 

int main(  ){

    getint( m );

    getnum( n1 ),getnum( n2 );

    int k =1; m = len <<1;

    for(; k < m ; k <<=1);

    for(int i =0; i < k ;++ i ) a[ i ]=cd( n1[ i ],0);

    FFT( a , k ,true);

    for(int i =0; i < k ;++ i ) b[ i ]=cd( n2[ i ],0);

    FFT( b , k ,true);

    for(int i =0; i < k ;++ i ) c[ i ]= a[ i ]* b[ i ];

    FFT( c , k ,false);

    for(int i =0; i < k ;++ i ) ans[ i ]=( ll )( c[ i ].real(  )+0.5);

    for(int i =0; i < k ;++ i ){

        ans[ i +1]+= ans[ i ]/ base ;

        ans[ i ]%= base ;

    }

    for(int i = k ; i >=0;-- i )if( ans[ i ]){

        ansn = i ;break;

    }

    putint(int( ans[ ansn ]));

    for(int i = ansn -1; i >=0;-- i ){

        if( ans[ i ]<1000)putchar('0');

        if( ans[ i ]<100)putchar('0');

        if( ans[ i ]<10)putchar('0');

        putint(int( ans[ i ]));

    }

    putchar('\n');

    return 0;

}