专题训练 - 构造 III

[CF1451E2] Bitwise Queries (Hard Version)

首先使用 $n-1$ 次操作询问出 $a_1\oplus a_i(2\le i\le n)$，然后我们只需要求出某一个 $a_i$ 就可以求出整个序列了。

由于 x\or y=x\oplus y\oplus(x\and y)，事实上此时已经可以求出任意两个 $a_i,a_j$ 的异或和，所以我们可以只考虑 \and。

下面假设你询问了 a_i\and a_j，下一次再询问，不可能是另外两个完全不同的位置。这是因为目前为止我们已知的所有信息都是对称的，对称的话就势必不能解出唯一解，除非你解出来的两个解是相等的，显然数据并不能保证这一点。

不妨设已知 a_i\and a_j 与 a_j\and a_k，其中 $i,j,k$ 两两不同，接下来我们考虑某个二进制位的情况。

1. 若 a_i\and a_j=1 或者 a_j\and a_k=1，那么 $a_j=1$。
2. 否则，若 $a_i\oplus a_j=0$ 或者 $a_j\oplus a_k=0$，那么 $a_j=0$。
3. 否则，此时我们可以推出 $\{a_i,a_j\}=\{a_j,a_k\}=\{0,1\}$，枚举不难发现只能是 $(a_i,a_j,a_k)=(0,1,0)$ 或 $(1,0,1)$。

我们会发现，最后的情况是无法确定出来到底是哪一种的。如果是 Easy Version 允许询问 $n+2$ 次，只要询问 a_i\and a_k 就好了。

那么，我们如何省掉这一次询问？这就必然和题目保证的特殊数据范围有关系了。

不难发现取值范围 $0\sim n-1$ 有 $n$ 个不同的数，所以如果 $a_1\sim a_n$ 两两不同，那么它们一定是 $0\sim n-1$ 的一个排列。

在考虑这种特殊的情况之前，我们先来看如果存在两个相同的元素该怎么办。

1. 如果存在某个 $a_i,i=2\sim k$ 满足 $a_1=a_i$，这等价于 $a_1\oplus a_i=0$；
2. 如果存在某对 $2\le i,j\le k,i\neq j$ 满足 $a_i=a_j$，这等价于 $a_1\oplus a_i=a_1\oplus a_j$。

如果存在这样的情况，我们只需要问这两个位置的 \and 或者 \or，就可以求出这个位置的取值，然后解出每一个值了。

好，下面再看 $a_1\sim a_n$ 组成 $0\sim n-1$ 的排列这一情况。由于 $n$ 是 $2$ 的幂，所以任意两个 $0\sim n-1$ 的数异或起来仍然在 $0\sim n-1$ 中，因此 $a_1\oplus a_2\sim a_1\oplus a_n$ 一定是 $1\sim n-1$ 的一个排列（如果有 $0$ 是上一种情况）。

那么就必然存在一个 $a_k$ 使得 $a_1\oplus a_k=n-1$。这有什么特殊的？因为这两个数异或起来二进制全 $1$，那么它们不可能有两个位置都是 $1$，于是 a_1\and a_k=0，这就可以帮我们省掉一次询问。

AC Code。