CF1895D 题解

_sunkuangzheng_ · 2023-11-04 07:18:36 · 题解

当 b_1 确定时，b_2 \sim b_n 都是已经确定的。

你只需要关心 b 的最大值。

由题目中的式子可知，b_2 = b_1 \oplus a_1,b_3 = b_2 \oplus a_2,\ldots，当 b_1 确定时，整个 b 数组都已经确定。

设 c 是 a 的前缀异或和数组，我们合并前缀式子，得到 b_i = b_1 \oplus c_{i-1}。显然的，如果存在 i,j(i \ne j) 使得 c_i = c_j，那么必然无解。而题目保证有解，即 c 数组互不相同且 c_i \ne 0，也即对于任何 b_1 都满足 b 所有元素互不相同，我们只需要考虑 b_i \le n-1 这一限制。

我们发现所有 b_i \le n-1 等价于 \max\{b_i\} \le n-1，因此你只需要枚举 b_1 的值，将 c_1 \sim c_{n-1} 插进 01-trie，每次查询 b_1 \oplus c_i 的最大值即可。时间复杂度 \mathcal O(n \log V)。

/**
 *    author: sunkuangzheng
 *    created: 03.11.2023 23:00:09
**/
#include<bits/stdc++.h>
using namespace std;
const int N = 6e6+5;
int t,n,ch[N][2],tot,val[N],a[N],b[N],ans;
void ins(int x){
    int s = 0;
    for(int i = 22;i >= 0;i --){
        val[s] ++;
        if(!ch[s][(x >> i) & 1]) ch[s][(x >> i) & 1] = ++tot;
        s = ch[s][(x >> i) & 1];
    }val[s] ++;
}int qry(int x){
    int s = 0,ans = 0;
    for(int i = 22;i >= 0;i --){
        int k = (x >> i) & 1;
        if(ch[s][!k]) s = ch[s][!k],ans += (1 << i);
        else s = ch[s][k];
    }return ans;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> n;
    for(int i = 1;i < n;i ++) cin >> a[i],b[i] = a[i] ^ b[i-1],ins(b[i]);
    for(int i = 0;i < n;i ++) if(qry(i) < n) {ans = i;break;}
    cout << ans << " ";
    for(int i = 1;i < n;i ++) cout << (ans ^ b[i]) << " ";
}