MAXOR - Tập con XOR lớn nhất
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: cuom1999

Cho n số a[1], a[2], .. a[n]. Hãy chọn ra một tập con có k số sao cho XOR các phần tử của chúng lớn nhất. Định nghĩa phép XOR xem tại https://vi.wikipedia.org/wiki/Ph%C3%A9p_to%C3%A1n_thao_t%C3%A1c_bit

Input: Dòng đầu chứa n và k(1 <= k <= n <= 20). Dòng thứ hai chứa n số a[i] (0 <= a[i] <= 10^18)

Output: In ra một số là giá trị XOR lớn nhất có thể của một bộ k số

Input 1:

3 2

1 2 3

Output 1:

3

Input 2:

3 3 

1 2 3

Output 2:

0

Ví dụ

Trong test 1, có 3 cách chọn:

(1, 2): 1 XOR 2 = 3

(1, 3): 1 XOR 3 = 2

(2, 3): 2 XOR 3 = 1

Đáp số lớn nhất là 3, ứng với cách 1

Trong test 2 chỉ có 1 cách chọn (1, 2, 3) và 1 XOR 2 XOR 3 = 0

Back to Top