레이팅 미적용설명
\(N\)개의 음이 아닌 정수 \(a_1, \dots, a_N\)이 주어진다.
비트 AND 연산 결과가 \(0\)이 되는 쌍, 즉 \(a_i \,\&\, a_j = 0\)인 쌍 \((i, j)\) (\(i < j\))의 개수를 구하여라.
모든 쌍을 직접 확인하는 \(O(N^2)\) 풀이는 통과할 수 없다. 각 수의 보수의 부분집합 개수를 한 번에 세는 부분집합 합 동적 계획법(SOS DP)이 필요하다.
제약
\(1 \le N \le 200{,}000\)
\(0 \le a_i < 2^{20}\)
입력 형식
첫 줄에 \(N\)이 주어진다.
둘째 줄에 \(a_1, \dots, a_N\)이 주어진다.
출력 형식
조건을 만족하는 쌍의 개수를 한 줄에 출력한다.
예제 1
입력
4
5 2 10 8
출력
4설명
\(5\,\&\,2 = 0\), \(5\,\&\,10 = 0\), \(5\,\&\,8 = 0\), \(2\,\&\,8 = 0\)로 4쌍이다. \(2\,\&\,10 = 2\), \(10\,\&\,8 = 8\)은 조건을 만족하지 않는다.
예제 2
입력
3
0 0 7
출력
3설명
\(0\)은 어떤 수와도 AND가 \(0\)이므로 세 쌍 모두 조건을 만족하여 답은 3이다.
문제 정보
riseoj 작성
출처 Original
태그