trang chủ / đề bài / xorbasis

XOR cực đại tập con

Đề bài

Mô tả

Cho dãy N số nguyên không âm a1,a2,…,aN.

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 X 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 0.

Hãy tìm giá trị X lớn nhất có thể đạt được.

Dữ liệu vào

  • Dòng đầu chứa số nguyên N.
  • Dòng thứ hai chứa N số nguyên không âm a1,a2,…,aN.

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

  • 1≤N≤105
  • 0≤ai<260

Ví dụ

Input Output Giải thích
3
1 2 3
3 Chọn tập {3} ta được X=3. Cũng có thể chọn {1,2} vì 1⊕2=3. Không thể đạt giá trị lớn hơn 3.
4
1 2 4 8
15 Chọn cả 4 phần tử: 1⊕2⊕4⊕8=15.
1
0
0 Chỉ có một số bằng 0; bất kể chọn hay không thì XOR đều bằng 0.

Ghi chú

Phép ⊕ là phép XOR bit (exclusive or). Ví dụ 5⊕3=6 vì 1012⊕0112=1102.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0