### PROBLEM LINK:

**Author:** Vitaliy Herasymiv

**Tester:** Shang Jingbo and Gerald Agapov

**Editorialist:** Devendra Agarwal

### DIFFICULTY:

Medium

### PREREQUISITES:

Dynamic Programming.

### PROBLEM:

You are given N objects from 1 to N.Initially they are colored with color 1.You are supplied with C colors from 0,…C-1 .When object with color a is painted in color b, the resulting color will have color (a*b) mod C. Little Elephant is going to make K turns.

At i-th turn he will randomly choose any subset (even empty) of objects with indices in range [L_{i}; R_{i}] (inclusive) and paint all objects in chosen subset with random color (the same for all objects in the subset).

Little Elephant wants to know the expected sum of all colors over all n objects after making all K turns.

### Explanation

This problem can be solved using a simple dynamic programming approach.

The main idea is to find the probability of occurence of each color at each index for every turn.

**Note** : Sum of probability of occurence of colors at any index i is 1.

So let us think about the base case for this dp :

Initially the color at each index is 1 , so the probability of occurence of color 1 is 1 at each index.

**Pseudo Code For Base Case**

```
dp[i][j][k] denotes the probability of occurence of color k at jth index in ith turn.
Init dp[i][j][k] to 0 for all i , j, k.
for(int i=1;i<=N;i++)
dp[0][i][1]=1;
```

Let dp[i][j][k] denotes the probability of occurence of color k at j^{th} index in i^{th} turn.

Let us think on how to compute dp[i][j][k] :

In the i^{th} turn , we need to change the color of any subset from [ L_{i} ; R_{i} ] , so the probability of occurence of each color in the range [1 ; L_{i}-1 ] and [ R_{i}+1 ; N ] will be same as the (i-1)^{th} turn.

Let us now focus on the interval [ L_{i} ; R_{i} ] for i^{th} turn. Probability of presence of a index in all random subsets from [ L_{i} ; R_{i} ] is 0.5 ( Reason : Either you will take that element or you won’t take that element for the subset).So , dp[i][j][k] += dp[i-1][j][k] * (0.5) , if the j^{th} index is not selected in the subset.

Let us now focus on the case when index j is considered in the subset. Probability that it is considered in the subset is 0.5 .

Probability that this index is now colored with m^{th} color is 1/C , because there is equal probability of each color to be choosen. So probability that the index is choosen and is colored with m^{th} color is 1/(2C).

The resulting color will be m*k , where k is the existing color of that index. So , probability that the index is colored with k^{th} color and is colored with m^{th} color will add to the probability of getting (m * k)%C color.

So dp[i][j][(m * k)%C] += dp[i-1][j][k]/(2C) is justified.

Finally after all the turn’s , we can compute the expected value from dp[K][i][j] , dp[K][i][j] denotes the probability of color j at i^{th} index at the end . so we can summate over j * dp[K][i][j] over all i and j and get the expected value.

**Psedo Code**

```
for(int i=1;i<=K;i++)
Take_Input( L and R )
for(int j=1;j<=N;j++) //for all indices
for(int k=0;k<C;k++)
if( j>=L && j<=R)
// if you choose the subset and you choose mth colors
for(int m = 0;m<C;m++)
dp[i][j][(m*k)%C] += dp[i-1][j][k]/(2*C);
//if you don't chose it [ probability that you do not take it in subset is 0.5 ]
dp[i][j][k] += dp[i-1][j][k]*0.5
else
//This is unaffected in this turn
dp[i][j][k] += dp[i-1][j][k]
Finding_Answer:
for(int i=1;i<=N;i++)
for(int j=0;j<C;j++)
answer = answer + j*dp[K][i][j];
return answer
```

**Complexity**:

O(K * N * C * C).