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。