后半部分是一个很 trivial 的 dp，别的题解都讲的很清楚，但是看别的题解都同样用递推来预处理的 k 个棋子恰好占据 i 行 j 列的方案数，这里提供直接基于反演（或者说容斥）的另一种思路。
一句话做法：考虑先求一个 k 个棋子占据至多 i 行 j 列的方案数，然后反演。 单次 O(n^2m^2)。
设 f(n, m) 表示 k 个棋子占据至多 n 行 m 列的方案数，即可以为空。根据定义显然有 f(n, m) = \dbinom{nm}{k}；g(n, m) 表示恰好占据 n 行 m 列的方案数。则根据两个函数的意义我们可以得到这样一个关系：f(n, m) =\displaystyle \sum_{i \ge 0}\sum_{j \ge 0}\dbinom{n}{i}\dbinom{m}{j}g(i, j)，对其套用二项式反演可得 g(n, m) = \displaystyle\sum_{i \ge 0}\sum_{j \ge 0}\dbinom{n}{i}\dbinom{m}{j}(-1)^{n - i}(-1)^{m - j}f(i, j)，对每种颜色把 g 求出来然后再跑一个 dp 即可。