Олимпиадный тренинг

Задача . B. Очевидная задача Arpa и ужасающее решение Mehrdad

Задача

Темы: математика Перебор теория чисел *1500

В стране Arpa живут прекрасные девушки, как мы уже отмечали раньше.

Однажды Arpa задумался над очевидной задачей:

Дан массив и целое число x. Посчитайте число пар индексов i, j (1 ≤ i < j ≤ n) таких, что $\text{[math]}$ , где $\text{[math]}$ — операция побитовый xor (в примечаниях дано определение).

$\text{[math]}$

Mehrdad тут же придумал ужасающее решении, в которое никто не мог поверить. Теперь Arpa нужна ваша помощь в написании решения к этой задаче.

Входные данные

Первоя строка содержит два целых числа n и x (1 ≤ n ≤ 10⁵, 0 ≤ x ≤ 10⁵) — число элементов в массиве и число x.

Вторая строка содержит n целых чисел a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁵) — элементы массива.

Выходные данные

Выведите одно целое число: ответ на задачу.

Примечание

В первом примере существует только одна пара индексов i = 1 и j = 2. $\text{[math]}$ , поэтому ответ равен 1.

Во втором примере две подходящие пары это i = 3, j = 4 (т. к. $\text{[math]}$ ) и i = 1, j = 5 (т. к. $\text{[math]}$ ).

Операция побитовый 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.

Примеры

№	Входные данные	Выходные данные
1	2 3 1 2	1
2	6 1 5 1 2 3 4 1	2

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет