# CFR 159 D. Palindrome pairs ( DP )

Problem - D - Codeforces

dp[ i ] : 考慮完 i 個字元時的答案
dp[ i ] = dp[ i - 1 ] + SIGMA{ spal[ j ] | 所有 j 滿足 s[ j .. i ] 為回文 }

```string seq;

void init(){
cin >> seq;
}

vvi is_pal; // [ l, r ]
vi spal;
vl dp;

void preprocess(){
is_pal = vvi( seq.size() + 1, vi( seq.size() + 1 ) );
for( int i = 0; i < seq.size(); ++i )
is_pal[ i ][ i ] = 1;
for( int i = 0; i + 2 <= seq.size(); ++i )
if( seq[ i ] == seq[ i + 1 ] )
is_pal[ i ][ i + 1 ] = 1;
for( int len = 1; len + 2 <= seq.size(); ++len )
for( int i = 1; i + len < seq.size(); ++i )
if( is_pal[ i ][ i + len - 1 ] )
if( seq[ i - 1 ] == seq[ i + len ] )
is_pal[ i - 1 ][ i + len ] = 1;
spal = vi( seq.size() + 1 );
for( int i = 0; i < seq.size(); ++i )
for( int j = i; j < seq.size(); ++j )
spal[ j + 1 ] += is_pal[ i ][ j ];
for( int i = 0; i < seq.size(); ++i )
spal[ i + 1 ] += spal[ i ];
dp = vl( seq.size() + 1 );
for( int i = 0; i < seq.size(); ++i ){
dp[ i + 1 ] += dp[ i ];
for( int j = 0; j <= i; ++j )
if( is_pal[ j ][ i ] )
dp[ i + 1 ] += spal[ j ];
}
}

void solve(){
cout << dp[ ( int ) seq.size() ] << endl;
}
```