BOJ 24733 - 이것도 XOR해 보시지

May 10, 2023

$O(NK)$ 로 해결 가능하다.

$0$ 번째 수와 모든 수를 쿼리해서 $n-1$ 번의 쿼리를 써서 만든 배열을 $R$ 이라 하자.

$0$ 번째 수와 $\oplus$ 했을 때 $0$ 이 나오면 그것과 같다는 의미이다.

$k=1,2,\dots$ 을 반복하며 $t_0=k$ 로 두고 모든 다른 수를 $k \oplus R_i$ 를 해준다.

$R_i=a_0 \oplus a_i$ 이기 때문에 $k \oplus R_i = k \oplus k \oplus a_i=a_i$ 가 되기 때문이다.

이렇게 각 $k$ 마다 만들어진 배열을 $T$ 라 할 때,

$T$ 가 문제의 조건( $1 \le p \le k$ )에 맞게 수들이 배치가 되었는지 살핀다.

그렇다면 그것이 정답이고 아니라면 $k$ 를 계속 증가시킨다.

You may also enjoy