博客

可以解决与异或有关的题目

思路：在一个较大的集合中(假设有1e5个数)，有一些数是没用意义的，因为它可以由其它数异或得到(就像线性代数里的线性相关)，我们若是能消除这些没有意义的数，得到一个较小的集合(60个数左右)，使得对这个较小的集合进行操作，等价于对大集合进行操作，显然可以极大的提升时间复杂度。

对于任意一个集合，如果其中有两个元素的最高位都是1，可以用异或将其中一个元素替换掉，如此往复，可以让集合用某一位作为最高位的数唯一，这样我们就可以用60个数的集合，来表示1e5个数的集合。

被替换掉的数显然可以通过集合元素异或得到。证：a与b最高位为第k位，且为1，a ^ b = c，c的第k位显然为0，现在用c替换掉b，而b = a ^ c，得证

线性基有以下性质：

1. 线性基没有异或和为 0 的子集
2. 线性基的元素能相互异或得到原集合的元素的所有相互异或得到的值
3. 线性基中每个元素的二进制最高位互不相同

求子集的最大异或和：

最大异或和

处理出线性基之后贪心找最大就行

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p[66];
void insert(ll x) {
    for (int i = 60; i >= 0; i--) {
        if (x & (1ll << i)) {
            if (p[i]) {
                x ^= p[i];
            } else {
                p[i] = x;
                return;
            }
        }
    }
}
ll ask_max() {
    ll res = 0;
    for (int i = 60; i >= 0; i--) {
        if ((res ^ p[i]) > res) {
            res ^= p[i];
        }
    }
    return res;
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        ll x;
        cin >> x;
        insert(x);
    }
    cout << ask_max() << endl;
    return 0;
}

求子集的最小异或和：

找到线性基中最小且不为0的返回就行。

线性基无法找到异或值为0的元素，所以若是有两个元素异或得到0，需要特判(下面没写特判)

ll ask_min() {
    for (int i = 0; i <= 60; i++) {
        if (p[i]) {
            return p[i];
        }
    }
    return 0;
}

求子集的第k小异或和：

k 大异或和

求解之前要先将线性基标准化，即对于集合中的元素，若有一个元素最高位在第p位上，则其他所有元素的第p位为0，标准化后的线性基用b数组存储，flag记录有没有异或值为0的子集，flag == false表示有

第k小异或和的贡献与k的二进制位对应

如求第5小的异或和，k = 5，bin(5) = 0b101，第5大异或和 = b[0] ^ b[2]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p[66], b[66], cnt = 0, flag = 1;
bool insert(ll x) {
    for (int i = 60; i >= 0; i--) {
        if (x & (1ll << i)) {
            if (p[i]) {
                x ^= p[i];
            } else {
                p[i] = x;
                return true;
            }
        }
    }
    return false;
}
void exchange() {
    for (int i = 0; i <= 60; i++) {
        for (int j = i - 1; j >= 0; j--) {
            if (p[i] & (1ll << j)) {
                p[i] ^= p[j];
            }
        }
        if (p[i]) {
            b[cnt++] = p[i];
        }
    }
}
ll kth(ll k) {
    if (k > ((1ll << cnt) - 1)) {
        return -1;
    }
    ll res = 0;
    for (int i = 0; i <= 60; i++) {
        if (k & (1ll << i)) {
            res ^= b[i];
        }
    }
    return res;
}
int main() {
    ll n, m, k;
    cin >> n;
    for (int i = 0; i < n; i++) {
        ll x;
        cin >> x;
        flag &= insert(x);
    }
    exchange();
    cin >> m;
    while (m--) {
        cin >> k;
        if (!flag && k == 1) {
            cout << 0 << endl;
        } else if (!flag) {
            cout << kth(k - 1) << endl;
        } else {
            cout << kth(k) << endl;
        }
    }
    return 0;
}