Khái niệm cơ sở tuyến tính

Cơ sở tuyến tính là một tập hợp các số được xây dựng từ một dãy cho trước, sao cho bất kỳ phần tử nào trong dãy gốc đều có thể được biểu diễn dưới dạng XOR của một số phần tử thuộc cơ sở. Kỹ thuật này thường được sử dụng để giải quyết các bài toán liên quan đến XOR của tập con.

Các tính chất quan trọng

• Mọi phần tử trong dãy ban đầu đều có thể được tạo ra bằng cách XOR một số phần tử từ cơ sở tuyến tính.
• Không tồn tại tập con khác rỗng trong cơ sở tuyến tính mà XOR của các phần tử trong tập đó bằng 0.
• Số lượng phần tử trong cơ sở tuyến tính là cố định và nhỏ nhất có thể, miễn là vẫn đảm bảo tính chất thứ nhất.

Cách xây dựng cơ sở tuyến tính

Giả sử ta dùng một mảng basis[] để lưu cơ sở tuyến tính, trong đó basis[i] lưu giá trị có bit cao nhất tại vị trí thứ i.

Quy trình xây dựng như sau:

• Duyệt từng phần tử trong dãy gốc, gọi phần tử đang xét là val.
• Duyệt các bit của val từ cao xuống thấp. Nếu bit thứ i bằng 1, xử lý hai trường hợp:
• Nếu basis[i] rỗng, gán basis[i] = val và kết thúc vòng lặp.
• Nếu basis[i] đã có giá trị, thực hiện val = val ^ basis[i] để xóa bit cao nhất hiện tại của val, rồi tiếp tục lặp.

Lý do phải duyệt từ bit cao xuống thấp là để đảm bảo basis[i] luôn là giá trị có bit cao nhất đúng tại vị trí i.

Chứng minh các tính chất

Tính chất 1

Dựa vào tính chất đảo ngược của phép XOR: nếu a ^ b = c thì c ^ b = a. Trong quá trình xây dựng, nếu val bị biến đổi thành 0, tức là val ban đầu đã có thể được biểu diễn bằng XOR của các phần tử trong cơ sở, nên không cần thêm vào. Ngược lại, val được đưa vào cơ sở. Như vậy, mọi phần tử trong dãy gốc đều có thể được biểu diễn thông qua cơ sở tuyến tính.

Tính chất 2

Giả sử phản chứng: nếu tồn tại a ^ b = 0 thì a = b, điều này vô lý vì hai giá trị trong cơ sở không thể giống nhau. Hơn nữa, điều này cũng vi phạm tính chất basis[i] là giá trị duy nhất có bit cao nhất tại vị trí i.

Tính chất 3

Việc thêm một phần tử vào cơ sở chỉ xảy ra khi nó không thể được biểu diễn bởi các phần tử đã có. Do đó, số lượng phần tử trong cơ sở là tối thiểu và duy nhất.

Code xây dựng cơ sở tuyến tính

const int MAX_BIT = 60;
long long basis[MAX_BIT + 1] = {0};

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

Bài toán XOR lớn nhất

Một ứng dụng phổ biến của cơ sở tuyến tính là bài toán: chọn một số phần tử từ dãy sao cho XOR của chúng đạt giá trị lớn nhất.

Vì giá trị của cơ sở tuyến tính bao trùm toàn bộ miền giá trị của dãy gốc, bài toán quy về việc chọn phần tử từ cơ sở để tối ưu kết quả XOR.

Phương pháp tham lam

Duyệt từ bit cao nhất xuống thấp. Nếu việc XOR result với basis[bit] làm result tăng lên, tức là bit thứ bit sẽ được bật lên 1, và đây là lựa chọn tối ưu cho bit đó. Nếu không duyệt từ cao xuống thấp, có thể bỏ lỡ貭 kết quả tốt hơn.

long long max_xor() {
    long long result = 0;
    for (int bit = MAX_BIT; bit >= 0; bit--) {
        if ((result ^ basis[bit]) > result) {
            result ^= basis[bit];
        }
    }
    return result;
}