[题解] 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}。

这样我们就得到了转移：

\begin{aligned} f_{i, j} &= \sum_{1 \le x \le i} (-1)^{x+1} \binom{i}{x}C^{x} f_{i - x, j} \\ &+ \sum_{1 \le y \le j} (-1)^{y + 1} \binom{j}{y} C^{y} f_{i, j - y} \\ &+ \sum_{1 \le x \le i} \sum_{1 \le y \le j} (-1)^{x + y + 1} \binom{i}{x} \binom{j}{y} C f_{i - x, j - y} \end{aligned}

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

ans = \sum_{1 \le i \le n} \sum_{1 \le j \le m} (-1)^{i + j} \binom{n}{i} \binom{m}{j} C f_{n - i, m - j}

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

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

\sum_{1 \le x \le i} \sum_{1 \le y \le j} (-1)^{x +y +1} \binom{i}{x} \binom{j}{y} Cf_{i - x, j - y}

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

\begin{aligned} f_{i, j} &= \sum_{1 \le x \le i} (-1)^{x+1} \binom{i}{x}C^{x} f_{i - x, j} \\ &+ \sum_{1 \le y \le j} (-1)^{y + 1} \binom{j}{y} C^{y} f_{i, j - y} \\ &+ \sum_{1 \le x \le i} (-1)^x \binom{i}{x} C g_{i - x, j} \\ g_{i, j} &= \sum_{1 \le y \le j} \binom{j}{y} (-1)^{y + 1} f_{i, j - y} \end{aligned}

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

代码。