Play with bit
Tài là một cậu bé mà sẽ rất thích thú khi được nhận một dãy số A gồm N số nguyên không âm. Và Tài phải giải quyết vấn đề sau để có thể nhận được dãy số A này.
Cho một số nguyên không âm k, tìm số lượng cặp (i, j) (1 ≤ i ≤ j ≤ N) thỏa điều kiện sau: (Ai|Aj ) + (Ai ⊕ Aj ) + (Ai&Aj ) = k + Aj trong đó:
• (Ai|Aj ) được định nghĩa là phép toán Or.
• (Ai ⊕ Aj ) được định nghĩa là phép toán Xor.
• (Ai&Aj ) được định nghĩa là phép toán And.
Đầu vào
• Dòng thứ nhất chứa số nguyên T (1 ≤ T ≤ 10^5) - số lượng test.
• Mỗi test sẽ được tổ chức như sau:
– Dòng đầu tiên của mỗi test chứa hai số nguyên N, K (1 ≤ N ≤ 10^5) (0 ≤ K ≤ 10^18).
– Dòng tiếp theo chứa N số nguyên A1, A2, · · · , AN (0 ≤ Ai ≤ 10^18).• Tổng của N trong các test không vượt quá 3 · 10^5
Đầu ra
Đếm số cặp số thỏa mãn điều kiện đã nêu trên.
Ví dụ:
Đầu vào
2
1 8
7
3 8
1 6 4Đầu ra
0
2Giải thích:
• Ví dụ đầu tiên chỉ có một số nguyên duy nhất vậy nên không có cặp số nào thỏa mãn.
• Ở ví dụ thứ hai, chúng ta có hai cặp số thỏa mãn điều kiện:
– (i, j) = (1, 2) với A1 = 1 và A2 = 6 (1|6)+(1⊕6)+(1&6) = 7+7+0 = 14 và 8+6 = 14.
– (i, j) = (2, 3) với A1 = 6 và A2 = 4 (6|4)+(6⊕4)+(6&4) = 6+2+4 = 14 và 8+6 = 14.
Comments
\((A[i] | A[j]) + (A[i] ⊕ A[j]) + (A[i] \& A[j]) = k + A[j]\)
\(\iff A[i] + A[j] + (A[i] ⊕ A[j]) = k + A[j]\)
\(\iff A[i] ⊕ A[j] = k - A[i]\)
\(\iff A[i] ⊕ (A[i] ⊕ A[j]) = A[i] ⊕ (k - A[i])\)
\(\iff (A[i] ⊕ A[i]) ⊕ A[j] = A[i] ⊕ (k - A[i])\)
\(\iff A[j] = A[i] ⊕ (k - A[i])\)
Như vậy ta lập mảng \(B[i] = A[i] ⊕ (k - A[i])\) (\(B[i]\) có thể âm), với mỗi phần tử trong \(B[i]\) ta đếm số \(j > i\) sao cho \(A[j] = B[i]\)