题解

思路

记一块砖左边中点是否接有线段为一个二进制量。

做法

沿一行移动时，遇到 A 会翻转这个量，遇到 B 则保持不变，因此选定每行最左侧的状态后整行唯一确定；环形闭合要求每行 A 的数量为偶数。对列方向同理，每列 A 的数量也必须为偶数。

为每行设置变量 $R_i$，为每列设置变量 $C_j$。设走到格子 $(i,j)$ 前，该行与该列已经经过的 A 数量奇偶分别为 $p_{i,j},q_{i,j}$。A 型砖在横、纵方向各恰有一个端点，自动合法；B 型砖必须在横向与纵向中恰选一个方向，所以给出异或约束 $R_i\oplus C_j=1\oplus p_{i,j}\oplus q_{i,j}$。用带权并查集合并所有 B 格子的约束，若出现矛盾或某行某列的 A 数量为奇数，答案为零；否则每个连通分量可任选一个根变量，答案就是 $2$ 的连通分量数次幂。

复杂度

总复杂度为 $O(HW\alpha(H+W))$，空间复杂度为 $O(H+W)$。