A boy has n objects to paint, ordered in a row and numbered form left to right starting from 1. There are totally c colors, numbered from 0 to c-1. At the beginning all objects are colored in color with number 1. When object with color a is painted in color b, the resulting color will have color (a*b) mod c.
Now he is going to make k turns. At i-th turn he will randomly choose any subset (even empty) of objects with indices in range [Li; Ri] (inclusive) and paint all objects in chosen subset with random color (the same for all objects in the subset).
Now for given values of N,C,K. and K pairs of integers Li and Ri ,
we have to calculate the expected sum of all colors over all n objects after making all k turns. Help !!.
Example :
4 3 4
1 2
2 4
3 3
1 4
Ans : 3.44444444
I've been trying this from some time with no result.
I want a way on how to do this , please help!!.