[ABC242] F - Black and White Rooks

[Q] https://atcoder.jp/contests/abc242/tasks/abc242_f

解説AC。まず入口が難しい。
1. Bの置き方を考える。
使用する行数と列数を固定してしまう。
2. Wの置き方を考える。
Bで使った行と列を除いて、あいている行と列の中で組み合わせを考える。

N = 6, M = 7, B = 5, W = 4
として、
1. B = 5個 の置き方を考える。
たとえば 2行3列 で固定する。

bbb
bb.

2行の取り方は、N = 6 から2行をとるので、6C2
3列の取り方は、M = 7 から3列をとるので、7C3
2行3列のときの、配置の仕方は、DP[2][3][5]。これは後で求める。

2. ここからWの置き方を考える。
Bで 2行3列 を使ったので、残りはN-2行、M-3列の、4行4列。
W = 4 なので、2行2列の場合を考える。

ww
ww

2行の取り方は、残り4行 から 2行をとるので4C2
2列の取り方は、残り4列 から 2列をとるので4C2
2行2列のwの配置の仕方は、DP[2][2][4]。後で求める。

Bが2行3列、Wが2行2列のときは、
ans += 6C2 * 7C3 * DP[2][3][5] * 4C2 * 4C2 * DP[2][2][4]

こんなのを、
Bが 1行1列 のとき、Wが1行1列 ~ N行M列。
Bが 1行2列 のとき、Wが1行1列 ~ N行M-1列
...
Bが N-1行M-1列 のとき、Wが1行1列
のすべての場合で組み合わせを加算させる。

3. 駒の配置の仕方、DPを考える。
DP[N行][M列][K個] で管理する。
1. 初期値。n*m C k 通り、とりあえず全部採用する。
2. n行採用したのに要素がない行がある、とかいう不正な駒配置が含まれているので、除く。 

DP[4][4][5] を求める。
1. 初期値
DP[4][4][5]は 16か所空きマスのうち、5個設置する場合を考える。
DP[4][4][5] = 16C5 通りある。

2. 不正配置を除去。

.... // <= 1行がからっぽ
x...
.x.x
..xx

こういうNGな配置を除去する必要がある。

これは、3行4列に5個配置されている状態 DP[3][4][5]を除けばいい。
空行の選び方は、4行から使用する3行を選ぶので、4C3。
空列の選び方は、4列から使用する4列を選ぶので、4C4
DP[4][4][5] -= DP[3][4][5] * 4C3 * 4C4

同じことを、
1行1列に5個配置されている場合を除いて、
1行2列に5個配置されている場合を除いて、
1行3列に5個配置されている場合を除いて、
1行4列に5個配置されている場合を除いて、
2行1列に5個配置されている場合を除いて、
2行2列に5個配置されている場合を除いて、
...
4行3列に5個配置されている場合を除く。

4行4列の処理だけ行わない。

実装

ll N, M, B, W;
mint DP[51][51][2501];

void DPinit(){
 set<ll> K;
 K.insert(B);
 K.insert(W);
 for(ll y = 1; y <= N; ++y){
   for(ll x = 1; x <= M; ++x){
     for(ll k: K){ //DP[y][x][k]だけ入れる
       for(ll ny = 1; ny <= y; ++ny){
         for(ll nx = 1; nx <= x; ++nx){
           if (ny == y && nx == x){ // 初期入れ
             DP[y][x][k] += COM(y * x, k);
           }
           else {
             DP[y][x][k] -= DP[ny][nx][k] * COM(y, ny) * COM(x, nx);
           }
         }
       }
     }
   }
 }
}

int main(){
 cincout();
 COMinit();
 
 cin >> N >> M >> B >> W;
 DPinit();
 mint ans = 0;
 // Bの使用する行と列を決めちゃう
 for (ll by = 1; by < N; ++by){
   for(ll bx = 1; bx < M; ++bx){
     // もしBが置ききれないならスキップ
     if (max(by, bx) > B) continue;
     if (by * bx < B) continue;
     // それに伴って、Wも同じ
     for (ll wy = 1; wy <= N - by; ++wy){
       for(ll wx = 1; wx <= M - bx; ++wx){
         if (max(wy, wx) > W) continue;
         if (wy * wx < W) continue;
         ans += DP[by][bx][B] * DP[wy][wx][W] * COM(N, by) * COM(N - by, wy) * COM(M, bx) * COM(M - bx, wx);
       }
     }
   }
 }
 cout << ans << endl;
}

https://atcoder.jp/contests/abc242/submissions/30199488