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

GreenCloudS

 
 
 

日志

 
 

BZOJ-3647: 密码破译(HASH)  

2014-07-21 16:49:00|  分类: oi,bzoj,hash,字 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


首先我们发现要是可以分成n块,那么对于任意d|n,都可以分成d块,所以枚举长度的质因数,然后HASH判一下成不成立,最后乘起来就好啦,预处理的话质因数分解是log n的,所以总复杂度是O(n log n)-O(log n)。


代码(200W查询多么可怕,POI原题即视感):

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <cmath>

  • #include <vector>

  •  

  • using namespace std ;

  •  

  • typedef long long ll ;

  •  

  • const int p = 31 , P = 1000173169 ;

  • const int maxn = 501000 ;

  •  

  • char s[ maxn ] ;

  • int n , m ;

  •  

  • bool flag[ maxn ] ;

  • vector < int > vec[ maxn ] ;

  • int prm[ maxn ] , pn = 0 ;

  •  

  • inline int power( int x , int cnt ) {

  •         int y = 1 ;

  •         for ( ; cnt ; cnt >>= 1 ) {

  •                 if ( cnt & 1 ) y = ( ll ) y * x % P ;

  •                 x = ( ll ) x * x % P ;

  •         }

  •         return y ;

  • }

  •  

  • int mul[ maxn ] , pre[ maxn ] ;

  •  

  • inline void Init(  ) {

  •         memset( flag , true , sizeof( flag ) ) ;

  •         for ( int i = 2 ; i <= n ; ++ i ) {

  •                 if ( flag[ i ] ) prm[ ++ pn ] = i ;

  •                 for ( int j = 1 ; i * prm[ j ] <= n && j <= pn ; ++ j ) {

  •                         flag[ i * prm[ j ] ] = false ;

  •                         if ( ! ( i % prm[ j ] ) ) break ;

  •                 }

  •         }

  •         for ( int i = 0 ; i ++ < pn ; ) {

  •                 for ( int j = prm[ i ] ; j <= n ; j += prm[ i ] ) vec[ j ].push_back( prm[ i ] ) ;

  •         }

  •         mul[ 0 ] = 1 ;

  •         for ( int i = 0 ; i ++ < n ; ) mul[ i ] = ( ll ) mul[ i - 1 ] * p % P ;

  •         pre[ 0 ] = 0 ;

  •         for ( int i = 0 ; i ++ < n ; ) pre[ i ] = ( ( ( ll ) pre[ i - 1 ] * p % P ) + ( s[ i ] - 'a' ) ) % P ;

  • }

  •  

  • inline int query( int l , int r ) {

  •         if ( l > r ) return 0 ;

  •         int sum = ( ll ) pre[ l - 1 ] * mul[ r - l + 1 ] % P ;

  •         sum = ( pre[ r ] - sum + P ) % P ;

  •         return sum ;

  • }

  •  

  • inline bool check( int l , int r , int x ) {

  •         return query( l , r - x ) == query( l + x , r ) ;

  • }

  •  

  • inline int Query( int l , int r ) {

  •         int len = r - l + 1 , cnt = 1 , y , z ;

  •         for ( vector < int > :: iterator i = vec[ len ].begin(  ) ; i != vec[ len ].end(  ) ; ++ i ) {

  •                 for ( y = 1 ; ; ) {

  •                         if ( ! ( len % ( z = y * *i ) ) ) {

  •                                 if ( check( l , r , len / z ) ) y = z ; else break ;

  •                         } else break ;

  •                 }

  •                 cnt *= y ;

  •         }

  •         return len / cnt ;

  • }

  •  

  • int main(  ) {

  •         scanf( "%d" , &n ) ; scanf( "%s" , s + 1 ) ;

  •         Init(  ) ;

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

  •         while ( m -- ) {

  •                 int l , r ; scanf( "%d%d" , &l , &r ) ; printf( "%d\n" , Query( l , r ) ) ;

  •         }

  •         return 0 ;

  • }



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

历史上的今天

评论

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

页脚

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