[ARC145E] Adjacent XOR 题解

本文主要是介绍[ARC145E] Adjacent XOR 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

推荐在 cnblogs 上阅读。

[ARC145E] Adjacent XOR 题解

这道题真的是道神仙题，是那种考场想不出来、补题也补得十分艰难的题。可能我还是太菜了。

看了 APJ 大神的题解，琢磨很久才懂。为了帮助像我一样的同学，特地写一篇题解。

这是 2 月的第一篇题解、更是我的第一道黑题题解，谨纪念。

参考文献

[1] APJifengc，「解题报告」[ARC145E] Adjacent XOR

题意

给你 $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

#include <bits/stdc++.h>
using namespace std;#define int long longconst int MAXN = 1e3 + 5;int n;
int a[MAXN], b[MAXN], c[MAXN];
int pos[64];
vector<int> ans;struct XXJ {int d[64];  // 基底int id[64], tot;void Clear() {memset(d, 0, sizeof(d));memset(id, 0, sizeof(id));tot = 0;}bool Count(int x) {for (int i = 59; ~i; i--)if (x >> i & 1) {if (d[i] == 0)return 0;x ^= d[i];}return 1;}int Insert(int x) {int res = 0;for (int i = 60; ~i; i--)if (x >> i & 1) {if (d[i] == 0) {d[i] = x;id[i] = tot++;return res | (1ll << id[i]);}res |= (1ll << id[i]);x ^= d[i];}return res;}
} X;void work(int x) {ans.push_back(x);for (int i = 1; i <= x; i++) {b[i] ^= b[i - 1];c[i] ^= c[i - 1];}
}signed main() {scanf("%lld", &n);for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);for (int i = 1; i <= n; i++) scanf("%lld", &b[i]);for (int i = 1; i <= n; i++) {if (X.Count(a[i] ^ b[i]) == 0)return puts("No"), 0;X.Insert(b[i]);}for (int i = n; i; i--) {X.Clear();for (int j = 1; j <= i; j++) {bool flg = X.Count(b[j]);c[j] = X.Insert(b[j]);if (flg == 0)pos[__lg(c[j])] = j;}int tmp = X.Insert(a[i]);for (int j = X.tot; ~j; j--) {int sum = 0;for (int k = 1; k <= i; k++) sum ^= c[k];if ((sum >> j & 1) != (tmp >> j & 1))work(pos[j] + 1);}work(i);}reverse(ans.begin(), ans.end());printf("Yes\n%lld\n", (int)ans.size());for (int i : ans) printf("%lld ", i);return 0;
}