문제
풀이
sparse table을 이용한 문제이다. 기존 o(n)의 시간복잡도에서 o(log2(n))으로 시간복잡도를 줄여 정답을 도출하는 문제이다.
f1(x), f2(x), f4(x)… f2^(n)(x)의 값들을 dp를 통해 저장해놓는다. 이 때 점화식은 dp[i][x] = dp[i-1][dp[i-1][x]]이다.
그 이후, n을 n을 넘지 않는 가장 큰 2의 진수들로 계산해나가며 정답을 도출해낸다.
소스 코드
```python import sys from math import *
m = int(sys.stdin.readline()) # m = 5
func = [0] + list(map(int, sys.stdin.readline().split()))
dp = [[0 for i in range(m+1)] for j in range(19)]
for i in range(1, m+1): dp[0][i] = func[i]
for i in range(1, 19): for j in range(1, m+1): dp[i][j] = dp[i-1][dp[i-1][j]]
q = int(sys.stdin.readline())
for _ in range(q): n, x = map(int, sys.stdin.readline().split())
1
2
3
4
5
6
for j in range(18, -1, -1):
if(n >= 1 << j):
n -= 1 << j
x = dp[j][x]
print(x)
#log2(200000) = 17.6
1
```
