XOR 마법진
골드 II의견: 0
마법사의 수련장에는 \(N\)개의 마법 수정이 있으며, \(i\)번째 수정의 마력은 \(a_i\)이다. 수련생은 수정의 부분집합 (빈 집합 포함)을 선택하고, 선택한 수정들의 마력을 모두 비트 XOR한 값이 마법진의 마력이 된다.
마법진의 마력이 정확히 \(T\)가 되는 부분집합의 수를 구하여라.
- \(0 \le N \le 40\)
- \(0 \le a_i \le 10^9\)
- \(0 \le T \le 10^9\)
첫째 줄에 수정의 수 \(N\)과 목표 마력 \(T\)가 공백으로 구분되어 주어진다.
둘째 줄에 각 수정의 마력 \(a_1, a_2, \dots, a_N\)이 공백으로 구분되어 주어진다. (\(N=0\)이면 둘째 줄은 비어 있을 수 있다.)
마법진의 마력이 정확히 \(T\)가 되는 부분집합의 수를 출력한다.
4 0
1 2 3 4
2
XOR가 \(0\)인 부분집합: 빈 집합, \(\{1,2,3\}\)(\(1\oplus2\oplus3=0\)), \(\{1,2,3,4\}\)가 아니라 실제로 세면 \(\{\}\), \(\{1,2,3\}\), \(\{4\}\)는 \(4\neq0\)이므로 직접 열거해 확인한다.
3 5
5 5 5
4
\(5\) 하나로만 이루어진 부분집합 \(3\)가지(\(\{a_1\},\{a_2\},\{a_3\}\))와 세 개 모두 선택하는 \(1\)가지로 총 \(4\)가지다.
riseoj 작성
출처 Original
평가 및 의견
XOR 마법진
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
XOR 마법진