CF1906B Button Pressing

题目链接：https://codeforces.com/problemset/problem/1906/B

题意简述

有 $n$ 盏灯，用一个 $0/1$ 序列代表关闭/打开的状态。若第 $i$ 盏灯处于打开的状态，允许对其执行如下的操作：

同时翻转第 $i-1$ 盏（若 $i$ 不为 $1$）和第 $i+1$ 盏（若 $i$ 不为 $n$）灯。

给定两个状态，求是否能从第一个到达第二个状态。

碎碎念（不重要）

看到这题一开始还以为有点思路，结果想了半天还是不会，于是只能看答案了。

首先，操作不会改变第 $i$ 盏灯本身的状态，故一个操作序列永远是可逆的，即可达是等价关系。

之后我手玩了 $n=2 - 4$ 的等价类，感觉有些特殊的性质，结果就陷入打表的泥潭里了，最后也没看出什么头绪。

解法（官解）

结果官解特别的简单。考虑前缀和数组 $s_i = \oplus_{1 \le j \le i} a_j$ ，则一次操作i对应将其中两相邻的不同数交换：

$a_i = 1 \Rightarrow s_{i-1}$ 与 $s_i$ 不同；
将 $a_{i-1}$ 与 $a_{i+1}$ 均翻转 $\Rightarrow$ 将 $s_{i-1}$ 与 $s_i$ 均翻转；由于它们不同，这等价于将它们交换。

这样我们总能将所有的 $1$ 聚到一起，因此两个状态在前缀和数组中 $1$ 的个数相等时等价。

但还要注意一个例外情况：$i=1$。此时，不存在 $s_{i-1}$，操作等价于翻转 $2-n$ 的所有前缀和。这将前缀和中1的个数 $c$ 变为 $1 + (n - 1 - (c - 1)) = n + 1 - c$。

因此两个状态当前缀和数组中 $1$ 的个数相等，或前缀和数组中1的个数之和为 $n+1$。

注意还有一个例外情况，就是前缀和数组中全为 $0$（即 $a$ 为全 $0$ 数组），但此时无法进行任何操作，也不存在“前缀和数组中 $1$ 的个数之和为 $n+1$”的情况，故不需要特殊判断。

代码实现（Kotlin）

fun f(s: String): Int {
    return s.scan(0) { x, c -> x xor (c - '0') }.sum()
}

fun main() {
    val tc = readln().toInt()
    repeat(tc) {
        val n = readln().toInt()
        val (a, b) = readln() to readln()
        val (x, y) = f(a) to f(b)
        println(if (x == y || x + y == n + 1) "YES" else "NO")
    }
}