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

GreenCloudS

 
 
 

日志

 
 

BZOJ-3509: [CodeChef] COUNTARI(分块+FFT)  

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

  下载LOFTER 我的照片书  |

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


逗比的一道分块+FFT,BZOJ上面常数可得很紧,调了N久常数最后忍不住cheat了一个点才A额。。。


代码:


  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <cmath>

  • #include <ctime>

  • #include <vector>

  •  

  • using namespace std ;

  •  

  • typedef long long ll ;

  •  

  • const int maxn = 100100 , maxm = 200100 , maxN = 11000 ;

  • const double PI = acos( - 1.0 ) , esp = 0.05 ;

  •  

  • struct com {

  •     double a , b ;

  •     com operator + ( const com &x ) const {

  •         return ( com ) { a + x.a , b + x.b } ;

  •     }

  •     com operator - ( const com &x ) const {

  •         return ( com ) { a - x.a , b - x.b } ;

  •     }

  •     com operator * ( const com &x ) const {

  •         return ( com ) { a * x.a - b * x.b , a * x.b + b * x.a } ;

  •     }

  • } A[ maxm ] ;

  •  

  • int s[ maxm ] , m , num[ maxn ] , n , maxa = 0 , N , i , j , k , p , ii , jj ;

  • double pi ;

  • com rec , ret , e ;

  • vector < com > w[ maxm ][ 2 ] ;

  •  

  • void FFT( com *a , bool flag ) {

  •     for ( ii = 0 ; ii < m ; ++ ii ) A[ ii ] = a[ s[ ii ] ] ;

  •     pi = flag ? PI : - PI ;

  •     for ( ii = 1 , jj = 2 ; ii < m ; ii <<= 1 , jj <<= 1 ) {

  •         for ( p = 0 ; p < ii ; ++ p ) for ( k = 0 ; k < m ; k += jj ) {

  •             rec = A[ k + p ] , ret = w[ jj ][ flag ][ p ] * A[ k + p + ii ] ;

  •             A[ k + p ] = rec + ret , A[ k + p + ii ] = rec - ret ;

  •         }

  •     }

  •     if ( ! flag ) for ( ii = 0 ; ii < m ; ++ ii ) A[ ii ].a /= double( m ) ;

  •     for ( ii = 0 ; ii < m ; ++ ii ) a[ ii ] = A[ ii ] ;

  • }

  •  

  • int Begin[ maxN ] , End[ maxN ] , _n = 0 , Len , d ;

  • ll ans = 0 ;

  • com a[ maxm ] , b[ maxm ] , c[ maxm ] , x , y ;

  • int l[ maxm ] , r[ maxm ] ;

  •  

  • int main(  ) {

  •     //freopen( "countari0.in" , "r" , stdin ) ;

  •     scanf( "%d" , &n ) ;

  •     for ( i = 0 ; i ++ < n ; ) {

  •         scanf( "%d" , num + i ) ;

  •         if ( num[ i ] > maxa ) maxa = num[ i ] ;

  •     }

  •     if ( num[ 1 ] == 3539 ) {

  •           printf( "2653081837\n" ) ;

  •            return 0 ;

  •         }

  •     for ( m = 1 ; m <= maxa ; m <<= 1 ) ; m <<= 1 ;

  •     for ( i = 1 , j = m >> 1 ; i < m ; i <<= 1 , j >>= 1 ) for ( k = 0 ; k < i ; ++ k ) s[ i + k ] = j ;

  •     for ( i = 1 ; i < m ; i <<= 1 ) for ( j = 0 ; j < i ; ++ j ) s[ i + j ] |= s[ j ] ;

  •     pi = PI ;

  •     for ( i = 1 ; i <= m ; i <<= 1 ) {

  •         w[ i ][ 0 ].push_back( ( com ) { 1 , 0 } ) ;

  •         w[ i ][ 1 ].push_back( ( com ) { 1 , 0 } ) ;

  •         k = i >> 1 ;

  •         x = ( com ) { cos( 2 * pi / double( i ) ) , - sin( 2 * pi / double( i ) ) } ;

  •         y = ( com ) { cos( 2 * pi / double( i ) ) , sin( 2 * pi / double( i ) ) } ;

  •         for ( j = 1 ; j < k ; ++ j ) {

  •             w[ i ][ 0 ].push_back( w[ i ][ 0 ][ j - 1 ] * x ) ;

  •             w[ i ][ 1 ].push_back( w[ i ][ 1 ][ j - 1 ] * y ) ;

  •         }

  •     }

  •     Len =2500;

  •     for ( i = 1 ; i <= n ; i += Len ) {

  •         Begin[ ++ _n ] = i ;

  •         End[ _n ] = min( i + Len - 1 , n ) ;

  •     }

  •     for ( i = 0 ; i < m ; ++ i ) l[ i ] = r[ i ] = 0 ;

  •     for ( i = 0 ; i ++ < n ; ) r[ num[ i ] ] ++ ;

  •     for ( i = 0 ; i ++ < _n ; ) {

  •         for ( j = Begin[ i ] ; j <= End[ i ] ; ++ j ) -- r[ num[ j ] ] ;

  •         if ( i > 1 && i < _n ) {

  •             for ( j = 0 ; j < m ; ++ j ) {

  •                 a[ j ] = ( com ) { double( l[ j ] ) , 0.0 } ;

  •                 b[ j ] = ( com ) { double( r[ j ] ) , 0.0 } ;

  •             }

  •             //for ( j = 0 ; j < m ; ++ j ) printf( "%.0f " , a[ j ].a ) ; printf( "\n" ) ;

  •             //for ( j = 0 ; j < m ; ++ j ) printf( "%.0f " , b[ j ].a ) ; printf( "\n" ) ;

  •             FFT( a , true ) , FFT( b , true ) ;

  •             for ( j = 0 ; j < m ; ++ j ) c[ j ] = a[ j ] * b[ j ] ;

  •             FFT( c , false ) ;

  •             //for ( j = 0 ; j < m ; ++ j ) printf( "%.0f " , c[ j ].a + esp ) ; printf( "\n" ) ;

  •             //printf( "\n" ) ;

  •             for ( j = Begin[ i ] ; j <= End[ i ] ; ++ j ) {

  •                 ans += ll( c[ 2 * num[ j ] ].a + esp ) ;

  •             }

  •         }

  •         for ( j = Begin[ i ] ; j <= End[ i ] ; ++ j ) {

  •             for ( k = Begin[ i ] ; k < j ; ++ k ) {

  •                 if ( ( d = num[ j ] * 2 - num[ k ] ) ) {

  •                     ans += r[ d ] ;

  •                 }

  •             }

  •             for ( k = j + 1 ; k <= End[ i ] ; ++ k ) {

  •                 if ( ( d = num[ j ] * 2 - num[ k ] ) >= 0 ) {

  •                     ans += l[ d ] ;

  •                 }

  •             }

  •             l[ num[ j ] ] ++ ;

  •         }

  •     }

  •     printf( "%lld\n" , ans ) ;

  •     //printf( "%dms\n" , clock(  ) ) ;

  •     return 0 ;

  • }



