选数 题解
首先，设最初取值为\(x\)，按照套路，我们设异或前缀和：\(pre_i=a_1\oplus a_2…\oplus a_i\)，设\(f(x)=\left(\left\lfloor\frac{2x}{2^n}\right\rfloor+2x\right)\bmod 2^n\)
注意到：\(0\le a_i<2^n\)，也即其二进制下不会超过\(n\)位。
那么我们实际上要求的即为：\(\max_{i=0}^m f(x\oplus pre_i)\oplus pre_n\oplus pre_i\)
简单带入一下\(f\)，容易得到：
\(f(x\oplus pre_i)=f(x)\oplus f(pre_i)\)
有趣的是，\(f(x)\)相当于是将\(x\)在二进制下向左做一个一个单位长度的循环
这也可以证明我们对下列所有的\(f\)的变换是正确的，每一个\(f(x)\)都有唯一的值与之对应。
所以式子变为：\(f(x)\oplus f(pre_i)\oplus pre_n\oplus pre_i\)，其中后半截的可以预处理的，不妨设\(s_i=f(pre_i)\oplus pre_n\oplus pre_i\)
将\(s_1\sim s_n\)插入trie，并且注意到可以在不异或任何值的情况下对\(x\)进行变化，所以需要插入0别问90pts是为什么
再者，再看这个式子：\(\max_{i=0}^m f(x)\oplus s_i\),注意到\(x\in [0,2^n-1],f(x)\in[0,2^n-1]\)，所以可以将\(f(x)\)用\(x\)替换掉。
这样的话，式子化为\(\max_{i=0}^m x\oplus s_i\)，我们的问题就变成了如何求得这个最大值。
我们设solve(p,now,ans)表示当前遍历到trie的指针\(p\)，已经计算到第\(now\)位，答案最大为\(ans\)
此时我们来分类讨论，毕竟先后手都足够聪明。
- 若\(p\)有两个儿子，则不论第\(now\)位填什么，都有决策使这个位变为0，所以递归
solve(t[p][0],now-1,ans<<1),slove(t[p][1],now-1,ans<<1) - 若\(p\)仅有一个儿子，则可以反着填数，使这一位变成
1。设儿子为\(k\)，则递归solve(k,now-1,ans<<1|1) - 若\(p\)没有儿子，直接返回
(ans,1)（最大值和个数）
最后返回值是返回各个分支的最大值，注意个数的统计。
核心代码如下：
#define pr pair<int,int>
#define mk make_pair
pr query(int p,int ans){
if(t[p][0]==0&&t[p][1]==0)return mk(ans,1);
if(t[p][0]&&t[p][1]){
pr ans1=query(t[p][0],ans<<1);
pr ans2=query(t[p][1],ans<<1);
if(ans1.first==ans2.first)return mk(ans1.first,ans1.second+ans2.second);
return max(ans1,ans2);
}
if(t[p][0])return query(t[p][0],ans<<1|1);
return query(t[p][1],ans<<1|1);
}
signed main(){
ios::sync_with_stdio(false);
cin>>n>>m;
n2=1;for(int i=1;i<=n;i++)n2*=2;
for(int i=1;i<=m;i++)cin>>a[i];
for(int i=1;i<=m;i++)pre[i]=pre[i-1]^a[i];
for(int i=1;i<=m;i++)s[i]=get(pre[i])^pre[n]^pre[i];
for(int i=1;i<=m;i++)insert(s[i]);
insert(0);
pr ans=query(1,0);
cout<<ans.first<<endl<<ans.second<<endl;
}