[题解] ARC193C Grid Coloring 3

时光倒流，判定是第一次删一个同色的十字，之后每次可以删同色的行、列、十字，能删空就合法。

记 $f_{i, j}$ 表示 $i$ 行 $j$ 列的网格中，能通过删同色的行、列、十字删空的个数。

转移时找到同色的位置集合，随便删一个的话会算重，考虑每次钦定一个子集并删掉，容斥计算答案。

对于一个网格，有两种情况：同色位置的集合中只有行或只有列、同色位置的集合中同时有行和列。

对于同色位置的集合中恰好只有 $k$ 行的情况，钦定 $j$ 行同色，那么要求 $\displaystyle \sum_{1 \le j \le k} \binom{k}{j} c_j = 1$，不难得到容斥系数 $c_j = (-1)^{j + 1}$。列的情况是相同的。

对于同色位置的集合中恰好有 $i$ 行 $j$ 列的情况，在只钦定行和只钦定列的时候已经被算了两次，所以我们需要在同时钦定行列的时候让它的贡献为 $-1$。

钦定 $x$ 行 $y$ 列同色，那么就是要求 $\displaystyle \sum_{1 \le x \le i} \sum_{1 \le y \le j} \binom{i}{x} \binom{j}{y} c_{x, y} = -1$，可以得到 $c_{x, y} = (-1)^{x + y + 1}$。

这样我们就得到了转移：

统计答案就是上面的第三种情况要求贡献为 $1$，所以令容斥系数 $c_{x, y} = (-1)^{x + y}$ 即可得到：

这样就得到了 $O(n^4)$ 的做法。

瓶颈在于同时钦定行列的情况的转移，也就是计算：

记 $\displaystyle g_{i, j} = \sum_{1 \le y \le j} \binom{j}{y} (-1)^{y + 1} f_{i, j - y}$，那么转移就变成了：

这样就做到了 $O(n^3)$。

代码。