Construction Algorithm

The Linear Basis structure maintains a set of linearly independent vectors to solve problems involving the XOR operation. To insert a value into the basis, we process the bits from the most significant bit (MSB) to the least significant bit (LSB).

Let basis[] be the array storing the basis elements, initialized to 0. For an input value val:

1. Iterate from the highest bit down to 0.
2. If the bit-th bit of val is not set, continue.
3. If basis[bit] is empty (0), assign basis[bit] = val and stop.
4. Otherwise, update val = val XOR basis[bit] to eliminate the current high bit and continue checking lower bits.

const int BIT_WIDTH = 60;
long long basis[BIT_WIDTH];

void insertValue(long long val) {
    for (int i = BIT_WIDTH - 1; i >= 0; --i) {
        if (!(val >> i & 1)) continue;
        if (!basis[i]) {
            basis[i] = val;
            return;
        }
        val ^= basis[i];
    }
}

Fundamental Properties

1. Completeness: Any number from the original sequence can be represented as the XOR sum of a subset of the basis vectors.

2. Independence: No non-empty subset of the basis vectors results in an XOR sum of 0. This ensures linear independence in the vector space $GF(2)^n$.

3. Cardinality Uniqueness: The number of elements in any valid linear basis constructed from the same set of numbers is constant.

Proof of Independence: Assume a subset of the basis sums to 0, implying $A \oplus B \oplus C = 0$, which means $A \oplus B = C$. Since $C$ can be formed by $A$ and $B$, the insertion algorithm would have eliminated $C$ and it would not exist in the basis. This is a contradiction.

Checking Representability

To determine if a specific target value can be formed by the basis, we attempt to reduce it to zero using the stored basis vectors.

bool canRepresent(long long target) {
    for (int i = BIT_WIDTH - 1; i >= 0; --i) {
        if ((target >> i) & 1) {
            target ^= basis[i];
        }
    }
    return target == 0;
}

Finding Maximum XOR Value

To find the maximum XOR sum possible, we use a greedy strategy starting from the highest bit. If XORing the current answer with the basis element at a specific bit increases the value, we apply the operation.

long long findMaximum() {
    long long res = 0;
    for (int i = BIT_WIDTH - 1; i >= 0; --i) {
        if (basis[i]) {
            res = std::max(res, res ^ basis[i]);
        }
    }
    return res;
}

Finding Minimum XOR Value

The minimum non-zero XOR value is the smallest element stored in the basis. If the original set contained 0, the answer is 0.

long long findMinimum(bool zeroExists) {
    if (zeroExists) return 0;
    for (int i = 0; i < BIT_WIDTH; ++i) {
        if (basis[i]) return basis[i];
    }
    return 0;
}