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

注意到

题目要求对 $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$ 的情况，最后结果自然去重。