자릿수 XOR
골드 IV의견: 0
암호학자 수빈이는 자릿수 XOR이 신기하다고 생각한다. 양의 정수 \(x\)의 자릿수 XOR은 \(x\)의 각 자리 숫자들을 모두 비트 XOR한 값이다.
예를 들어 \(123\)의 자릿수 XOR은 \(1 \oplus 2 \oplus 3 = 0\)이고, \(456\)의 자릿수 XOR은 \(4 \oplus 5 \oplus 6 = 7\)이다.
구간 \([L, R]\)에 있는 정수 중 자릿수 XOR이 정확히 \(X\)인 수의 개수를 구하여라.
- \(1 \le L \le R \le 10^{18}\)
- \(0 \le X \le 15\)
(자릿수는 \(0\)~\(9\)이므로 XOR은 항상 \(0\)~\(15\) 범위이다.)
한 줄에 세 정수 \(L\), \(R\), \(X\)가 공백으로 구분되어 주어진다.
\(L\) 이상 \(R\) 이하인 정수 중 자릿수 XOR이 정확히 \(X\)인 수의 개수를 출력한다.
1 20 5
2
자릿수 XOR이 \(5\)인 수: \(5\) (XOR=\(5\)), \(14\) (\(1 \oplus 4=5\)), \(19\) (\(1 \oplus 9=8\) 아님)... 확인하면 \(5, 14\)로 \(2\)개이다.
10 99 0
9
두 자리 수 \(\overline{ab}\)에서 \(a \oplus b = 0\) 이면 \(a=b\), 즉 \(11, 22, \ldots, 99\)의 \(9\)개이다.
riseoj 작성
출처 Original
평가 및 의견
자릿수 XOR
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
자릿수 XOR