关于此题E - Maximize XOR（Atcoder ABC 386）搜索技巧的一些总结

传送门
题目要求n个数中选k个数异或起来最大，我们想到字典树中最大异或和这一经典问题，但是很明显字典树只能解决任选两个数的最大异或，而此题是任选k个，那我们走投无路只能考虑爆搜。
首先可以很容易写出一个暴力的搜索：

void dfs1(long long pos,long long sum,long long kk) {
    if(kk == 0) {
        ans = max(ans,sum);
        return;
    }
    if(pos == n+1) return;
    for(long long i = pos;i <= n;i++)
        dfs1(i+1,sum ^ a[i],kk-1);
}

但是这样肯定是会T爆的，我们注意到，当k取得值比较大的时候，复杂度就已经接近\(2^{n}\)了，而这是肯定无法接受的。
如果做过最大异或和问题，那么肯定有一个性质是牢记于心的：一个数异或两遍另一个数还等于它本身（结合异或运算的法则很好推
那么我们想，当k非常大的时候，是不是可以把问题转化成：我们知道n个数异或起来的值，想从中剔除掉n-k个数使得结果最大，而此处的“剔除”操作，是不是和前面的“增加”操作其实都是异或操作（不像是加减操作 增加和剔除是不同的符号），那么我们只需要进行分类讨论：
当$k ≤ n-k: $只需要爆搜即可

当$k > n-k: $我们就相当于把初始值设成tot（就是所有数的异或和），然后同样的用上面的搜索函数，将kk（代表从n个数中找kk个数）从k改成n-k即可，因为此时想象成挑n-k个剔除。
得益于异或操作的这一性质，这道题被巧妙解决。

再顺带一提，关于搜索程序的写法，我一开始的写法是：

void dfs1(long long num,long long sum,long long kk) {
    if(num == kk) {
        ans = max(ans,sum);
        return;
    }
    for(long long i = 1;i <= n;i++) {
        if(!vis[i]) {
            vis[i] = 1;
            dfs1(num+1,sum ^ a[i],kk);
            vis[i] = 0;
        }
    }
}

然而这样就会T爆。原因是重复搜索了很多次相同的k（或n-k）个数，完全不需要在当前位置的时候还回头看，这样会大大浪费时间复杂度。所以搜索的写法也很重要