ある配置がいい配置である必要十分条件は、以下の \(2\) つが満たされることです。

• 白い駒が \(1\) つ以上置かれている行の集合を \(rw\)、黒い駒が \(1\) つ以上置かれている行の集合を \(rb\) としたとき、\(rw \cap rb = \emptyset\)
• 白い駒が \(1\) つ以上置かれている列の集合を \(cw\)、黒い駒が \(1\) つ以上置かれている列の集合を \(cb\) としたとき、\(cw \cap cb = \emptyset\)

よって、この問題を解く上では \(rw\)、\(rb\)、\(cw\)、\(cb\) を決め打つ方針が有用です。これら \(4\) 要素を完全な全探索によって決め打つとあり得るものの個数が膨大になり、実行時間制限にはとても間に合いませんが、\(rw\) のサイズ、\(rb\) のサイズ、\(cw\) のサイズ、\(cb\) のサイズのみをそれぞれ決め打った上で最後に適切に二項係数を掛けてあげることで、計算量を多項式時間、具体的には \(O(N^2M^2)\) に抑えることができます。

具体的には、\(n\) 行 \(m\) 列のマス目に対してどの行、どの列にも \(1\) つ以上の駒が置かれているように \(x\) 個の駒を配置する方法の個数を \(f(n,m,x)\) として、答えは以下のようになります。

• \(\sum_{i=1}^{N} \sum_{j=1}^{N-i} \sum_{k=1}^{M} \sum_{l=1}^{M-k} \binom{N}{i} \times \binom{N-i}{j} \times \binom{M}{k} \times \binom{M-k}{l} \times f(i,k,B) \times f(j,l,W)\)

よって \(x=B,W\) の \(2\) 通りについて、\(1 \leq n \leq N,\ 1 \leq m \leq M\) における \(f(n,m,x)\) を \(O(N^2M^2)\) 程度の計算量で求めることができれば、この問題を合計 \(O(N^2M^2)\) で解くことができることが分かりました。

それでは、ここからは \(f(n,m,x)\) の求め方を \(2\) 通り紹介します。理解のし易さは動的計画法解の方が上だと思いますので、この問題を解けなかった人は、まずはそちらを見るようにしてください。

1. 動的計画法

\(f(n,m,x)\) の値は、\(\binom{n \times m}{x}\) から「\(1 \leq i \leq n,\ 1 \leq j \leq m,\ (i,j) \neq (n,m)\) を満たすすべての \((i,j)\) について、\(n\) 行のうち \(1\) つ以上の駒が置かれているものの数がちょうど \(i\)、\(m\) 列のうち \(1\) つ以上の駒が置かれているものの数がちょうど \(j\) であるような駒の配置の個数を足し合わせたもの」を引いたものと等しくなります。

具体的に式で書くと、

• \(f(n,m,x) = \binom{n \times m}{x} - (\sum_{1 \leq i \leq n,\ 1 \leq j \leq m,\ (i,j) \neq (n,m)} \binom{n}{i} \times \binom{m}{j} \times f(i,j,x))\) となります。

この定義通りに \(n\) の昇順 → \(m\) の昇順にループを回して動的計画法を行うと、\(O(N^2M^2)\) で \(f(n,m,x)\) のテーブルを求めることが可能です。

実装例 (PyPy3)

2. 包除原理

包除原理を考えると、\(f(n,m,x)\) は \(0 \leq i \leq n,\ 0 \leq j \leq m\) を満たすすべての \((i,j)\) について \((-1)^{i+j} \times (1\) つも駒が置かれていない行の数が \(i\) 個以上、\(1\) つも駒が置かれていない列の数が \(j\) 個以上であるような駒の配置の通り数\()\) を足し合わせたものとなります。

具体的な式で書くと、

• \(f(n,m,x) = \sum_{i=0}^{n} \sum_{j=0}^{m} (-1)^{i+j} \times \binom{n}{i} \times \binom{m}{j} \times \binom{(n-i) \times (m-j)}{x}\)

となります。これをそのまま実装すると、\(O(N^2M^2)\) で \(f(n,m,x)\) のテーブルを求めることが可能です。

実装例 (PyPy3)