상근이의 숫자 친구 세기
시간 제한1초메모리 제한128 MB
최대 백만 개의 큰 정수가 주어질 때 적어도 하나의 십진수 자릿수를 공유하는 쌍의 개수를 세는 문제로, 각 수를 10비트 마스크로 표현해 1024개 부분집합에 대해 효율적으로 계산해야 합니다.
문제
정수 두 개가 같은 숫자를 하나 이상 포함하면 두 정수는 친구입니다. 같은 숫자가 나타나는 위치는 달라도 됩니다.
서로 다른 양의 정수 N개가 주어질 때, 친구인 정수 쌍의 개수를 구하세요. 인덱스가 다른 두 수를 하나의 쌍으로 보며, 순서만 다른 두 쌍은 같은 쌍입니다.
입력
첫째 줄에 정수의 개수 N이 주어집니다. (1 <= N <= 1,000,000)
다음 N개의 줄에는 1 이상 10^18 이하의 양의 정수가 하나씩 주어집니다. 같은 정수는 두 번 이상 주어지지 않습니다.
출력
친구인 정수 쌍의 개수를 출력합니다.