If we represent the coloring book as a graph, the images act as the nodes and two nodes are connected with an edge if they cannot be colored in the same color.

Firstly, solve the case when all the input numbers are different. Then the graph consists of disjoint cycles and ~f(n)~ represents the number of ways we can color a cycle consisting of ~n~ nodes. The images are painted sequentially. The first image can be painted in ~k~ ways. The second can be painted in ~k-1~ ways because it has to differ from the first image. Analogously, it is concluded that in the ~k(k-1)^{n-1}~ colorings, there will exist some colorings in which the image numbered ~1~ is of the same color as the image numbered ~n~. Connecting the nodes ~1~ and ~n~, if they're of the same color, a cycle sized ~n-1~ is created with differently colored nodes. We can conclude that the recursive relation applies: ~f(n) = k(k-1)^{n-1} - f(n-1)~. Therefore, we can compute this function easily in linear complexity.

If the input numbers are not different, our cycles will have edges that are, in fact, trees. Let us imagine that we have colored the cycles and are now coloring those edges. The node connected directly with the cycle can be colored in ~k-1~ ways (it has to be different than the one connected to it), the node connected to it can be painted in also ~k-1~ ways and so on. It is a valid conclusion that for each node not belonging to the cycle, we have to multiply our current solution by ~k-1~.

We traverse the graph using DFS and decide how many cycles there are of different sizes.