[ARC145E] Adjacent XOR 题解
这道题真的是道神仙题，是那种考场想不出来、补题也补得十分艰难的题。可能我还是太菜了。
看了 APJ 大神的题解，琢磨很久才懂。为了帮助像我一样的同学，特地写一篇题解。
这是 2 月的第一篇题解、更是我的第一道黑题题解，谨纪念。
参考文献
题意
给你 $n$ 个整数 $a_1,a_2,\dots,a_n$，再给你 $n$ 个整数 $b_1,b_2,\dots,b_n$。通过执行以下操作，问你能不能操作 $70000$ 次以内使得 $a$ 与 $b$ 相同。
- 操作：选择整数 $k\in[1,n]$，进行 $a_i\leftarrow a_{i-1}\oplus a_i$，$i\in[2,k]$ 的赋值操作。
数据范围：$2\le n\le 1000$，$0\le a_i,b_i \lt 2^{60}$。
Solution
转化目标
题意清晰，就是告诉你要构造方案。
由于每一次操作都是 $a_i\leftarrow a_{i-1}\oplus a_i$，这个及其难下手。不妨反过来，从 $b$ 入手。
在此之前，先琢磨透这个在 $a$ 上做手脚的操作，到底是个啥？
其实一次操作，钦定 $k$ 以后，就是去把每一个在 $[2,k]$ 的 $a_i$ 都赋值为原 $a$ 数组下标从 $1\sim i-1$ 的异或和。
而我们对 $a_i$ 做手脚，是因为我们期望得到 $b_i$。这个对 $a$ 数组的操作，每次都依靠前缀。
形式化地，这样：
$$ b_1=a'_1=a_1\\b_2=a'_2=a_1\oplus a_2\\b_3=a'_3=a_1\oplus a_2\oplus a_3\\\dots\\b_i=a'_i=\oplus_{j=1}^i a_j $$现在考虑从 $b$ 入手，从而推出 $a$。那么题意变为：
选择 $k\in[1,n]$，进行 $b_i=\oplus_{j=1}^i b_j$，$i\in[1,k]$ 的赋值操作。
为什么这样得到的 $b_i$ 会等于 $a_i$ 呢？展开一下就明白了：
$$ b'_1=b_1\\b'_2=b'_1\oplus b_2\\b'_3=b'_1\oplus b'_2\oplus b_3 $$如果一项一项带入，就会发现 $b'_{i}=b_{i-1}\oplus b_i$。
又把 $b_i$ 用 $a_i$ 表示，可以得到 $b'_{i}=(a_1\oplus\dots\oplus a_{i-1})\oplus (a_1\oplus \dots \oplus a_i)=a_i$。
至此，题意与解题目标发生了转化、也更加清晰。
能否构造
观察一手数据范围，可以跑 $n\log b$。考虑对于每个 $i$，就用 $O(\log b)$ 构造出一个 $a_i$。这里为了防止前缀和影响已更新好的数，我们选择倒着构造。
先判断能否构造，不难想到，可以构造的充要条件是：每一个 $a_i$ 都可以由 $b_{[1,i-1]}$ 中的若干数与 $b_i$ 异或得到。
构造开始
这个 $b$ 数组，不是个善茬，想不到怎么很好处理。思考一下 $b$ 数组需要做的操作，都是它的线性基可以处理的（其实看到异或问题，多多少少要想到一点线性基）。
我们把基底按先后加入顺序标号，来表示 $b$ 的每一个数。此刻来考虑这个新数组 $c$。
我们想从 $a_n\sim a_1$ 进行构造，如果我们此时构造 $a_i$，那么我们不能动 $a_k$，$k\in[i+1,n]$；否则就打乱了。
所以，当我们改变到第 $i$ 位的时候，只能对 $k=i$ 进行操作：$b_i\leftarrow \oplus_{j=1}^ib_j$。实际上，就是构造异或和等于 $a_i$。
我们按加入的先后顺序标号，所以当第 $i$ 位最早在 $pos_i$ 出现时，在 $[1,pos_i-1]$ 中 $i$ 这一位都为零。这个很显然。
那得知这个有什么用呢？我们可以通过这个将前缀异或和进行某一位的翻转。既然 $pos_i$ 是第一次出现 $i$，那如果我对 $k=pos_i+1$ 进行操作，只有 $b_{pos_i+1}$ 的异或和多了 $i$ 这一位，总异或和这一位也就可以翻转了。
也是从大到小考虑，$pos_i$ 递减，不会影响之前的数。
构造总结
那现在构造方法就很明了了：
- 从大到小枚举 $i$，计算当前异或和。
- 当异或和与 $a_i$ （重标号后的）某一位不一样，就对那一位进行翻转操作。
- 最后对 $k=m$ 进行操作，即可得出 $a_m$。
- 重复 $n$ 遍，最后把操作序列翻转，就是从 $a$ 到 $b$ 的操作了。
代码
code
|
|