Core Concepts

Before defining a linear basis, it is essential to understand the following terms regarding bitwise XOR operations on integer sets:

XOR Sum

For a given set of unsigned integers Z, the XOR sum is the cumulative XOR of all its elements: Z₁ ⊕ Z₂ ⊕ ... ⊕ Z_n.

Span

The span of a set Z, denoted as span(Z), represents the set of all possible values generated by computing the XOR sum of every subset within Z.

Linear Dependence

A set Z is considered linearly dependent if there exists an element Z_i that can be expressed as the XOR sum of other elements in the set. Removing Z_i from Z does not alter span(Z). If no such element exists, the set is linearly independent.

Xor Linear Basis

A set B serves as a linear basis for a set S if it satisfies two conditions:

1. span(B) = span(S): The span of the basis covers all XOR combinations achievable by the original set.
2. B is linearly independent.

The number of elements in B defines the dimension or size of the basis. Key properties include:

• A linear basis for a given set is not strictly unique.
• No subset of a linear basis yields an XOR sum of zero.
• It constitutes the minimal set capable of spanning the original set's XOR space.
• Every element in the basis has a distinct highest set bit.
• Any XOR combination of elements from the original set can be uniquely formed by an XOR combination of basis elements.

Algorithmic Implementations

Constructing the Basis

Insertion involves reducing the element using existing basis vectors. If a new basis vector is added, eliminating the newly added bit from higher basis vectors and clearing lower set bits using existing lower basis vectors maintains a diagonalized form.

constexpr int MAX_BIT = 60;
unsigned long long basis[MAX_BIT + 1];
bool zero_flag = false;

void insert(unsigned long long val) {
    for (int bit = MAX_BIT; bit >= 0; --bit) {
        if (!((val >> bit) & 1)) continue;
        if (basis[bit]) {
            val ^= basis[bit];
        } else {
            basis[bit] = val;
            for (int lower = bit - 1; lower >= 0; --lower) {
                if (basis[lower] && ((basis[bit] >> lower) & 1)) {
                    basis[bit] ^= basis[lower];
                }
            }
            for (int upper = MAX_BIT; upper > bit; --upper) {
                if ((basis[upper] >> bit) & 1) {
                    basis[upper] ^= basis[bit];
                }
            }
            return;
        }
    }
    zero_flag = true;
}

Existence Verification

An integer can be represented by the basis if reducing it with the basis vectors results in zero.

bool exists(unsigned long long val) {
    for (int bit = MAX_BIT; bit >= 0; --bit) {
        if ((val >> bit) & 1) {
            if (!basis[bit]) return false;
            val ^= basis[bit];
        }
    }
    return true;
}

Querying Minimum XOR Subset Sum

The smallest non-zero basis element corresponds to the minimum XOR subset sum. If the original set contained linear dependencies (indicated by zero_flag), the minimum possible sum is zero.

unsigned long long query_min() {
    if (zero_flag) return 0;
    for (int bit = 0; bit <= MAX_BIT; ++bit) {
        if (basis[bit]) return basis[bit];
    }
    return 0;
}

Querying Maximum XOR Subset Sum

By greedily applying the basis vectors from the highest bit downwards, we maximize the result. To find the maximum XOR sum with a specific value x, simply initialize the result with x instead of zero.

unsigned long long query_max(unsigned long long initial = 0) {
    unsigned long long res = initial;
    for (int bit = MAX_BIT; bit >= 0; --bit) {
        if ((res ^ basis[bit]) > res) {
            res ^= basis[bit];
        }
    }
    return res;
}

Querying the K-th Smallest XOR Sum

By treating the binary representation of k as a selector for the diagonalized basis vectors, we can compute the k-th smallest sum. If zero is a valid sum, adjustments to k are necessary.

unsigned long long query_kth(unsigned long long k) {
    if (zero_flag) {
        if (k == 0) return 0;
        --k;
    }
    unsigned long long res = 0;
    for (int bit = 0; bit <= MAX_BIT; ++bit) {
        if (basis[bit]) {
            if (k & 1) res ^= basis[bit];
            k >>= 1;
        }
    }
    return res;
}