백준 17435 : 합성함수와 쿼리

https://www.acmicpc.net/problem/17435

17435번: 합성함수와 쿼리

 

dp[i][j] = f2^j(i) 즉, f1(i)를 2^j번 합성 함수한 결과를 의미합니다.

먼저, 주어진 f1(1) ~ f1(m)을 dp[1~m][0]에 담아줍니다.

​

dp[1][1] = dp[ dp[1][0] ][0];

dp[2][1] = dp[ dp[2][0] ][0];

...

dp[1][2] = dp[ dp[1][1] ][1]; // (f(1)을 2^2번 합성한 값) = ((f(1)을 2^1번 합성한 값)을 2^1번 합성한 값)

dp[i][j] = dp[ dp[i][j-1] ][j-1] 입니다.

​

예를 들어, f11(x)에서 11 == 1 + 2 + 8이므로,

x = x를 1번 합성한 값

x = x를 2번 합성한 값

x = x를 8번 합성한 값으로 쿼리 결과를 빠르게 구할 수 있습니다.

 

#include <cstdio>

int m, q, n, x, dp[200001][19];

int main() {
	scanf("%d", &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d", &dp[i][0]);
	}

	for (int i = 1; i < 19; i++) {
		for (int j = 1; j <= m; j++) {
			dp[j][i] = dp[dp[j][i - 1]][i - 1];
		}
	}

	scanf("%d", &q);
	for (int i = 0; i < q; i++) {
		scanf("%d %d", &n, &x);
		for (int j = 0; n != 0; j++) {
			if (n & 1) {
				x = dp[x][j];
			}
			n >>= 1;
		}
		printf("%d\n", x);
	}
}