P13618 题解

模拟赛考到这个题了，记录一下。

下面的 $r = 6, c = 7$，$n,m$ 表示题目中的 $r,c$。

题目里面说了任意两个 $r \times c$ 矩形内黑，白格子数量都相同。差分相邻的矩形 $(x,y),(x+1,y),(x,y+1),(x+1,y+1)$，容易发现 $a_{x,y} + a_{x + r, y + c} = a_{x, y + c} + a_{x + r, y}$。由此可以将所有位置按照横轴 $\bmod\ r$，纵轴 $\bmod\ c$ 的余数一共分为 $r \times c$ 个等价类。

我们发现一个等价类内如果出现了两个位置 $(x,y), (x + r, y)$ 满足 $a_{x,y} \ne a_{x + r, y}$ 就一定有 $a_{x,y} + a_{x + r, y + c} = a_{x,y + c} + a_{x + r, y} = 1$，则此时 $a_{x + r, y + c}$ 与 $a_{x, y + c}$ 的取值就已经固定了，另一维同理。所以对于每一个等价类，要么是每行内所有元素相同，要么是每列内所有颜色相同。因此，直接确定左上角 $r \times c$ 大小的网格就可以确定每个等价类的情况。

考虑枚举左上角 $r \times c$ 个位置的情况，从当前一行推到下一行时，我们只需要保证所有行相同的位置中 $1$ 的个数要一样多。同理推到下一列时列相同的位置中 $1$ 的数量要一样多。若有 $x$ 个行相同的位置，考虑在这里面选出所有的 $1$，因为整个矩形中一共出现 $\frac{m}{c}$ 次，所以方案数就是 $\sum_{i=0}^{x} \binom{x}{i}^{m/c}$，列的方案数同理。

但这样我们忽视了一个问题：有的等价类可能每行与每列都相同，此时会算重。考虑在行相同/列相同中容斥掉这一部分，设一开始总方案数 $f(x)$，实际上的总方案数 $g(x)$，定有 $0 \le k \le x$ 个位置对应全部相同则有 $g(x) = \sum_{k=0}^{x} (-1)^{x-k} \binom{x}{k} f(k)$。

最终答案即为每行每列方案数之积。直接枚举复杂度是 $\mathcal{O}(2^{r \times c})$ 的，无法接受。我们考虑按行转移，记录当前列相同的数量然后枚举这一行每个位置的情况，每行填完再乘上这一行对应的行的方案数，可以做到 $\mathcal{O}(r \times (2r)^{c})$，常数相当小可以通过。