D메일

엘 프사이 콩그루.

— 호오인 쿄우마

이 문제는 인터랙티브 문제이다.

세계선이란 특정 시점의 작은 사건 차이로 갈라진 독립적 차원의 한 갈래를 가리킨다. 이러한 세계선들은 모두 동시에 공존하며 서로 영향을 주지 않는 독립적인 평행 우주라고 볼 수 있다.

세계선은 총 $2^N$개가 있으며 각 세계선은 $0$ 이상 $2^N-1$ 이하의 서로 다른 정수로 나타낼 수 있다. 하지만 당신은 현재 당신이 있는 세계선이 몇 번 세계선인지 모른다. 이를 알아내기 위해 D메일과 다이버전스 미터를 사용하려고 한다.

D메일은 과거로 보낼 수 있는 문자메시지이다. 당신은 D메일로 $0$ 이상 $2^N-1$ 이하인 정수 $a$를 하나 과거로 보낼 수 있다. 번호가 $x$인 세계선에서 D메일로 정수 $a$를 보내면 과거의 사건이 미세하게 변경되어 $x\oplus a$번 세계선으로 이동하게 된다. ($\oplus$는 비트 XOR 연산자이다.)

다이버전스 미터는 현재 세계선을 나타내는 기계이다. 그러나 이 기계는 세계선을 정확하게 보여주지 못하고 $0$ 또는 $1$로만 표현할 수 있다. $0\leq i \leq 2^N-1$인 모든 정수 $i$에 대해 다이버전스 미터가 $i$번 세계선에서 출력하는 값을 $f(i)$라고 하자. 당신은 첫 번째 D메일을 보내기 전, $0\leq i \leq 2^N-1$인 모든 정수 $i$에 대해 $f(i)$의 값을 정할 수 있다. $f(i)$의 값은 한 번 정하고 나면 다시 바꿀 수 없으며, 이후 D메일을 보내 세계선이 바뀔 때마다 다이버전스 미터에 출력된 값을 확인할 수 있다. 다이버전스 미터를 설정한 후 D메일을 $N+1$번 이하로 보내 초기의 세계선이 몇 번 세계선이었는지 알아내 보자.