BOJ 23894 합성함수와 쿼리 2

먼저 $x, f(x), f^2(x), \cdots, f^m(x)$가 1을 포함하지 않는 경우를 빠르게 구하기 위해 sparse table을 만듭니다.

그리고 $x \neq 1$일 때 $f^e(x) = 1$인 최소의 $e$를 기록해 둡니다. 이는 역방향 그래프에서 1에서 시작하는 BFS를 수행하여 계산할 수 있습니다.

이제 다음의 방법으로 쿼리를 처리할 수 있습니다.

• 1번 쿼리: $f(1)$의 값을 업데이트합니다. 이는 별도의 처리가 필요하지 않습니다.
• 2번 쿼리
  • $x = 1$일 경우: $y = f(1)$에서 다시 1로 간다면 사이클이 발생합니다. 이 사이클의 길이 $d$는 $y$에서 1까지의 거리 + 1입니다. $d > m$이면 sparse table을 이용해 답을 구하면 되고, $d \le m$이면 $m$을 $m \bmod d$로 업데이트합니다. 그 뒤에 $m > 0$이면 $m$에서 1을 더 빼고 $y$로 이동한 뒤 sparse table로 답을 구합니다. $f(1) = 1$이라면 1이 답이 됩니다.
  • $x \neq 1$일 경우: $m$이 $x$에서 1까지의 거리 $d$ 이상이라면 1로 이동하고 $m$에서 $d$를 빼 준 뒤 위의 케이스로 넘어갑니다. 그렇지 않다면 sparse table로 답을 구할 수 있습니다.