题解

思路

令 $X$ 表示当前格子序列，并定义边界序列 $Y_i=X_i\oplus X_{i+1}$。

做法

初始的 $Y$ 全为 $1$；一次操作恰好选择形如 $1,0,\ldots,0,1$ 的一段，把两端的 $1$ 变成 $0$。第一个格子的值始终为 $1$，所以若 $A_1=0$，答案为零。否则目标边界序列为 $B_i=A_i\oplus A_{i+1}$。

考察 $B$ 中每一段连续的零。若某段长度 $x$ 为奇数，它不可能由成对消去的边界得到。若 $x=2m$，完成该段需要 $m$ 次操作，段内操作顺序共有 $(2m-1)!!$ 种。不同零段彼此独立，但它们的操作可以任意交错；若各段对应 $m_1,m_2,\ldots,m_k$，交错数为 $(\sum m_i)!/\prod m_i!$。

复杂度

因此答案为

预处理阶乘、逆阶乘和奇数双阶乘后线性扫描即可，总复杂度为 $O(N)$，空间复杂度为 $O(N)$。