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