## Editorial for An Animal Contest 6 P5 - Rock Painting

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: rickyqin005

What is the probability of rock being the first or last rock with some colour ?

Let's create an array of length to represent the initial state of the rocks. If , the rock has not been coloured. Otherwise, will denote the colour of the rock.

We also define to be the probability of rock being the rightmost rock and to be the probability of rock being the leftmost rock with some colour . We have:

where is the number of non-coloured rocks to the right of rock and is the number of distinct non-zero to the right of rock . Calculating is the same as but in reverse.

Therefore, the final answer to this problem is:

Time Complexity:

For this subtask, we can generalize the definition of to be . Using , we have:

Using some algebra, we have:

Substituting the sum of geometric series formula into the equation, we get:

Time Complexity: