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

GreenCloudS

 
 
 

日志

 
 

BZOJ-3527: [Zjoi2014]力(FFT)  

2014-05-07 21:11:00|  分类: oi,bzoj,FFT |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


开始是不会的,后来ORZ了题解之后就惊奇的发现把qi提取出来就是两个裸的卷积,那就FFT啦。


代码(FFT写挫了,慢的要死):

  • #include <cstdio>
  • #include <algorithm>
  • #include <cstring>
  • #include <complex>
  • #include <cmath>
  •  
  • using namespace std ;
  •  
  • #define rep( i , x ) for ( int i = 0 ; i < x ; ++ i )
  •  
  • typedef double ld ;
  • typedef complex < ld > cd ;
  •  
  • const int maxn = 801000 ;
  •  
  • ld PI = acos( 0.0 ) * 2.0 ;
  •  
  • cd A[ maxn ] ;
  • int s[ maxn ] ;
  •  
  • void FFT( cd *d , int n , bool flag ) {
  •     ld pi = flag ? PI : - PI ;
  •     int i , j , p , l , k , len , cnt ;
  •     cd rec , ret , e , w ; 
  •     rep( i , n ) s[ i ] = 0 ; 
  •     for ( i = 1 , j = n >> 1 ; i < n ; i <<= 1 , j >>= 1 ) for ( k = 0 ; k < i ; ++ k ) s[ i + k ] = j ; 
  •     for ( i = 1 ; i <= n ; i <<= 1 ) for ( j = 0 ; j < i ; ++ j ) s[ j + i ] |= s[ j ] ;
  •     rep( i , n ) A[ i ] = d[ s[ i ] ] ;
  •     for ( i = 1 , cnt = 2 ; i < n ; i <<= 1 , cnt <<= 1 ) {
  •         len = i << 1 ; 
  •         e = exp( 2 * pi * cd( 0 , 1 ) / ld( cnt ) ) , w = cd( 1 , 0 ) ;
  •         for ( p = 0 ; p < i ; ++ p , w *= e ) {
  •             for ( l = 0 ; l < n ; l += len ) {
  •                 cd ret = A[ l + p ] , rec = A[ l + p + i ] * w ;
  •                 A[ l + p ] = ret + rec , A[ l + p + i ] = ret - rec ;
  •             }
  •         }
  •     }
  •     rep( i , n ) d[ i ] = A[ i ] ;
  •     if ( ! flag ) rep( i , n ) d[ i ] /= ld( n ) ;
  • }
  •  
  • cd a[ maxn ] , b[ maxn ] , c[ maxn ] ;
  • int n , m ; 
  • double q[ maxn ] ;
  • ld ans[ maxn ] ;
  •  
  • ld sqr( ld x ) {
  •     return x * x ;
  • }
  •  
  • int main(  ) {
  •     scanf( "%d" , &n ) ;
  •     rep( i , n ) scanf( "%lf" , q + i ) ;
  •     for ( m = 1 ; m < n ; m <<= 1 ) ;
  •     m <<= 1 ; 
  •     rep( i , m ) a[ i ] = b[ i ] = cd( 0 , 0 ) ;
  •     rep( i , n ) {
  •         a[ i ] = cd( q[ i ] , 0 ) , b[ i ] = cd( ld( 1 ) / sqr( ld( i + 1 ) ) , 0 ) ;
  •     }
  •     FFT( a , m , true ) , FFT( b , m , true ) ;
  •     rep( i , m ) c[ i ] = a[ i ] * b[ i ] ;
  •     FFT( c , m , false ) ;
  •     rep( i , n ) if ( ! i ) ans[ i ] = 0 ; else ans[ i ] = c[ i - 1 ].real(  ) ;
  •     rep( i , m ) a[ i ] = b[ i ] = cd( 0 , 0 ) ;
  •     rep( i , n ) {
  •         a[ i ] = cd( q[ n - i - 1 ] , 0 ) , b[ i ] = cd( ld( 1 ) / sqr( ld( i + 1 ) ) , 0 ) ;
  •     }
  •     FFT( a , m , true ) , FFT( b , m , true ) ;
  •     rep( i , m ) c[ i ] = a[ i ] * b[ i ] ;
  •     FFT( c , m , false ) ;
  •     rep( i , n ) if ( i < n - 1 ) ans[ i ] -= c[ n - i - 2 ].real(  ) ;
  •     rep( i , n ) printf( "%.3f\n" , double( ans[ i ] ) ) ;
  •     return 0 ;
  • }



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

历史上的今天

评论

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

页脚

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