[9521] 색칠하기

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

이 문제는 i에서 출발하여 f[i]로 향하는 간선을 직접 그려보면 몇가지 특징을 확인 할 수 있다.

1. 각 지점마다 하나의 간선을 출발시킨다는 점

2. 상호간에 간선관계가 직/간접적으로 전혀 없는 덩어리?그래프?들로 이루어져 있다는 점

3. 이 덩어리들안에는 무조건 단 하나의 루프가 있다는 점(자기자신으로 향하는 간선을 가진점도 루프로 간주)

결국 이 문제는 N개의 점이 몇개의 덩어리들로 나누어 져 있으며, 그 덩어리들은 각각 하나씩 루프를 가지고있다.

루프에 포함되지 않는 점들은 K-1개의 경우를 가지게되고, 결국 루프를 구성하는 점들의 경우의 수를 구할 수 있어야 한다.

1번부터 M번까지, M개의 점으로 이루어진 루프가 있다면 

1번 = K가지

2번 ~ M-2번 = K-1가지 의 경우가 존재하며

M-1번째 점이 만약 1번점과 같은 색을 가진다면, M번째 점은 K-1가지

M-1번째 점이 만약 1번점과 다른 색을 가진다면, M번째 점은 K-2가지 의 경우로 각각 나뉘게 된다.

즉 M개의 점으로 이루어진 루프를 구성하는 경우의 수를 d[M]이라 한다면

d[M] = d[M-2] * (K-1) + d[M-1] * (K-2) 로 표현할 수 있다. 

(물론 d[1] = K, d[2] = K(K-1), d[3] = K(K-1)(K-2)이다.)