题目内容

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

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

解题思路

可达性分析

由于允许任意次相邻格子间交换“0”和“1”，且“1”们不可区分，只要保持“1”的总数 $K$ 不变，就能把这 $K$ 个“1”放到任意 $K$ 个格子上。因此，可达的所有状态就是：在 $N=n\times m$ 个格子中任取 $K$ 个位置放“1”。

奇偶性判定

定义权值

$W=\frac12\sum_{u\sim v}|x_u-x_v|.$