Contest Duration: - (local time) (100 minutes) Back to Home
Official

## F - Black and White Rooks Editorial by en_translator

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)

posted:
last update: