思路显然，代码显然，然后没了

注意到

题目要求对 $n \times m$ 的棋盘染色，使得每个长宽都为偶数的矩形中红色和蓝色数量相同。

显然

一个长宽均为偶数的矩形可以被划分为若干个 $2 \times 2$ 的小矩形。如果每个 $2 \times 2$ 的子矩形都满足红蓝各半（即 2 红 2 蓝），那么任意偶数长宽的矩形也必然满足条件。 反之，如果存在某个 $2 \times 2$ 不满足，则条件不成立。 因此，原条件等价于：棋盘中任意 $2 \times 2$ 的子矩形恰好包含 2 个红色和 2 个蓝色。

数学推导

设 $a_{i,j} \in \{0, 1\}$ 表示格子 $(i, j)$ 的颜色。 $2 \times 2$ 子矩形红蓝各半 $\iff a_{i,j} + a_{i,j+1} + a_{i+1,j} + a_{i+1,j+1} = 2$。 这等价于两个条件：

1. 异或和为 0：$a_{i,j} \oplus a_{i,j+1} \oplus a_{i+1,j} \oplus a_{i+1,j+1} = 0$
2. 不全相同：不能全为 0 或全为 1。

由条件 1 可得 $a_{i,j} \oplus a_{i,j+1} = a_{i+1,j} \oplus a_{i+1,j+1}$，即行的差分与行号无关。 设 $d_j = a_{i,j} \oplus a_{i,j+1}$，则 $a_{i,j}$ 可以表示为：

其中 $r_i = a_{i,0}$，$c_j = d_0 \oplus d_1 \oplus \dots \oplus d_{j-1}$（$c_0 = 0$）。

代入条件 2，对于任意 $2 \times 2$ 子矩形：

• 若 $c_j = c_{j+1}$，则四个值为 $x, x, y, y$。和为 2 $\implies x \neq y \implies r_i \neq r_{i+1}$。
• 若 $c_j \neq c_{j+1}$，则四个值为 $x, 1-x, y, 1-y$。和恒为 2。

结论： 合法棋盘必须满足以下两个条件之一（或同时满足）：

• 集合 A：$c$ 严格交替（即 $c_j \neq c_{j+1}$ 对所有 $j$ 成立）。此时 $r$ 可任意。
• 集合 B：$r$ 严格交替（即 $r_i \neq r_{i+1}$ 对所有 $i$ 成立）。此时 $c$ 可任意。

根据容斥原理，合法方案数 $= |A| + |B| - |A \cap B|$。

注意等价性： $(r, c)$ 和 $(\bar{r}, \bar{c})$（即所有 $r_i, c_j$ 取反）会产生完全相同的棋盘 $a_{i,j}$。因此在计算 $|A|$ 和 $|B|$ 时，我们只计算 $c_0=0$ 和 $r_0=0$ 的情况，最后结果自然去重。

color

有一个矩阵 $A$ 长 $n$，宽 $m$。矩阵中部分值 $A_{i, j}$ 确定为 $0$ 或 $1$。计算满足条件的矩阵个数。

• 原来确定的值，不能改动。矩阵的元素是 $0/1$。

• 有 $\forall (x_1, y_1, x_2, y_2), x_1 \le x_2,y_1\le y_2 , (x_2-x_1)\bmod 2 = (y_2 - y_1) \bmod 2 =0$ ，满足： $\sum\limits_{i\in [x_1, x_2]}({\sum\limits_{j \in [y_1, y_2]}{A_{i, j}} )} = (x_2 - x_1)(y_2 - y_1) / 2$。

计算这样的矩阵 $A$ 的个数。

不难发现，考虑全都是 ?。确定第一行的点的值。

• 如果 $\exist i \in [1, m), A_{1, i} = A_{1, i+1}$，那么整个 $A$ 就确定了。且对于 $A_{i, j} =A_{1, j}, i \equiv 1 \pmod 2$，否则 $A_{i, j} = 1-A_{1, j}$。

• 否则，则每一行的选择是独立的，均只能 010101010 或者 101010101010 的形式。

所以原问题做完。

对于一般情况， $A_{i, j} = 0/1$。

可以钦定第一行是否存在相邻相同字符？

如果存在，每个 $A_{i, j} = c$ 相当于确定了 $A_{1, j}$ 就确定了，因为 $A_{i, j} = 1-A_{i+1, j}$。

如果不存在，那不更简单，直接代入即可。

对于每一行 $i$，记 $D_{i, 0/1}$ 表示第 $i$ 行能否变成 0101010101（0 表示），10101010（1 表示），答案就是 $\Pi_{i\in[1, n]}({D_{i, 0} + D_{i,1}})$

666，特殊性质出来了不直接秒了吗？？写不出来的直接 AFO。