P9887 [ICPC 2018 Qingdao R] Flippy Sequence

DreamGrid 刚刚从他的虚拟机中找到了两个二进制序列 $s_1, s_2, \dots, s_n$ 和 $t_1, t_2, \dots, t_n$（对于所有 $1 \le i \le n$，$s_i, t_i \in \{0, 1\}$）！他想要执行下面描述的操作恰好两次，使得在两次操作后，对于所有 $1 \le i \le n$，都有 $s_i = t_i$。 操作是：选择两个整数 $l$ 和 $r$（$1 \le l \le r \le n$），将所有 $l \le i \le r$ 的 $s_i$ 变为 $(1 - s_i)$。 DreamGrid 想知道有多少种方法可以做到这一点。 我们使用以下规则来确定两种方法是否不同： - 设 $A = (a_1, a_2, a_3, a_4)$，其中 $1 \le a_1 \le a_2 \le n, 1 \le a_3 \le a_4 \le n$，表示 DreamGrid 为第一次操作选择整数 $a_1$ 和 $a_2$，为第二次操作选择整数 $a_3$ 和 $a_4$； - 设 $B = (b_1, b_2, b_3, b_4)$，其中 $1 \le b_1 \le b_2 \le n, 1 \le b_3 \le b_4 \le n$，表示 DreamGrid 为第一次操作选择整数 $b_1$ 和 $b_2$，为第二次操作选择整数 $b_3$ 和 $b_4$。 - 如果存在整数 $k$（$1 \le k \le 4$）使得 $a_k e b_k$，则 $A$ 和 $B$ 被认为是不同的。

无

无

对于第二个样例测试用例，有两个有效的操作对：$(1, 1, 2, 2)$ 和 $(2, 2, 1, 1)$。 对于第三个样例测试用例，有六个有效的操作对：$(2, 3, 5, 5)$，$(5, 5, 2, 3)$，$(2, 5, 4, 4)$，$(4, 4, 2, 5)$，$(2, 4, 4, 5)$ 和 $(4, 5, 2, 4)$。 题面翻译由 ChatGPT-4o 提供。