题解

思路

把能够被同一次操作同时标记的两条边连起来，所有网格边会沿对角方向分成若干互不影响的链。

做法

对一条含 $k$ 条边的链，可得到的标记集合等价于在路径上选择若干互不相邻的二元组。设其方案数为 $a_k$，按最左边是否被标记分类可得 $a_0=a_1=1$、$a_k=a_{k-1}+a_{k-2}$。

令 $n=\min(H,W)$、$m=|H-W|$。整理所有链的长度后，答案为 $(a_2a_4\cdots a_{2n})^2a_{2n+1}^{m}$。预处理斐波那契型数列 $a_i$，再预处理偶数下标的前缀乘积 $b_n=\prod_{i=1}^{n}a_{2i}$；每组询问输出 $b_n^2a_{2n+1}^{m}$，幂用快速幂计算。

复杂度

预处理复杂度为 $O(\max(H,W))$，每组询问复杂度为 $O(\log|H-W|)$，空间复杂度为 $O(\max(H,W))$。