A placement is good if and only if the following two conditions are satisfied:

• \(rw \cap rb = \emptyset\), where \(rw\) denotes the set of rows in which one or more white rooks are placed and \(rb\) denotes the set of rows in which one or more black rooks are placed
• \(cw \cap cb = \emptyset\), where \(cw\) denotes the set of columns in which one or more white rooks are placed and \(cb\) denotes the set of columns in which one or more black rooks are placed

Therefore, in order to solve this problem, it is effective to search over \(rw\), \(rb\), \(cw\), and \(cb\). While actually iterating over all possible combinations of these sets takes too long time because there are too many such combinations, we can only enumerate the sizes of \(rw\), \(rb\), \(cw\), and \(cb\), and then multiply to them proper binomial coefficients, so that the computational complexity is reduced to polynomial time, namely \(O(N^2M^2)\).

Specifically, let \(f(n,m,x)\) be the number of placements of \(x\) rooks on \(n\)-row and \(m\)-column grid so that every row and every column has one or more rooks on it, then the answer would be as follows.

• \(\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)\)

Therefore, if we could find \(f(n,m,x)\) for \(1 \leq n \leq N,\ 1 \leq m \leq M\) in about \(O(N^2M^2)\) time when \(x = B, W\), then we can solve this problem in a total of \(O(N^2M^2)\) time.

Now, we will introduce two ways to find \(f(n,m,x)\). Probably, the DP solution is easier to understand, so if you couldn’t solve this problem, please check out the former first.

1. Dynamic Programming (DP)

The value of \(\binom{n \times m}{x}\) is equal to \(\binom{n \times m}{x}\) subtracted by “the sum of number of placements in which exactly \(i\) rows out of \(n\) rows have one or more rooks each and exactly \(j\) columns out of \(m\) columns have one or more rooks each, for all \((i, j)\) such that \(1 \leq i \leq n,\ 1 \leq j \leq m,\ (i,j) \neq (n,m)\).”

Formally, it can be expressed with the following equation:

• \(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))\).

By doing Dynamic Programming according to this definition in the increasing order of \(n\) and then in the increasing order of \(m\), we can obtain the table of \(f(n,m,x)\) in a total of \(O(N^2M^2)\) time.

Sample code (PyPy3)

2. Inclusion-exclusion principle

By the inclusion-exclusion principle, \(f(n,m,x)\) is the sum of \((-1)^{i+j} \times (\) the sum of number of placements in which at least \(i\) rows have no rooks and at least \(j\) columns have no rooks\()\) over all \((i, j)\) such that \(0 \leq i \leq n,\ 0 \leq j \leq m\).

Formally, it can be expressed with the following equation:

• \(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}\).

We can directly implement this so that the table of \(f(n,m,x)\) is found in a total of \(O(N^2M^2)\) time.

Sample code (PyPy3)