原题链接
解析
看到要求按位与的最大值，想到拆位。从高位往低位考虑，因为低位的 \(1\) 再多也比不上一个高位的 \(1\)。
从简单情形开始考虑，不妨只考虑一位，也就是令 \(a_i\) 的取值范围为 \(\{0,1\}\)，此时我们希望分成的 \(m\) 段每段的异或和都为 \(1\)，这等价于每段中有奇数个 \(1\)。于是可以发现最终按位与的结果可以为 \(1\) 当且仅当序列中 \(1\) 的个数的奇偶性与 \(m\) 的奇偶性相同且 \(1\) 的个数大于等于 \(m\)。
也就是说，我们主要关心每一段 \(1\) 的个数的奇偶性，每一段内 \(1\) 的个数并不重要，总个数够用就行，保证了前面分割出来的段的奇偶性，就能保证最后一段的奇偶性。
值域扩展后可以提出一个做法：设已经选取了的位的集合为 \(S\)。从高往低位考虑，只考虑这一位上 \(1\) 的个数的奇偶性与 \(m\) 相同的位。然后遍历序列尝试分段，维护当前每一位上 \(1\) 的出现次数的奇偶性，每当当前段中 \(S\) 中所有的位的 \(1\) 的个数都为奇数就分一段，最后如果能分不少于 \(m\) 段就将这一位加入 \(S\)。\(S\) 中每一位组合成的数即为所求。
时间复杂度 \(O(n \log V)\)。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int N = 3e5 + 5,M = 2e5 + 5,base1 = 131,base2 = 13331,mod = 998244353,mod2 = 1e9 + 7;
int a[N],cnt[30];
int main(){ios::sync_with_stdio(false);cin.tie(0);int T;cin>>T;while(T--){memset(cnt,0,sizeof(cnt));int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];for(int j=0;j<=29;j++){cnt[j] += bool(a[i] & (1 << j));}}int res = 0;for(int i=29;i>=0;i--)if((cnt[i] & 1) == (m & 1)){int nres = res | (1 << i),t = 1,x = 0;for(int j=1;j <= n && t < m;j++){x ^= a[j];if((x & nres) == nres){t++;x = 0;}}if(t >= m){res = nres;}}cout<<res<<'\n';}return 0;
}