Editorial for Bedao Regular Contest 04 - CLOWN AND BALLS


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Xét ~n~ số nguyên đã cho dưới dạng nhị phân của chúng.

Với mỗi số nguyên, quy ước bit nhỏ nhất là bit ~0~ (tương ứng với ~2^0~). Khi đó bit thứ ~i~ tương ứng với ~2^i~.

Xét ~n~ số, nếu bit thứ ~i~ là bit ~1~ trong lẻ số thì khi chia ra ~2~ tập ~W~ và ~B~, ta thấy một trong hai tập sẽ có lẻ bit ~1~ thứ ~i~ và tập còn lại sẽ có chẵn bit ~1~ thứ ~i~. (Vì lẻ = chẵn + lẻ hoặc lẻ + chẵn).

Khi đó, vì ta lấy XOR ở mỗi tập, nên ở tập chẵn không còn ~2^i~ (chẵn bit ~1~ XOR sẽ là bit ~0~). Ngược lại, ở tập lẻ sẽ còn ~2^i~. Cho nên khi lấy kết quả tổng ~W + B~, luôn có ~2^i~ trong kết quả.

Vậy với những bit ~i~ xuất hiện lẻ lần, ở trong mọi trường hợp đều tính vào kết quả cuối cùng một lượng là ~2^i~. Ta gọi tổng của lượng không đổi này là ~ans_1~.

Điều này tương tự với việc ta không cần quan tâm đến những bit xuất hiện lẻ lần nữa. Đi lần lượt ~n~ số và tắt hết những bit xuất hiện lẻ lần của chúng.

Giờ những bit còn lại đều xuất hiện chẵn lần. Có ~2~ trường hợp là chẵn = chẵn + chẵn hoặc = lẻ + lẻ. Nghĩa là nếu ~W~ có bit ~1~ tại bit thứ ~i~ (hay nói cách khác, tập ~W~ có lẻ số có bit ~1~ tại vị trí này) thì ~B~ cũng có bit ~1~ tại bit thứ ~i~.

Từ đây suy ra ~W = B~. Khi đó, việc tối đa hóa ~W + B~ tương tự như tối đa hóa ~W~.

Bài toán trở thành cho ~n~ số ~a_i~. Hãy tìm một tập số mà tổng XOR của chúng là lớn nhất.

Bài toán trên là một bài toán cổ điển dùng Khử Gauss. Bạn đọc có thể tham khảo tại:

Cơ bản ý tưởng là: coi ~n~ số trên thành một ma trận ~n \times 61~ (Tính từ bit ~0~ tới bit ~60~). Tìm dạng ma trận bậc thang của ma trận trên bằng ~khử \ Gauss\ XOR~.

Gọi ~ans_2~ là kết quả của tổng ~XOR~ lớn nhất. Bắt đầu bằng ~ans_2 = 0~, sau đó lần lượt đi từ hàng trên cùng xuống dưới của ma trận (Gọi ~x~ là số ở hàng hiện tại), thực hiện ~ans_2 = max(ans_2, ans_2 \ XOR \ x)~.

Vì ~ans_2 = W~. Nên ~W + B = 2 \times ans_2~.

Vậy đáp án cuối cùng là: ~ans_1 + 2 \times ans_2~.

Độ phức tạp: ~O(N \times 61 \times log_2 (61))~ (Thao tác khử Gauss cần xét ~61~ bit)


Comments

Please read the guidelines before commenting.


There are no comments at the moment.