BZOJ-3647: 密码破译（HASH）

题目：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 ;

}