M. Пары без общих битов

Посчитайте количество пар индексов $i < j$, для которых $a_i ;\&; a_j = 0$ — то есть у чисел нет ни одного общего единичного бита.

Условие $a_i ;\&; a_j = 0$ означает, что $a_j$ является подмаской дополнения $a_i$. А количество элементов, являющихся подмаской заданной маски, — это ровно то, что считает преобразование из классной задачи I.

Решение в три шага:

1. Посчитать, сколько раз встречается каждое значение: $cnt[v]$.
2. Прогнать по $cnt$ сумму по подмаскам — получится $sub[m]$, количество элементов, являющихся подмаской $m$.
3. Для каждого $i$ прибавить $sub[\lnot a_i]$, где дополнение берётся в пределах $n$ битов.

В сумме каждая пара учтётся дважды, а элемент, равный нулю, учтёт сам себя. Поэтому ответ равен

Стоит это $O(2^B \cdot B + n)$, где $B$ — количество битов. Перебор всех пар был бы $O(n^2)$, то есть $5 \cdot 10^9$.

Дополнение внутри $B$ битов — это ((1 << B) - 1) ^ a, а не ~a: последнее перевернёт и старшие биты, которых в задаче нет.

Первая строка содержит число $n$ ($1 \le n \le 10^5$).

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

Одно число.