Các cặp số k-thú vị

Điểm: 5,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho dãy gồm $n$ số nguyên không âm. Một cặp số nguyên $x$ và $y$ được gọi là $k$ -thú vị nếu biểu diễn nhị phân của chúng khác nhau ở đúng $k$ vị trí bit.

Ví dụ với $k = 2$ : cặp $x = 5$ và $y = 3$ là $k$ -thú vị vì $x = 101_{2}$ và $y = 011_{2}$ khác nhau ở $2$ bit.

Cho dãy $a_{1}, a_{2}, \dots, a_{n}$ và số $k$ . Hãy đếm số cặp chỉ số $(i, j)$ thoả mãn $i < j$ và cặp giá trị $(a_{i}, a_{j})$ là $k$ -thú vị.

Dữ liệu vào

Dòng thứ nhất chứa hai số nguyên $n$ và $k$ .
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .

Dữ liệu ra

Một số nguyên — số cặp $(i, j)$ với $i < j$ sao cho $(a_{i}, a_{j})$ là $k$ -thú vị.

Ràng buộc

$2 \leq n \leq 10^{5}$
$0 \leq k \leq 14$
$0 \leq a_{i} \leq 10^{4}$

Ví dụ

Input	Output	Giải thích
4 1 0 3 2 1	4	Có $4$ cặp $k$ -thú vị: $(1, 3), (1, 4), (2, 3), (2, 4)$ .
6 0 200 100 100 100 200 200	6	$k = 0$ nghĩa là hai số phải bằng nhau. Các cặp thoả mãn: $(1, 5), (1, 6), (2, 3), (2, 4), (3, 4), (5, 6)$ .

Bình luận

Không có bình luận tại thời điểm này.