AND가 0인 쌍
플래티넘 III의견: 0
\(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\)이 주어진다.
조건을 만족하는 쌍의 개수를 한 줄에 출력한다.
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\)은 조건을 만족하지 않는다.
3
0 0 7
3\(0\)은 어떤 수와도 AND가 \(0\)이므로 세 쌍 모두 조건을 만족하여 답은 3이다.
riseoj 작성
출처 Original
평가 및 의견
AND가 0인 쌍
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
AND가 0인 쌍