행성 X3
시간 제한1초메모리 제한192 MB
최대 백만 개의 수가 주어질 때 모든 쌍의 XOR 값의 합을 비트별 개수를 세어 계산합니다.
문제
상근이는 초등학교 졸업 여행으로 외계 행성 X3을 방문했다. 이 행성 주민의 이름은 모두 자연수이며, 모든 주민은 서로를 알고 있다.
두 주민의 친밀도는 두 이름을 이진수로 쓴 뒤 계산한다. 자릿수가 더 짧은 이진수의 앞에 0을 붙여 두 길이를 맞춘다. 같은 자리의 비트가 같으면 0, 다르면 1을 적고, 그렇게 얻은 이진수를 십진수로 바꾼 값이 친밀도이다.
10과 19의 친밀도는 25이다.
1 0 0 1 1 = 19
0 1 0 1 0 = 10
--------------
1 1 0 0 1 = 25
행성 X3의 가치는 서로 다른 두 주민 쌍에 대해 계산한 친밀도의 총합이다. 주민들의 이름이 주어질 때 행성의 가치를 구하시오.
입력
첫째 줄에 X3 거주민의 수 N이 주어진다. (1 <= N <= 1,000,000)
다음 N개의 줄에는 거주민의 이름이 하나씩 주어진다. 각 이름은 1 이상 1,000,000 이하의 자연수이다.
출력
첫째 줄에 행성 X3의 가치를 출력한다.