Editorial

---

D

summary:

$2^{30}$보다 작은 수가 들어있는 길이 $n$ 배열이 있고 거기서 $l~r$의 구간에서 홀수 길이만큼 원하는 만큼 xor을 해서 구간을 모두 0으로 만들 수 있는지, 가능하다면 최소 횟수를 구하는 문제이다.

solution:

구간에서 아무리 xor을 해 봤자 구간 전체의 xor은 절대 바뀌지 않으므로 만약 구간 전체를 xor한 값이 0이 아니라면 불가능이다.

따라서 구간 전체의 xor이 0인지 체크하고, 모든 수가 0인지 체크 해준다. (0횟수로 가능한지)

그렇지 않고 구간의 길이가 홀수라면 1번만에 가능이다.

구간의 길이가 짝수라면 구간에서 홀수 길이의 xor해서 0이 되는 prefix가 존재해야 한다.

그렇지 않으면 어떤 구간을 하던 절대로 홀수 길이만 해서는 0을 만들 수가 없기 때문이다.

opinion:

나는 비트를 따로 떼서 생각했고, 1개수가 홀수이거나 전부 다 1이면 불가능이라고 생각했다. 그런데 틀렸다. 왜냐하면 1개수가 홀수이면 불가능은 맞는데, 짝수 길이에서 전부 다 1인 것은 가능이기 때문이다.

그리고 짝수 길이에서 xor해서 1이 되는 prefix가 존재해야 한다는 점을 놓쳤다.