Codeforces Round 383 (Div. 2) |
---|
Закончено |
В стране Arpa живут прекрасные девушки, как мы уже отмечали раньше.
Однажды Arpa задумался над очевидной задачей:
Дан массив и целое число x. Посчитайте число пар индексов i, j (1 ≤ i < j ≤ n) таких, что , где — операция побитовый xor (в примечаниях дано определение).
Mehrdad тут же придумал ужасающее решении, в которое никто не мог поверить. Теперь Arpa нужна ваша помощь в написании решения к этой задаче.
Первоя строка содержит два целых числа n и x (1 ≤ n ≤ 105, 0 ≤ x ≤ 105) — число элементов в массиве и число x.
Вторая строка содержит n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 105) — элементы массива.
Выведите одно целое число: ответ на задачу.
2 3
1 2
1
6 1
5 1 2 3 4 1
2
В первом примере существует только одна пара индексов i = 1 и j = 2. , поэтому ответ равен 1.
Во втором примере две подходящие пары это i = 3, j = 4 (т. к. ) и i = 1, j = 5 (т. к. ).
Операция побитовый xor принимает два целых битовых числа одинаковой длины и выполняет логическую операцию xor на каждой паре соответсвующих бит. Результат в позиции равен 1, если и только если только первый бит 1 или только второй бит 1, и результат равен 0 если оба бита 0 или оба бита 1. Больше информации о побитовом xor можно найти здесь: https://ru.wikipedia.org/wiki/Битовые_операции#.D0.98.D1.81.D0.BA.D0.BB.D1.8E.D1.87.D0.B0.D1.8E.D1.89.D0.B5.D0.B5_.D0.98.D0.9B.D0.98_.28XOR.29.
Название |
---|