注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

BZOJ-2179: FFT快速傅立叶  

2014-03-06 19:58:00|  分类: FFT,高精度乘法,b |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


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


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


代码:

BZOJ-2179: FFT快速傅立叶 - cjjlsdy - cjjlsdy的博客

  • #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;

  • }


  评论这张
 
阅读(5)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017