문제 17435번: 합성함수와 쿼리 (acmicpc.net) 17435번: 합성함수와 쿼리 함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자. f1(x) = f(x) fn+1(x) = f(fn(x)) 예를 들어 f4(1) = f(f(f(f(1))))이다. n과 x가 주어질 때 fn(x)를 계산하는 www.acmicpc.net 풀이 정의역과 공역의 범위가 같은 functional graph가 주어졌으므로 무한히 합성가능합니다. n번 합성한 경우의 함수값을 결정하기 위해 n번 반복을 한다면 Q * n 으로 최대 200,000 x 500,000 의 연산량이 발생해버립니다. 따라서 다른 방법을 사..
희소 배열
희소 배열 희소배열, Sparse Table 이라 불리는 기법에 대해 알아봅시다. 노드마다 단 하나의 간선만을 가지는 방향그래프가 있습니다. 위와 같은 그래프를 특별히 functional graph라고 부릅니다. 이 그래프에서 각 노드는 간선을 타고 한 칸씩 움직일 수 있습니다. 이때 만약 1번 노드에서 3칸 전진한 노드를 알고 싶다면, 1 -> 2 -> 4 -> 8 이므로 8번 노드임을 알 수 있습니다. 그렇다면 1번 노드에서 10칸 전진한 노드를 알고 싶다면? 직접 10칸을 움직여보면 알 수 있겠죠. 1 -> 2 -> 4 -> ... -> 7입니다. 1,000,000,000 칸 전진한 노드를 알고 싶다면? 1,000,000,000 번 움직여야하기 때문에 컴퓨터로 작업한다해도 시간이 꽤나 걸리게 될겁니..
