Play with bit


Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 488M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

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
2

Giả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


  • 9
    old_creator  commented on Oct. 30, 2022, 12:15 p.m. edit 6

    \((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]\)