M. Пары с заданным «или»

Посчитайте количество пар индексов $i < j$, для которых $a_i \oplus a_j = k$.

Ключевое свойство исключающего «или»: из $a \oplus b = k$ следует $b = a \oplus k$. То есть для каждого элемента напарник определён однозначно — это уже не перебор, а поиск.

Идём слева направо, храня счётчик встреченных значений:

long long answer = 0;
std::unordered_map<int, int> seen;
for (int x : a) {
    answer += seen[x ^ k];
    seen[x]++;
}

Каждая пара учитывается ровно один раз — в момент, когда встречается её правый элемент.

Отдельный случай — $k = 0$: тогда напарник элемента равен ему самому, и формула считает количество пар одинаковых значений. Никакой особой обработки это не требует, но проверить на таком тесте стоит.

Ответ может не поместиться в 32 бита: при $10^5$ одинаковых чисел и $k = 0$ пар почти $5 \cdot 10^9$.

Первая строка содержит числа $n$ ($1 \le n \le 10^5$) и $k$ ($0 \le k < 2^{30}$).

Вторая строка — $n$ чисел $a_i$ ($0 \le a_i < 2^{30}$).

Одно число.