XOR tập con lớn nhất · canuc80k6101

Cho mảng $x_{1}, \dots, x_{n}$ . Chọn một tập con bất kỳ, kể cả tập rỗng, và lấy XOR của các phần tử đã chọn. Hãy tìm giá trị XOR lớn nhất có thể.

Test 1

Input

4
1 2 7 8

Output

Giải thích: Chọn hai phần tử $7$ và $8$ cho XOR bằng $15$ ; không giá trị nào dùng bốn bit thấp có thể lớn hơn $15$ .

Mô hình: Cho mảng x_1..x_n. Chọn một tập con bất kỳ, kể cả tập rỗng, và lấy XOR của các phần tử đã chọn. Hãy tìm giá trị XOR lớn nhất có thể.
Thuật toán: Xây cơ sở theo bit cao nhất. Sau đó đặt ans=0. Duyệt pivot từ bit cao xuống thấp; nếu ans xor basis[bit] lớn hơn ans thì thực hiện XOR.
Thuật toán: Tại bit đang xét, các pivot thấp hơn không thể thay đổi các bit cao hơn. Vì vậy quyết định làm bit cao nhất có thể thành 1 luôn ưu tiên tuyệt đối và không gây mất phương án tốt hơn ở các bit đã chốt.
Chứng minh đúng: Duyệt từ bit cao xuống. Trước khi xét bit b, ans đã lớn nhất theo mọi bit lớn hơn b. Pivot có bit cao nhất b không đổi các bit lớn hơn. Nếu XOR pivot làm giá trị tăng, nó làm bit quyết định đầu tiên từ 0 thành 1, nên mọi phương án không dùng pivot đều nhỏ hơn; nếu không tăng, dùng pivot không thể tốt hơn. Quy nạp qua các bit cho thấy ans là phần tử lớn nhất của span.
Độ phức tạp: O(n*31) thời gian, O(31) bộ nhớ.