ABC 3 D - AtCoder社の冬 ( DP )

D: AtCoder社の冬 - AtCoder Beginner Contest 003 | AtCoder
torus711さんの解き方( DPは想定解ではない模様 )が勉強になりました。ありがとうございます。
torus711.hatenablog.com
X * Y の小長方形をDPで方法数を求めます、その小長方形が条件を満たす様、一番上/左/下/右が埋まれているかどうかをバイナリでエンコードします。直接dとlの使われた数をそれぞれ状態に組み込んでしまうと900^3になりやばいです。なのでまとめて数えて、最後にコンビネーションと掛けます。

#include <bits/stdc++.h>
using namespace std;
const int MAXR = 30;
const int MAXC = 30;
const int MOD = 1e9 + 7;
typedef long long ll;
#define rep( i, a ) for(int i = 0; i < (int)( a ); ++i)

int r, c;
int x, y;
int d, l;

int C[ MAXR * MAXC + 1 ][ MAXR * MAXC + 1 ];
int nCk(int n, int k){
    C[ 0 ][ 0 ] = 1;
    rep( i, n ) rep( j, i + 1 )
        ( C[ i + 1 ][ j ] += C[ i ][ j ] ) %= MOD,
        ( C[ i + 1 ][ j + 1 ] += C[ i ][ j ] ) %= MOD;
    return C[ n ][ k ];
}

// pos / number of d + l / ( u, l, d, r )
int dp[ MAXR * MAXC + 1 ][ MAXR * MAXC + 1 ][ 1 << 4 ];

void solve(){
    memset( dp, 0, sizeof(dp) );
    dp[ 0 ][ 0 ][ 0 ] = 1;
    rep( i, x * y ) rep( j, x * y + 1 ) rep( k, ( 1 << 4 ) ){
        int nk = k;
        nk |= ( i / y == 0 ) << 0;
        nk |= ( i % y == 0 ) << 1;
        nk |= ( i / y == x - 1 ) << 2;
        nk |= ( i % y == y - 1 ) << 3;
        ( dp[ i + 1 ][ j ][ k ] += dp[ i ][ j ][ k ] ) %= MOD;
        ( dp[ i + 1 ][ j + 1 ][ nk ] += dp[ i ][ j ][ k ] ) %= MOD;
    }
    ll ans = (ll)dp[ x * y ][ d + l ][ ( 1 << 4 ) - 1 ] * nCk( d + l, d ) % MOD;
    ( ans *= r - x + 1 ) %= MOD; // 平行移動
    ( ans *= c - y + 1 ) %= MOD;
    printf("%lld\n", ans);
}

int main(){
    scanf("%d%d", &r, &c);
    scanf("%d%d", &x, &y);
    scanf("%d%d", &d, &l);
    solve();
    return 0;
}