VK Cup 2017 - Квалификация 1 |
---|
Закончено |
У Васи есть последовательность, состоящая из n целых чисел. Вася считает пару чисел x и y k-интересной, если их двоичное представление отличается друг от друга ровно в k битах. Например, если k = 2, то пара чисел x = 5 и y = 3 является k-интересной, так как двоичные представления x=101 и y=011 отличаются ровно в двух битах.
Васе стало интересно, сколько в его последовательности существует пар индексов (i, j) таких, что i < j и пара чисел ai и aj является k-интересной. Перед вами стоит задача помочь Васе и определить это количество.
В первой строке следует два целых числа n и k (2 ≤ n ≤ 105, 0 ≤ k ≤ 14) — количество чисел в последовательности Васи и количество битов, в которых должны отличаться числа в k-интересной паре.
Во второй строке следует последовательность a1, a2, ..., an (0 ≤ ai ≤ 104), которая есть у Васи.
Выведите количество пар (i, j) таких, что i < j и пара чисел ai и aj является k-интересной.
4 1
0 3 2 1
4
6 0
200 100 100 100 200 200
6
В первом примере существует 4 k-интересные пары:
Во втором примере k = 0. Следовательно, числа в любой k-интересной паре должны быть равны между собой. Таким образом, для второго примера существует 6 k-интересных пар:
Название |
---|