CFR 7 D. Palindrome Degree ( Hash, DP, Palindrome )

Problem - D - Codeforces

題意：
f( s ) = k, if f( s[ 0, s.len / 2 ) ) = f( s[ ( len + 1 ) / 2, s.len ) ) = k - 1,
_______= 0, otherwise
給字串 seq，求 Sigma{ f( s ), for all s is prefix substring of seq }

資料規模：
字串長度 ≤ 5e6
TL: 500 ms
ML: 256 MB

解法：
首先預處理 hash。現在可以 O( 1 ) 判斷任意一個前綴是否為回文。接著考慮，如果是回文，那左半邊和右半邊是等價的，所以函數值一定也一樣。因此轉移式很顯然：
dp[ i ]：f( seq[ 0, i ) )
dp[ i ] = 0, if seq[ 0, i ) is not palindrome
________= dp[ i / 2 ] + 1, otherwise

時間 / 空間複雜度：
O( | S | )

string seq;

void init(){
  cin >> seq;
}

const int BASE = 301;
const int MOD[] = { ( int ) 1e9 + 7, ( int ) 1e9 + 9 };

vi phash[ 2 ];
vi rvphash[ 2 ];
vi pbase[ 2 ];

vi dp;

void preprocess(){
  for( int t = 0; t < 1; ++t ){
    pbase[ t ] = rvphash[ t ] = phash[ t ] = vi( seq.size() + 1 );
    pbase[ t ][ 0 ] = 1;
    for( int i = 0; i + 1 < pbase[ t ].size(); ++i ){
      pbase[ t ][ i + 1 ] = 1LL * pbase[ t ][ i ] * BASE % MOD[ t ];
    }
    for( int i = 0; i < seq.size(); ++i ){
      phash[ t ][ i + 1 ] = ( 1LL * phash[ t ][ i ] * BASE + seq[ i ] ) % MOD[ t ];
      rvphash[ t ][ i + 1 ] = ( 1LL * rvphash[ t ][ i ] * BASE + seq[ seq.size() - 1 - i ] ) % MOD[ t ];
    }
  }
  dp = vi( seq.size() + 1 );
  dp[ 1 ] = 1;
  for( int i = 2; i <= seq.size(); ++i ){
    int ng = 0;
    for( int t = 0; t < 1; ++t ){
      int lhv = phash[ t ][ i / 2 ];
      int rhv = ( 1LL * rvphash[ t ][ seq.size() - ( i + 1 ) / 2 ] - 1LL * pbase[ t ][ i / 2 ] * rvphash[ t ][ seq.size() - i ] ) % MOD[ t ];
      if( rhv < 0 ) rhv += MOD[ t ];
      ng |= lhv != rhv;
    }
    if( ng ) continue;
    dp[ i ] = dp[ i / 2 ] + 1;
  }
}

void solve(){
  int ans = 0;
  for( int i = 1; i <= seq.size(); ++i ){
    ans += dp[ i ];
  }
  cout << ans << endl;
}