XOR cực đại tập con
Đề bài
Mô tả
Cho dãy số nguyên không âm .
Bạn được phép chọn một tập con bất kỳ (có thể rỗng) của dãy. Gọi là giá trị XOR (phép XOR bit) của tất cả phần tử đã chọn. Quy ước XOR của tập rỗng bằng .
Hãy tìm giá trị lớn nhất có thể đạt được.
Dữ liệu vào
- Dòng đầu chứa số nguyên .
- Dòng thứ hai chứa số nguyên không âm .
Dữ liệu ra
In ra một số nguyên duy nhất là giá trị XOR lớn nhất có thể đạt được.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 1 2 3 |
3 | Chọn tập ta được . Cũng có thể chọn vì . Không thể đạt giá trị lớn hơn . |
| 4 1 2 4 8 |
15 | Chọn cả phần tử: . |
| 1 0 |
0 | Chỉ có một số bằng ; bất kể chọn hay không thì XOR đều bằng . |
Ghi chú
Phép là phép XOR bit (exclusive or). Ví dụ vì .
Bình luận