# CFR 570 E. Pig and Palindromes ( DP )

Problem - E - Codeforces
It is obvious we should perform DP, probably one from the upper-left, the other from the bottom-right, getting close to each other, marching across grids only when they match. We cannot store both the x-y-coordinates, for the complexity will be doomed both in space and time. Nonetheless, since we are only concerned about the number of ways both corners come through ( N + M ) / 2 steps meeting each other, we can simply record the number of steps traipsed by both of them, and the x-coordinate of both of them. Now the time complexity is feasible, as O( N ^ 3 ). Since when we are examining the values for step k, we will never need values from step j, j < k - 1 any more, we can perform rolling DP on steps, reducing the space complexity O( N ^ 2 ).

```const int MOD = 1e9 + 7;

bool in_range( int x, int y, int N, int M ){
return 0 <= x and x < N and 0 <= y and y < M;
}

void solve(){
int N, M; cin >> N >> M;
vector< string > G( N );
for( int i = 0; i < N; ++i )
cin >> G[ i ];

const int adx[] = { 0, 1 };
const int ady[] = { 1, 0 };
const int bdx[] = { 0, -1 };
const int bdy[] = { -1, 0 };

vector< vvi > dp( 2, vvi( N, vi( N ) ) );
int t = 0;
dp[ t ][ 0 ][ N - 1 ] = G[ 0 ][ 0 ] == G[ N - 1 ][ M - 1 ];
for( int i = 1; i < ( N + M ) / 2; ++i, t ^= 1 ){
for( int _i = 0; _i < N; ++_i )
for( int _j = 0; _j < N; ++_j )
dp[ t ^ 1 ][ _i ][ _j ] = 0;
for( int j = 0; j < N; ++j )
for( int k = 0; k < N; ++k ) if( dp[ t ][ j ][ k ] )
int any = i - 1 - j + ady[ adi ];
if( in_range( anx, any, N, M ) )
for( int bdi = 0; bdi < 2; ++bdi ){
int bnx = k + bdx[ bdi ];
int bny = M - 1 - ( i - 1 - ( N - 1 - k ) ) + bdy[ bdi ];
if( in_range( bnx, bny, N, M ) ){
if( G[ anx ][ any ] == G[ bnx ][ bny ] )
( dp[ t ^ 1 ][ anx ][ bnx ] += dp[ t ][ j ][ k ] ) %= MOD;
}
}
}
}

int ans = 0;
for( int i = 0, mv = ( N + M ) / 2 - 1; i < N; ++i )
for( int j = 0; j < N; ++j ){
int ax = i, ay = mv - i;
int bx = j, by = M - 1 - ( mv - ( N - 1 - j ) );
if( pii( ax, ay ) == pii( bx, by ) ){
( ans += dp[ t ][ i ][ j ] ) %= MOD;
continue;
}