526互联

Educational Codeforces Round 157 (Rated for Div. 2)

发布时间 2023-11-30 00:45:27作者: Qiansui

目录

Educational Codeforces Round 157 (Rated for Div. 2)

D. XOR Construction

方法一：
由题得 $ b_{i + 1} = a_i \oplus b_i = \cdots = b_1 \oplus a_1 \oplus a_2 \oplus a_3 \cdots \oplus a_i $
所以对于对于给定得 a 数组求一个前缀的异或和，那么 $ b_{i + 1} = a_i \oplus b_1 $
那么我们只要确定了 \(b_1\)，就确定了待求整个数组。剩下的问题就是怎么快速的找

const int N = 2e5 + 5, M = 20, inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f, mod = 998244353;

int idx = 0, tree[N << 1][2];//应当从高位存到低位！
void insert(int x){
	int p = 0;
	for(int j = M; j >= 0; -- j){
		int d = x >> j & 1;
		if(!tree[p][d]) tree[p][d] = ++ idx;
		p = tree[p][d];
	}
	return ;
}

bool query(int x, int n){
	int p = 0, mx = 0;
	for(int j = M; j >= 0; -- j){
		int d = x >> j & 1;
		if(tree[p][1 - d]){
			mx |= (1 << j);
			p = tree[p][1 - d];
		}else if(tree[p][d]) p = tree[p][d];
		else return false;
	}
	return (mx == n - 1);
}

void solve(){
	int n, x;
	cin >> n;
	vector<int> a(n, 0);
	for(int i = 1; i < n; ++ i){
		cin >> a[i];
		a[i] ^= a[i - 1];
		insert(a[i]);
	}
	x = n - 1;
	for(int i = 0; i < n; ++ i){
		if(query(i, n)){
			x = i;
			break;
		}
	}
	for(int i = 0; i < n; ++ i)
		cout << (x ^ a[i]) << ' ';
	return ;
}