题目分析

首先，我们要知道一个基本的定理：

$$k \oplus k=0$$

这是因为异或相同为 $0$，不同为 $1$。所以两个相同的数异或的值为 $0$。

知道了这个之后，我们就可以把题目中的式子全部都异或起来，变成这样：

$$\overbrace{(a_1\oplus a_1\oplus \ldots \oplus a_1)}^{n-1}\oplus \overbrace{(a_2\oplus a_2\oplus \ldots \oplus a_2)}^{n-1}\oplus \ldots \oplus \overbrace{(a_n\oplus a_n\oplus \ldots \oplus a_n)}^{n-1}=b_1\oplus b_2\oplus \ldots\oplus b_n $$

因为 $n$ 是偶数，所以可以化简成：

$$a_1\oplus a_2\oplus \ldots \oplus a_n=b_1\oplus b_2\oplus \ldots \oplus b_n $$

我们令 $b_1\oplus b_2\oplus \ldots \oplus b_n$ 为 $x$，则：

$$a_1\oplus a_2\oplus \ldots \oplus a_n=x$$

把这个式子和题目中第一个式子异或，得：

$$a_1\oplus (a_2\oplus a_2)\oplus (a_3\oplus a_3)\oplus \ldots \oplus (a_n\oplus a_n)=x\oplus b_1 $$

化简一下，得：

$$a_1=x\oplus b_1$$

同理可证，$a_i=x\oplus b_i$。

于是，我们就可以得出答案了。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int a[200100];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,k=0;
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		cin>>a[i];
		k^=a[i];
	}
	for (int i=1;i<=n;i++)
		cout<<(k^a[i])<<' ';
	return 0;
}

更好的阅读体验

题目翻译

给出有 $n$ 个数的序列 $b$，还原序列 $a$，使 $a_i$ 为除 $b_i$ 以外所有数的异或和。 $2\leq n\leq 2\times 10^6,0\leq a_i\leq 10^9$。 $n\equiv0\pmod{2}$。

题目思路

前置知识：异或的归零律、恒等律与自反 $a\oplus a=0,a\oplus 0=a,a\oplus b\oplus a=b$。

观察题意可得我们求出的 $a_i$ 即为 $b_1\oplus b_2\oplus \dots \oplus b_n$ 再去除一个 $b_i$。

设 $b_1\oplus b_2\oplus \dots \oplus b_n=k$。

我们根据异或的自反可得：

$$\begin{aligned}k\oplus b_i&=b_1\oplus b_2\oplus \dots \oplus b_n\oplus b_i\\&=b_1\oplus b_2\oplus\dots\oplus b_{i-1}\oplus b_{i+1}\oplus b_{i+2}\oplus \dots \oplus b_n\end{aligned} $$

于是我们得到了想求的 $a$ 数组。

完整代码

#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[200020];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        k^=a[i];
    }
    for(int i=1;i<=n;i++)
    {
        cout<<(k^a[i])<<" \n"[i==n];
    }
    return 0;
}