[codeforces] 1934D1. XOR Break — Solo Version

문제 링크

초기값이 $n$인 정수 변수 $x$가 있습니다. 저희는 $x$에 대해 다음 연산을 수행합니다.

• $0 < y < x$이면서 $0 < (x \oplus y) < x$인 정수 $y$를 선택합니다.
• $x$를 $y$ 또는 $x \oplus y$로 업데이트 합니다.

해당 연산을 최대 63번 사용해서 $x$의 값을 $m$으로 만들 수 있는지 판단하고 만들 수 있으면 만드는 과정을 출력하는 문제입니다.

케이스를 나눠서 생각해 봅시다. $m$의 $bm$번째 비트가 $m$에서 값이 $1$인 최상위 비트, $n$의 $bn_{1}$, $bn_{2}$번째 비트가 각각 $n$에서 값이 $1$인 최상위 비트, 두번째로 최상위 비트라고 하겠습니다. ($n$이 값이 $1$인 비트를 항상 두개 이상 가지고 있을 필요는 없으므로 $bn_{2}$는 항상 존재하는 값은 아닙니다.)

Case 1) $n$에서 값이 $1$인 비트의 갯수가 $1$개일 때

이 경우 $0 < y < n$인 모든 $y$에 대하여 $(n \oplus y) > n$을 만족합니다. 즉, 연산을 시행할 수 없어 $m$을 만드는것이 불가능합니다.

Case 2) $n$의 $bm$번째 비트가 $1$일 때

이 때는 항상 $(n \oplus m) < n$을 만족합니다. $m < n$이고 $n \oplus (n \oplus m) = m$을 만족하므로 연산에 $n \oplus m$을 사용할 수 있습니다. 즉, 연산 1번으로 $m$을 만들 수 있습니다.

Case 3) $n$의 $bm$번째 비트가 $0$일 때

Case 3-1) $bn_{2} < bm < bn_{1}$일 때

우리가 수행할 수 있는 연산을 사용하면 할 수록 $x$의 값은 감소합니다. 즉, $m$을 만들기 위해서는 $bn$번째 비트를 언젠가 $0$으로 전환해야 되는데 이때 $bm \leq i < bn$번째에 비트들 중 어느 하나라도 비트 값을 $1$로 바꿔주지 않으면 $x$의 값은 $m$보다 작아져 $m$을 만들 수 없게 됩니다. 그렇기 때문에 $bn$번째 비트를 $0$으로 바꿀 때 $bm \leq i < bn$번째 비트들 중 적어도 하나 이상은 $1$로 바꿔줘야 합니다.
위 과정을 거지치 위해 사용해야 되는 값은 $2^{bn-1} + 2^{i-1}$입니다. 그러나 이 값은 $n$을 초과합니다. 즉, 연산에 사용할 수 없고 다시 말해 위에서 언급한 과정을 수행할 수 없습니다. 그래서 이 경우에는 $m$을 만드는것이 불가능합니다.

Case 3-2) $bm < bn_{2}$일 때

$n$에서 첫번째부터 $bn_{2}$번째 비트까지 그대로 가져와서 만든 수를 $n'$이라고 하겠습니다. 그럼 $(n' \oplus m) < n$이고 $n \oplus (n' \oplus m) = 2^{bn_{1}-1} + m < n$이므로 연산을 시행해서 $x = 2^{bn_{1}-1} + m$으로 만들 수 있습니다. 그리고 $2^{bn_{1}-1}$으로 연산을 한번 더 시행하면 $x = m$이 됩니다. 즉, 연산 2번으로 $m$을 만들 수 있습니다.

입력을 받으면 어느 케이스에 해당한지 판단한 후에 답을 출력하면 됩니다. 이 과정은 $O(1)$에 수행이 가능하고 전체 시간복잡도는 $O(t)$가 됩니다.