0w1

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