[BOJ 25306] 백준 25306번 - 연속 XOR

		2022 연세대학교 미래캠퍼스 슬기로운 코딩생활 풀이
A		[BOJ 25304] 영수증
B		[BOJ 25305] 커트라인
C		[BOJ 25306] 연속 XOR
D		[BOJ 25307] 시루의 백화점 구경
E		[BOJ 25308] 방사형 그래프

1. 문제

$25306$. 연속 XOR (2022 연세대학교 미래캠퍼스 슬기로운 코딩생활 C번)

백준 25306번 - 연속 XOR (https://www.acmicpc.net/problem/25306)

2. 풀이

$XOR$의 성질 몇 가지를 이해하고 있으면, 쉽게 접근이 가능하다.

• $x\oplus 0 = x$
• $x\oplus x = 0$
• $x\oplus y = y\oplus x$
• $(x\oplus y)\oplus z = x\oplus (y\oplus z)$

어떤 수열 $A$의 substring XOR $(A_{L}\oplus A_{L+1}\oplus \ldots \oplus A_{R})$ 을 구하고자 한다. 이를 $A[L\sim R]$로 정의한다. 위의 성질들을 적절히 활용해서 다음과 같은 식을 도출해낼 수 있다.

$A[L\sim R]$ $=$ $(A_{L}\oplus A_{L+1}\oplus \ldots \oplus A_{R})$
$=$ $((A_{1}\oplus A_{2}\oplus \ldots \oplus A_{L-1})$ $\oplus$ $(A_{1}\oplus A_{2}\oplus \ldots \oplus A_{L-1}))$ $\oplus$ $(A_{L}\oplus A_{L+1}\oplus \ldots \oplus A_{R})$
$=$ $(A_{1}\oplus A_{2}\oplus \ldots \oplus A_{L-1})$ $\oplus$ $((A_{1}\oplus A_{2}\oplus \ldots \oplus A_{L-1})$ $\oplus$ $(A_{L}\oplus A_{L+1}\oplus \ldots \oplus A_{R}))$
$=$ $(A_{1}\oplus A_{2}\oplus \ldots \oplus A_{L-1})$ $\oplus$ $(A_{1}\oplus A_{2}\oplus \ldots \oplus A_{R})$
$=$ $A[1\sim (L-1)] \oplus A[1\sim R]$

---

$0$부터 시작해서 네 숫자 단위의 $XOR$ 합은 항상 $0$이다.

• $0\oplus 1\oplus 2\oplus 3$ $= 0$
• $4\oplus 5\oplus 6\oplus 7$ $= 0$
• $8\oplus 9\oplus 10\oplus 11$ $= 0 \;\ldots$

따라서 $A[1\sim X]$는 다음과 같은 값을 갖는다.

1. $X\,\%\, 4 = 0$ $\rightarrow$ $X$
2. $X\,\%\, 4 = 1$ $\rightarrow$ $1$
3. $X\,\%\, 4 = 2$ $\rightarrow$ $X+1$
4. $X\,\%\, 4 = 3$ $\rightarrow$ $0$

---

문제에서 구하고자 하는 값인 $X[A\ldots B]$는 첫 번째로 도출해낸 성질을 통해, $X[1\sim (A-1)] \oplus X[1\sim B]$로 구할 수 있다.

또한, 두 번째로 도출해낸 성질을 통해, $(A-1)$과 $B$를 $4$로 나누어 각각의 $XOR$ 값을 한 번에 구할 수 있다.

3. 채점 결과

4. 회고

XOR 성질을 잘 이해하고 있어야 풀 수 있었던 문제였다.

5. 코드