# 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

TL: 500 ms
ML: 256 MB

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;
}
```