합성함수와 쿼리

백준 17435번: 합성함수와 쿼리

아이디어

f500,000(x)를 구하기 위해 50만번 함수를 실행하면 시간초과를 받을 것이다.
f1(x), f2(x), f4(x), f8(x), f16(x).. 이렇게 미리 저장해놓으면 빠르게 구할 수 있다. 예를 들어 f20(x)는 f16(f4(x))이다. 모든 쿼리에 대해 로그 시간으로 대답할 수 있게 된다.

코드

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX = 200001;

int M, Q;
int table[MAX][19]; // 2^0 ~ 2^18 (n <= 500,000)

void make_table() {
    for (int i = 1; i < 19; i++) {
        for (int j = 1; j < M+1; j++) {
            table[j][i] = table[table[j][i-1]][i-1];
        }
    }
}

int query(int n, int x) {
    for (int i = 0; i < 19; i++) {
        if (n & (1<<i)) {
            x = table[x][i];
        }
    }
    return x;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> M;
    for (int i = 1; i < M+1; i++) {
        cin >> table[i][0];
    }
    make_table();

    cin >> Q;
    for (int i = 0; i < Q; i++) {
        int n, x;
        cin >> n >> x;
        cout << query(n, x) << '\n';
    }
    
    return 0;
}

여담

수학시간에 합성함수만 나오면 벌벌 떨었는데..