题目内容

有一个 $n$ 行 $m$ 列的网格，我们使用 $(i,j)$ 表示网格中从上往下数第 $i$ 行和从左往右数第 $j$ 列的单元格。每个方格的值为 $0$ 或 $1$ ，且任何操作均不得超出网格边界。

我们定义单元格的权值为该单元格与其相邻且数值不同的单元格个数。网格的奇偶性为所有单元格权值之和的奇偶性。

$Tk$ 可以任意次进行如下操作：

题解

题目描述

给定一个 $n$ 行 $m$ 列的二元网格（每个格子值为 $0$ 或 $1$），用 $(i,j)$ 表示第 $i$ 行第 $j$ 列的格子。允许的操作是任意次选择两个相邻格子（上下或左右）并交换它们的值。定义格子的权值为该格子与相邻格子中数值不同的个数，网格的奇偶性为所有格子权值之和的奇偶性。给定初始网格，问在经过任意次上述操作后，能够得到多少种不同的偶网格（即权值和为偶数的网格）的配置数。结果对 $10^9+7$ 取模。

思路

1. 可达状态分析
   网格连通且只允许相邻格子交换，交换操作可在连通图上生成对所有格子值的任意排列。因此，所有与初始网格拥有相同的 $1$ 的个数 $k$ 的二元矩阵均可达到。