题解
题目描述
给定一个 n 行 m 列的棋盘（每个格子值为 0 或 1），用 (i,j) 表示第 i 行第 j 列的格子。允许的操作是任意次选择两个相邻格子（上下或左右）并交换它们的值。定义格子的活跃度为该格子与相邻格子中数值不同的个数，整个棋盘的总活跃度为所有格子活跃度之和。如果一个棋盘的总活跃度是偶数，就称它为「平衡棋盘」。给定初始棋盘，问在经过任意次上述操作后，能够得到多少种不同的平衡棋盘的配置数。结果对 109+7 取模。
思路
- 可达状态分析
题目内容
有一个 n 行 m 列的方格棋盘，第 i 行第 j 列的格子记为 (i,j)。每个格子里要么放着白子（用 0 表示），要么放着黑子（用 1 表示）。
你可以进行任意次操作：每次选择两个有一条公共边的相邻格子，交换它们里面的棋子。操作不能越过棋盘边界。
对于一种棋盘状态，我们定义每个格子的「活跃度」为：与该格子相邻且棋子颜色不同的格子个数。整个棋盘的「总活跃度」则为所有格子活跃度之和。
如果一个棋盘的总活跃度是偶数，就称它为「平衡棋盘」。
现在给定初始棋盘，请问经过任意次操作后，能够得到多少种不同的平衡棋盘？两个棋盘只要存在某个相同位置上的棋子颜色不同，就视为不同的棋盘。
