### PROBLEM LINK:

[Practice][111]

[Contest][222]

**Author:** Vitalij Kozhukhivskij

**Tester:** Praveen Dhinwa and Hiroto Sekido

**Editorialist:** Lalit Kundu

### DIFFICULTY:

Medium

### PREREQUISITES:

### PROBLEM:

You have a sequence of N elements H_{1},H_{2}…H_{N}. A climb is defined by the nonempty sequence (p_{1}, p_{1}+1), (p_{2}, p_{2}+1), …, (p_{s}, p_{s}+1), where p_{k}+1 ≤ p_{k+1} for k = 1, 2, …, s − 1.

Two climbs, say (p_{1}, p_{1}+1), (p_{2}, p_{2}+1), …, (p_{s}, p_{s}+1) and (q_{1}, q_{1}+1), (q_{2}, q_{2}+1), …, (q_{t}, q_{t}+1) are different if and only if

- s ≠ t or
- There exists at least one k such that 1 ≤ k < min(s, t) and H
_{pk+1}– H_{pk}≠ H_{qk+1}– H_{qk}.

If you read the problem carefully and is thought over for sometime you’ll realise the basically what is asked for is number of different/distinct subsequences of the sequence H_{2}-H_{1},H_{3}-H_{2}…H_{N}-H_{N-1}.

### EXPLANATION:

So, our problem is reduced to: Given a sequence A_{1},A_{2}…A_{N}, find the number of distinct subsequences. Subsequence is a sequence that can be derived from sequence A by deleting some elements without changing the order of the remaining elements. Two subsequences are distinct if there length are different or some of the corresponding element is different.

dp* = Number of distinct subsequences ending with A*.

sum* = dp[1] + dp[2] + … + dp*. So sum[n] will be our answer.

last* = last position of occurence of A* in the array A.

A null string has one subsequence, so dp[0] = 1.

```
for i=1 to N:
dp*= sum[i-1] - sum[last[a*]-1]
sum*=sum[i-1] + dp*
last[a*]=i
print sum[n]
```

Initially, we assume we can append A* to all subsequences ending on previous characters, but this might violate the condition that the counted subsequences need to be distinct. Remember that last[A*] gives us the last position A* appeared on until now. The only subsequences we overcount are those that the previous A* was appended to, so we subtract those.

Using map in C++ to store last would have timed out. It was intentional. Also, take care of modulo operations.

### ALTERNATIVE SOLUTION

If all elements in A are distinct, our answer will be 2^{N}. Let’s say dp* stores the answer for array A_1 to A_i. Now, if there is some i<j such that A*==A[j], we should consider only last occurence of A[j] ie. at the index i. So we have to subtract the number of subsequences due to it’s previous occurrence.

This pseudo code will make it more clear:

```
dp[0]=1 // for length 0 the subsequences are 1
for i=1 to N:
dp*=dp[i-1]*2
if A* has occured last time at index j:
dp*=dp*-dp[j-1]
print dp[n]
```

### AUTHOR’S AND TESTER’S SOLUTIONS:

[Author’s solution][131]

[Tester’s solution][132]

Note: Editorial inspired from a post on stackoverflow.

[111]: http://www.codechef.com/problems/MOU2H

[222]: http://www.codechef.com/AUG14/problems/MOU2H

[131]: http://www.codechef.com/download/Solutions/2014/August/Setter/MOU2H.cpp

[132]: http://www.codechef.com/download/Solutions/2014/August/Tester/MOU2H.cpp