Московская командная олимпиада: Московская командная олимпиада 2017, лига Б

Маленькая девочка Алёна гуляла по лесу и увидела компанию из \(n\) программистов. Поговорив с ними она оценила общительность каждого человека в компании целым неотрицательным числом, и записала эти значения в виде последовательности \(a_1, a_2, \ldots, a_n\), \(i\)-й элемент которой соответствует общительности \(i\)-го программиста в компании.

Алёна считает, что сила дружбы двух программистов равна побитовому И величин их общительности. Так, сила дружбы \(i\)-го и \(j\)-го программистов из данной компании будет равна \(a_i\,and\,a_j\). Сплочённостью компании девочка называется сумму силы дружбы по всем парам двух различных программистов в компании. Помогите Алёне определить сплочённость встретившейся ей компании, то есть величину \(\)\sum_{i = 1}^{n-1} \sum_{j = i + 1}^{n} a_i\,and\,a_j\(\)

Дадим определение операции побитового И, обозначаемой в данном условии задачи как \(and\). Рассмотрим записи чисел \(x\) и \(y\) в двоичной системе счисления (возможно с ведущими нулями) \(x = x_k \dots x_1 x_0\) и \(y = y_k \dots y_1 y_0\). Тогда \(z = x\,and\,y\) определяется следующим образом: \(z = z_k \dots z_1 z_0\), где \(z_i=1\), если \(x_i=1\) и \(y_i=1\), иначе \(z_i=0\). Иными словами, единицы в побитовом И чисел находятся в тех разрядах, в которых у обоих чисел находятся единицы. Например, побитовое И чисел \(14=1110_2\) и \(7=0111_2\) равняется \(6 = 0110_2\). В языках программирования C/C++/Java/Python данная операция обозначается как &, а в Pascal как and.