题解

思路推导

把“不染色”看成一种不要求出现的特殊状态。若暂时忽略行列限制，长度为 $x$ 的格子序列中，要求全部 $c$ 种真实颜色均出现的方案数只与 $x$ 有关，记为 $g_x$。

做法

设 $d_k$ 表示处理当前数量的格子后，恰好已经出现 $k$ 种真实颜色的方案数。加入一个格子时，它可以不染色或使用已经出现的颜色，共有 $k+1$ 种选择；也可以首次使用一种尚未出现的颜色，共有 $c-k+1$ 种来源。因此倒序更新

$$d_k\leftarrow (k+1)d_k+(c-k+1)d_{k-1}.$$

逐个处理至 $nm$ 个格子，就能得到每个 $g_x=d_c$。

然后对空行与空列做容斥。若保留 $i$ 行、$j$ 列用于放置染色格，则内部共有 $ij$ 个格子，要求全部颜色出现的方案数为 $g_{ij}$。答案为

$$\sum_{i=0}^{n}\sum_{j=0}^{m}(-1)^{n-i+m-j}\binom ni\binom mj g_{ij}.$$

极小棋盘可以完整枚举每个格子的 $c+1$ 种状态。只有一种颜色时，也可直接对空行、空列容斥，作为独立的结构层级。

正确性证明

颜色状态动态规划中，第一项枚举“不染色或使用已出现颜色”，第二项枚举“当前格首次引入一种新颜色”，两类互斥且覆盖全部选择，所以 $g_x$ 精确统计了全部真实颜色均出现的长度为 $x$ 的状态序列。

在外层容斥中，选择被保留的行列后，只允许交叉区域的格子染色；符号恰好对应删去的空行与空列数。容斥原理保证每个至少覆盖一格的行、每列至少覆盖一格的合法方案贡献一次，而含空行或空列的方案贡献为零。内部又由 $g_{ij}$ 保证每种颜色出现，因此求和恰好是题目要求的方案数。

复杂度分析

预处理颜色状态的时间复杂度为 $O(nmc)$，外层容斥为 $O(nm)$，总时间复杂度为 $O(nmc)$，空间复杂度为 $O(nm+c)$。