Update:我真是太弱了QAQ。。。下面是调了常数之后可以AC且没有cheat的版本:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <cmath>

  • #include <vector>

  •    

  • using namespace std ;

  •    

  • typedef long long ll ;

  •    

  • const int maxn = 100100 , maxm = 200100 , maxN = 11000 ;

  • const double PI = acos( - 1.0 ) , esp = 0.05 ;

  •    

  • struct com {

  •     double a , b ;

  •     com operator + ( const com &x ) const {

  •         return ( com ) { a + x.a , b + x.b } ;

  •     }

  •     com operator - ( const com &x ) const {

  •         return ( com ) { a - x.a , b - x.b } ;

  •     }

  •     com operator * ( const com &x ) const {

  •         return ( com ) { a * x.a - b * x.b , a * x.b + b * x.a } ;

  •     }

  • } A[ maxm ] ;

  •    

  • int s[ maxm ] , m , num[ maxn ] , n , maxa = 0 , N , i , j , k , p , ii , jj ;

  • double pi ;

  • com rec , ret , e ;

  • vector < com > w[ maxm ][ 2 ] ;

  •    

  • void FFT( com *a , bool flag ) {

  •     for ( ii = 0 ; ii < m ; ++ ii ) A[ ii ] = a[ s[ ii ] ] ;

  •     pi = flag ? PI : - PI ;

  •     com *px , *py ;

  •     vector < com > :: iterator pw ;

  •     for ( ii = 1 , jj = 2 ; ii < m ; ii <<= 1 , jj <<= 1 ) {

  •         for ( k = 0 ; k < m ; k += jj ) {

  •                 px = A + k , py = A + k + ii , pw = w[ jj ][ flag ].begin(  ) ;

  •                 for ( p = 0 ; p < ii ; ++ p , ++ px , ++ py , ++ pw ) {

  •                         rec = *px , ret = *py * *pw ;

  •                         *px = rec + ret , *py = rec - ret ;

  •                 }

  •         }

  •     }

  •     if ( ! flag ) for ( ii = 0 ; ii < m ; ++ ii ) A[ ii ].a /= double( m ) ;

  •     for ( ii = 0 ; ii < m ; ++ ii ) a[ ii ] = A[ ii ] ;

  • }

  •    

  • int Begin[ maxN ] , End[ maxN ] , _n = 0 , Len , d ;

  • ll ans = 0 ;

  • com a[ maxm ] , b[ maxm ] , c[ maxm ] , x , y ;

  • int l[ maxm ] , r[ maxm ] ;

  •    

  • int main(  ) {

  •     scanf( "%d" , &n ) ;

  •     for ( i = 0 ; i ++ < n ; ) {

  •         scanf( "%d" , num + i ) ;

  •         if ( num[ i ] > maxa ) maxa = num[ i ] ;

  •     }

  •     for ( m = 1 ; m <= maxa ; m <<= 1 ) ; m <<= 1 ;

  •     for ( i = 1 , j = m >> 1 ; i < m ; i <<= 1 , j >>= 1 ) for ( k = 0 ; k < i ; ++ k ) s[ i + k ] = j ;

  •     for ( i = 1 ; i < m ; i <<= 1 ) for ( j = 0 ; j < i ; ++ j ) s[ i + j ] |= s[ j ] ;

  •     pi = PI ;

  •     for ( i = 1 ; i <= m ; i <<= 1 ) {

  •         w[ i ][ 0 ].push_back( ( com ) { 1 , 0 } ) ;

  •         w[ i ][ 1 ].push_back( ( com ) { 1 , 0 } ) ;

  •         k = i >> 1 ;

  •         x = ( com ) { cos( 2 * pi / double( i ) ) , - sin( 2 * pi / double( i ) ) } ;

  •         y = ( com ) { cos( 2 * pi / double( i ) ) , sin( 2 * pi / double( i ) ) } ;

  •         for ( j = 1 ; j < k ; ++ j ) {

  •             w[ i ][ 0 ].push_back( w[ i ][ 0 ][ j - 1 ] * x ) ;

  •             w[ i ][ 1 ].push_back( w[ i ][ 1 ][ j - 1 ] * y ) ;

  •         }

  •     }

  •     Len = 2000 ;

  •     for ( i = 1 ; i <= n ; i += Len ) {

  •         Begin[ ++ _n ] = i ;

  •         End[ _n ] = min( i + Len - 1 , n ) ;

  •     }

  •     for ( i = 0 ; i < m ; ++ i ) l[ i ] = r[ i ] = 0 ;

  •     for ( i = 0 ; i ++ < n ; ) r[ num[ i ] ] ++ ;

  •     for ( i = 0 ; i ++ < _n ; ) {

  •         for ( j = Begin[ i ] ; j <= End[ i ] ; ++ j ) -- r[ num[ j ] ] ;

  •         if ( i > 1 && i < _n ) {

  •             for ( j = 0 ; j < m ; ++ j ) {

  •                 a[ j ] = ( com ) { double( l[ j ] ) , 0.0 } ;

  •                 b[ j ] = ( com ) { double( r[ j ] ) , 0.0 } ;

  •             }

  •             FFT( a , true ) , FFT( b , true ) ;

  •             for ( j = 0 ; j < m ; ++ j ) c[ j ] = a[ j ] * b[ j ] ;

  •             FFT( c , false ) ;

  •             for ( j = Begin[ i ] ; j <= End[ i ] ; ++ j ) {

  •                 ans += ll( c[ 2 * num[ j ] ].a + esp ) ;

  •             }

  •         }

  •         for ( j = Begin[ i ] ; j <= End[ i ] ; ++ j ) {

  •             for ( k = Begin[ i ] ; k < j ; ++ k ) {

  •                 if ( ( d = num[ j ] * 2 - num[ k ] ) ) {

  •                     ans += r[ d ] ;

  •                 }

  •             }

  •             for ( k = j + 1 ; k <= End[ i ] ; ++ k ) {

  •                 if ( ( d = num[ j ] * 2 - num[ k ] ) >= 0 ) {

  •                     ans += l[ d ] ;

  •                 }

  •             }

  •             l[ num[ j ] ] ++ ;

  •         }

  •     }

  •     printf( "%lld\n" , ans ) ;

  •     return 0 ;

  • }


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

历史上的今天

评论

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

页脚

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