CF2131E Adjacent XOR

题意简述

给定一个长度为 $n$ 的数组 $a$。对于每一个满足 $1 \leq i < n$ 的下标 $i$，你可以最多执行一次如下操作：

将 $ai := a_i \oplus a{i+1}$，其中 $\oplus$ 表示按位异或运算。

你可以以任意顺序选择下标并依次执行这些操作。

现在给定另一个长度为 $n$ 的数组 $b$，请判断是否有可能将 $a$ 转换为 $b$。

思路分析

1400 分题。本来也不值得记的。

结论是：当满足下列三个条件之一时，有可能将 $a$ 转换为 $b$.

1. $a_i = b_i$
2. $ai \oplus b_i = a{i+1}(i \lt n)$
3. $ai \oplus b_i = b{i+1}(i \lt n)$

对任意 $i<n$，整个过程中 $a_{i+1}$ 最多只会处于两种稳定取值之一：

$$\text{init}(i{+}1)=a_{i+1},\qquad \text{final}(i{+}1)=b_{i+1}.$$

理由：只有操作 $i{+}1$ 会改 $a{i+1}$，且每个位置至多操作一次；所以 $a{i+1}$ 要么一直没变（等于初值），要么在某一时刻被更新一次，之后保持为其最终目标值（若最终能达成 $b$，这个最终值就应是 $b{i+1}$）。在你执行操作 $i$ 的那个瞬间，作为操作数出现的 $a{i+1}$ 只可能是这两者之一。

据此，操作 $i$ 的所有可能结果仅有三种：

$$\underbrace{a_i}_{\text{不做}} \quad\text{或}\quad \underbrace{a_i\oplus \text{init}(i{+}1)=a_i\oplus a_{i+1}}_{\text{在改 }i{+}1\text{ 之前做}} \quad\text{或}\quad \underbrace{a_i\oplus \text{final}(i{+}1)=a_i\oplus b_{i+1}}_{\text{在把 }i{+}1\text{ 变成 }b_{i+1}\text{ 之后做}}.$$

于是得到必要条件（$i<n$）：

$$b_i \in \{\,a_i,\ a_i\oplus a_{i+1},\ a_i\oplus b_{i+1}\,\},$$

等价写法：

$$a_i\oplus b_i \in \{\,0,\ a_{i+1},\ b_{i+1}\,\}.$$

边界 $i=n$ 只能是 $b_n=a_n$。