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;
}