CF1895D

发布时间 2023-11-09 09:43:42作者: carp_oier

analysis

看到这个类似差分的样子,想着对它进行转化,通过对题目给出的式子进行变形,我们可以得到下面的式子。

\[a_i = b_i \bigoplus b _ {i + 1} \]

\[\begin{aligned} b_{i+ 1} &= b_i \bigoplus a_i \\ &= b_ {i - 1} \bigoplus a_{i - 1} \bigoplus a_i \\ &= (\bigoplus_{j = 1}^{i} a_j) \bigoplus b_1 \end{aligned} \]

\(c_i\)\(\bigoplus _ {j = 1}^{i} a_j\)

得到原式:\(b_i = c_{i - 1} \bigoplus b_1\)

所以我们要关心的只有 \(b_1\) 这一个值。然后我们可以想到要维护异或最大值,不难想到用 01-trie 解决它。

code time

flush 是因为我用的快读快写中的 getchar 和 putchar 是自己手写的,所以有这个函数,大家可以直接忽略。(想了想还是得放一下我这 for 家族,不然看不懂/lh)

#define ll long long
#define rl register ll
#define fom(i, a) for(rl i=a; i; -- i)
#define foa(i, a, b) for(rl i=a; i < b; ++ i)
#define fos(i, a, b) for(rl i=a; i <= b; ++ i)
#define fop(i, a, b) for(rl i=a; i >= b; -- i) 

const ll N = 2e6 + 10;

ll n, idx, tr[2][N], a[N], s[N];

inline void insert(ll x)
{
    ll p = 0;
    fop(i, 30, 0)
    {
        bool u = x & (1 << i);
        if(!tr[u][p]) tr[u][p] = ++ idx;
        p = tr[u][p];
    }
}

inline ll check(ll x)
{
    ll p = 0, res = 0;
    fop(i, 30, 0)
    {
        bool u = x & (1 << i);
        if(tr[!u][p]) res |= (1 << i), p = tr[!u][p]; else p = tr[u][p];
    }
    return res;
}

int main()
{
   // freopen("1.in", "r", stdin); 
    read(n); insert(0); foa(i, 1, n) read(a[i]); foa(i, 1, n) s[i] = s[i - 1] ^ a[i], insert(s[i]);
    foa(i, 0, n) if(check(i) < n) { ww(i), ws; foa(j, 1, n) ww(i ^ s[j]), ws; return flush(), 0; }
    return flush(), 0;
}