Tính tổng a[i] XOR a[j]

Format lại code bằng cách thêm 3 dấu ` vào đầu và cuối code, như thế này:

// code của bạn

Bạn format code xong thì mình mới đọc được code của bạn.

OK bạn, mình đã edit rồi đó.

Code khá tường minh đó. Khổ nỗi bị sai .

Bạn để ý rằng, trong 1 dãy xor, cứ có chẵn bit 1 thì kết quả của dãy bằng 0, nếu không thì bằng 1.

1 ^ 1 ^ 1 = 1
1 ^ 1 ^ 1 ^ 1 = 0

Cái gì xor 0 cũng bằng chính nó.

x ^ 0 = x

Ta sẽ sử dụng 2 tính chất trên vào bài này.

Lưu ý thêm, a[i] ^ ... ^ a[j] = 1 số ghép bởi các bit, với mỗi bit k là kết quả của phép xor bit thứ k của các số a[i],... a[j], hay

res là 1 số có nhiều bit, với mọi bit k thì
res[k] = a[i][k] ^ ... ^ a[j][k]

Dòng trên không đúng về mặt lập trình, tuy nhiên mình sử dụng để bạn có thể mường tượng dễ hơn.

Limit bài này là 10^6 nên ta xét 20 bit. Với 20 bit, ta kiểm tra với mỗi bit i có bao nhiêu số a[u] có giá trị của bit i bằng 1. Các bit được đánh số từ phải sang trái. Bit 0 là bit tận cùng bên phải. Ví dụ:

a[1] = 10 = 0..001010 (2) // bit 1 và bit 3 bằng 1
a[2] = 8  = 0..001000 (2) // bit 3 bằng 1
a[3] = 7  = 0..000111 (2) // bit 0, 1, 2 bằng 1
a[4] = 18 = 0..010010 (2) // bit 1 và bit 4 bằng 1 
a[5] = 3  = 0..000011 (2) // bit 0 và bit 1 bằng 1
--------------------------
XOR       = 0..010100 (2) // thử xor cả dãy

author’s note: đến đây mình phát hiện ra code này không đẹp lắm, hơn nữa lại rất dễ gây hiểu nhầm, mình sẽ giải thích theo cách của mình.

Ta định nghĩa

b[i] = số lượng các số a[u] có bit i bằng 1

Cách kiểm tra xem số a[u] có bit i bằng 1 hay không:

// nhớ khởi tạo mảng b !!!!!!!!!

for (int i = 0; i <= 20; i++) // chạy từ 0 -> 20 không sao cả
    for (int u = 0; u < n; u++)
        if (a[u] & (1 << i) > 0) b[i]++;  // toán tử bitwise AND

1 << i là pow(2, i), nó biểu diễn dưới dạng nhị phân là 100..00 (i chữ số 0). Xem ví dụ để hiểu dòng code trên hơn:

x = 10 (1010 trong hệ nhị phân) -> lấy bit 3
         x = 1010
& (1 << 3) = 1000
-------------------
             1000
// 1 & 1 = 1, các trường hợp khác cho kết quả = 0 hết.

Khi kết quả x & (1 << 3) lớn hơn 0, ta kết luận x có bit 3 bằng 1.

Ta đã xong mảng b. Trích xuất kết quả:

s = 0;  // khởi tạo biến kết quả !!!!!!
for (int i = 0; i <= 20; i++) // lấy 20 bit
    if (b[i] % 2 == 0) // ở vị trí bit i có chẵn bit 1 -> bit i của kết quả sẽ bằng 0
        s += 0; // mình rảnh thôi, bạn có thể bỏ dòng này đi
    else // ở vị trí bit i có lẻ bit 1 -> bit i của kết quả sẽ bằng 1
        s += (1 << i)

Bạn nên đọc 1 tài liệu về bitwise để hiểu thêm.

Cảm ơn bạn vì sự chi tiết :D.

Cám ơn anh vì sự nhiệt tình :D.

Do xor tính trên từng bit nên ta xét bit thứ k của cả N số. Ta quan tâm đến số các bit 0 và số các bit 1 để tính số các bit 1 còn lại. Mà 1 xor 0 = 0 xor 1 = 1 nên kết quả tính là số bit 1 * số bit 0.

Vậy bài này quay trong O(N).

N <= 10^6, xấu nhất là có N / 2 bit 1 và N / 2 bit 0, có sợ nhân vào sẽ bị to quá không ạ?

Mình cũng tự hỏi là số 12 đó thớt tính ntn chứ sum này phải có int64, tối đa khoảng 10^12.