异或线性基

对于一个数组 \(a\)，若 \(p\) 是它的一组异或线性基，则

\(p\) 中任意非空子集异或和不为 \(0\)
\(p\) 中每个数的最高位 \(1\) 唯一
\(a\) 中任意元素都可以通过 \(p\) 的子集异或出来

构造方法

贪心法和高斯消元

由于高斯消元构造的异或线性基具有更好的性质，因此使用高斯消元法

例题

题目描述

给定 \(n\) 个整数（数字可能重复），求在这些数中选取任意个，使得它们的异或和最大。

输入格式

第一行一个数 \(n\)，表示元素个数。

接下来一行 \(n\) 个数。

输出格式

仅一行，表示答案。

数据范围

\(1 \leq n \leq 50,\ 0 \leq S_i < 2^{50}\)

code:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 55;

int n;
ll p[N], cnt;

void gauss()
{
    cnt = 0;
    for (int i = 63; i >= 0; i--)
    {
        for (int j = cnt; j < n; j++)
            if (p[j] >> i & 1) 
                swap(p[j], p[cnt]);
        
        if (!(p[cnt] >> i & 1)) continue;
        
        for (int j = 0; j < n; j++)
            if (j != cnt && p[j] >> i & 1)
                p[j] ^= p[cnt];
                
        cnt++;
        if (cnt == n) break;
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> p[i];

    gauss();

    ll res = 0;
    for (int i = 0; i < cnt; i++) res ^= p[i];

    cout << res << endl;

    return 0;
}

题目描述

\(XOR\) 是一种位操作符，我们定义如下：对于两个二进制数 \(A\) 和 \(B\)，令 \(C = A\ XOR\ B\)，那么对于 \(C\) 的每一位，我们可以通过检查 \(A 和 B\) 对应位的数字来得到其值。对于每一位，\(1\ XOR\ 1 = 0，1\ XOR\ 0 = 1，0\ XOR\ 1 = 1，0\ XOR\ 0 = 0\)。我们将这个操作符简单地表示为 \(\oplus\)，例如 \(3 \oplus 1 = 2\), \(4 \oplus 3 = 7\)。\(XOR\) 是一个非常奇妙的操作符，本题就是关于 \(XOR\) 的问题。

我们可以选择几个数字，并依次对它们执行 \(XOR\) 操作，得到另一个数字。例如，如果我们选择 \(2, 3\) 和 \(4\)，对它们执行 \(XOR\) 操作，结果是 \(2 \oplus 3 \oplus 4 = 5\)。现在，给定 \(N\) 个数字，你可以从中选择一些数字（甚至是一个数字），执行 \(XOR\) 操作。现在我希望你告诉我第 \(K\) 小的数字是什么。

输入格式

第一行输入一个整数 \(T\)，表示有 \(T\) 组测试数据。

对于每组测试数据，第一行是一个整数 \(N\)，表示数字的个数。

第二行包含 \(N\) 个整数（每个数字的范围是 \(1\) 到 \((10^{18})\)）。

第三行是一个整数 \(Q\)，表示查询的次数。

第四行包含 \(Q\) 个数字，分别表示第 \((K_1, K_2, \dots, K_Q)\) 小的数。

输出格式

对于每组测试数据，输出 \(Case\) #\(C\)，其中 \(C\) 表示当前测试数据的编号。对于每次查询，输出一个整数，表示第 \(K\) 小的数字。如果少于 \(K\) 个不同的数字，输出 \(-1\)。

数据范围

\(T \leq 30,\ 1 \leq N \leq 10000,\ 1 \leq Q \leq 10000,\ 1 \leq S_i \leq 10^{18},\ 1 \leq K_i \leq 10000\)

code:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 100010;

int T;
int n, m;
ll p[N], cnt;

void gauss()
{
    cnt = 0;
    for (int i = 63; i >= 0; i--)
    {
        for (int j = cnt; j < n; j++)
            if (p[j] >> i & 1) 
                swap(p[j], p[cnt]);
        
        if (!(p[cnt] >> i & 1)) continue;
        
        for (int j = 0; j < n; j++)
            if (j != cnt && p[j] >> i & 1)
                p[j] ^= p[cnt];
                
        cnt++;
        if (cnt == n) break;
    }
}

int main()
{
    cin >> T;
    for (int cases = 1; cases <= T; cases++)
    {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> p[i];
        
        gauss();
        
        cout << "Case #" << cases << ':' << endl;
        
        cin >> m;
        while (m--)
        {
            ll k;
            cin >> k;
            if (cnt < n) k--;
            
            ll res = 0;
            if (k >= (1ll << cnt)) res = -1;
            else
            {
                for (int i = 0; i < cnt; i++)
                    if (k >> i & 1)
                        res ^= p[cnt - i - 1];
            }
            
            cout << res << endl;
        }
    }

    return 0;
}

异或线性基