CF1895D题解
崔化博
·
·
题解
题解里怎么都用 trie，让我来篇不用 trie 的题解！
我们先找一下规律，容易发现只要知道了第一个数，那么后面的数就全知道了，现在的问题就是让 0- n-1 中的数全部出现。
我们设构造的数组的第一个为 k。
那么：
以此类推，所以我们发现 $b$ 中的所有数都可以表示为一个数异或上 $b_1$ 的形式。
我们发现直接考虑不太好做，于是我们考虑拆位。
如果说 $0- n-1$ 这些数中第 $j$ 位上有 $sum$ 个 1 的话，我们就必须得让 $b$ 数组最终也有 $sum$ 个 1。所以我们统计一下 $a_1,a_1 \oplus a_2,a_1 \oplus a_2 \oplus a_3...$ 中第j位上有多少个 1，如果说有 1 的个数恰好等于 $sum$，那么第一个数这位上是要填 0 的，因为 $0 \oplus 1=1$，否则就必须填1。
至于为啥有解的话我也不太会证，本来想写个判断的，结果看到题目中没说无解输出什么，就直接输出了。
参考代码实现（写的有点丑）：
```cpp
#include <bits/stdc++.h>
#define N 500005
#define M 13000005
#define mod 998244353
#define lowbit(x) (x&-x)
#define ls(x) llll[x]
#define rs(x) rrrr[x]
#define ll long long
//#define int long long
using namespace std;
int t,n;
int a[N],qian[N],b[N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=2;i<=n;++i){//让i从2开始方便一些
cin>>a[i];
qian[i]=qian[i-1]^a[i];//处理前缀异或
}
for(int j=0;j<=21;++j){
if((1<<j)>=n)continue;
int sum=0;
for(int i=0;i<n;++i){
if((i>>j)&1)++sum;
}
//统计有应该有多少个1
int sum1=0,sum2=0;
for(int i=2;i<=n;++i){
if((qian[i]>>j)&1)++sum1;
else ++sum2;
}
if(sum1==sum){//如果说1的个数和要求的一样
;//那么这位填0
}
else
b[1]+=(1<<j);//否则填1
}
ll lst=b[1];
for(int i=1;i<=n;++i){
cout<<(lst^a[i])<<' ';//最后已知第一位直接求出每一位
lst^=a[i];
}
return 0;
}
/*
k a1^k
a1^a2^k
a1^a2^a3^k
*/