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 ] ) for( int adi = 0; adi < 2; ++adi ){ int anx = j + adx[ adi ]; 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; } for( int adi = 0; adi < 2; ++adi ) if( in_range( ax + adx[ adi ], ay + ady[ adi ], N, M ) ) if( pii( ax + adx[ adi ], ay + ady[ adi ] ) == pii( bx, by ) ){ ( ans += dp[ t ][ i ][ j ] ) %= MOD; continue; } } cout << ans << endl; }