1.A2. CTDL&GT bài Các cặp phép toán XOR

LÀM BÀI
Points: 10
Time limit: 2.0s
Memory limit: 64M
Author:
hlk28chitinh
Problem type

Các cặp phép toán XOR

Trong một buổi tập bóng đá, FullHouse Dev đã tình cờ nghĩ ra một bài toán thú vị liên quan đến XOR. Họ quyết định chia sẻ bài toán này với đồng đội để rèn luyện tư duy logic trong lúc nghỉ giải lao.

Bài toán

Cho một mảng \(A\) gồm \(N\) số nguyên không âm. Hãy tìm số cặp chỉ số \((i, j)\) sao cho \(A[i] \oplus A[j] = i \oplus j\), trong đó \(\oplus\) là phép toán XOR bit.

INPUT FORMAT:
  • Dòng đầu tiên chứa một số nguyên \(T\) là số lượng bộ test.
  • Với mỗi bộ test:
    • Dòng đầu tiên chứa một số nguyên \(N\) là kích thước của mảng \(A\).
    • Dòng tiếp theo chứa \(N\) số nguyên cách nhau bởi dấu cách, biểu diễn các phần tử của mảng \(A\).
OUTPUT FORMAT:
  • Với mỗi bộ test, in ra một số nguyên duy nhất là số cặp thỏa mãn điều kiện đã nêu.
Ràng buộc:
  • \(1 \leq T \leq 10^5\)
  • \(1 \leq N \leq 10^5\)
  • \(0 \leq A[i] \leq 10^9\)
  • Tổng của \(N\) trong tất cả các bộ test không vượt quá \(10^6\).
VÍ DỤ:
INPUT
2
3
0 0 0
4
3 4 1 2
OUTPUT
0
2
Giải thích:
  • Ở bộ test đầu tiên, không có cặp nào thỏa mãn điều kiện.
  • Ở bộ test thứ hai, có hai cặp thỏa mãn:
    • Cặp \((1, 4)\): \(3 \oplus 2 = 1 \oplus 4 = 5\)
    • Cặp \((2, 3)\): \(4 \oplus 1 = 2 \oplus 3 = 5\)

Comments


  • 0
    Pham_Ngoc_Dung_FullHousedev  commented on April 4, 2025, 3:00 a.m.

    Bài này là đếm số lượng cặp thỏa mãn: A[i] + A[j] = i + j đúng không ạ, em hiểu như thế, còn phép xor trong bài này em hơi lạ

Zalo