To solve the first subtask, notice that, in order to not decrease the number of different colours, Oliver has to choose the same part of the painting in both steps. The probability that this will happen is ~\frac 1 n~ per iteration, and ~(\frac 1 n)^t~ after ~t~ iterations.

The second subtask can be solved by using dynamic programming. The states will be all partitions of the number ~n~ (sorted array of frequencies of each of the colours) because the symmetrical cases when we rotate the frequencies of each colour are redundant. Now we go through all combinations of Oliver's choice of two parts and determine in which partition of ~n~ it will change into. This is the transition. We will repeat it ~t~ times and then sum up all probabilities of partitions that consist of at least ~k~ colours.

For solving the last subtask, it is necessary to notice that we are using always the same transition, and that, actually, each of the elements from the current state is a linear combination of elements from the previous states. Because of that, we can store the states in a mathematical vector and create a transition matrix, and then apply the matrix ~t~ times.