Birthday Gift

我们将\(x++\)，从而最终的答案一定是要小于\(x\)的，也就一定要有一位不同

我们从高位到低位枚举最高的一位与\(x\)不同的位置\(i\)（也就是说，认为第\(i+1\)位到最高位都与\(x\)相同，但第\(i\)位不同）

我们先考虑更高位置如何相同

如果更高位置为\(0\)，那么那一位必须只能有偶数个\(1\)（否则无论怎么分组，最终这一位都是\(1\)），为了让组数最多，我们考虑每两个相邻\(1\)及其中间的\(0\)分为一组；我们从高到低地对每一位进行代码的分组，根据决策包容性，我们一定不会漏掉分组的组数。举个例子说明

比如在枚举的时候，我们第一次枚举到一个\(0\)，然后我们将每两个相邻\(1\)及其中间的\(0\)分为一组，如下

注意我们将每一组的所有数字都删除掉了，并形成一个新组，新组的每一个数字是原来对应组所有数字的异或（可见代码）

接下来我们考虑更低位的时候，我们分组就要满足上面的限制，比如如果我们要把四个\(1\)全部分在一起

就相当于合并新数组的\(a_1,a_2\)以及中间的两个\(0\)，根据贪心的决策包容性，显然没有问题

如果更高位置为\(1\)，那么随便怎么分组都不会超过限制。只是有一个问题，随便分组可能会导致这一位为\(0\)而不是\(1\)，不满足更高位都相同的要求。其实这个时候是不会遗漏最优解的，所以无所谓

主要是学习中间的决策包容性，以及不会遗漏最优解的操作

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
 
#define int ll
#define all(a) a.begin(), a.end()
 
void solve() {
    int n, x;
    cin >> n >> x;
    ++x;
    vector<int> a(n);
    for (int &i: a)
        cin >> i;
    int res = -1;
    for (int i = 30; i >= 0; --i) {
        vector<int> b;
        bool open = false;//为1表示有奇数个1，为0表示有偶数个1 
        for (int j = 0; j < a.size(); ++j) {
            if (!open)
                b.push_back(a[j]);
            else
                b.back() ^= a[j];
            if (a[j] & (1 << i))
                open = !open;
        }//尝试模拟一下这个循环，就是分组用的 
        if (!(x & (1 << i))) {//如果这一位是0 
            if (open) {//这一位有奇数个1
			//无论怎么分组最后这一位都会为1，大于0
			//我们又认为更高位都相同，所以不用往下循环了 
                cout << res << '\n';
                return;
            }
            a = b;//替换掉合并分组后的数组 
        } else {//如果这一位为1 
            if (!open)//这里就是不会遗漏最优解的原因
			//可以想一下 
                res = max(res, (int) b.size());
        }
    }
    cout << res << '\n';
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
}