SimilarSequencesAnother | Topcoder Archive

Problem Statement

Two sequences A and B are called similar if they have the same length and have the following property: we can obtain two identical sequences by deleting at most two elements of A and at most two elements of B. (The elements deleted from A don't have to have the same indices as the elements deleted from B. The order of the remaining elements in each sequence has to be preserved.)

You are given ints N and bound. Consider all the sequences with length N such that each element is an integer between 1 and bound, inclusive. Compute the number of ordered pairs of such sequences that are similar. Return this count modulo 1,000,000,009.

Definition

Class:: SimilarSequencesAnother
Method:: getCount
Parameters:: int, int
Returns:: int
Method signature:: int getCount(int N, int bound)
(be sure your method is public)

Constraints

N will be between 1 and 100, inclusive.
bound will be between 1 and 1,000,000,000, inclusive.

Examples

```
2
```
```
10
```
```
Returns: 10000
```
Any two 2-element sequences are similar. There are (10^2)^2 = 10,000 pairs of such sequences.
```
3
```
```
3
```
```
Returns: 687
```
In this case, two sequences are similar if they have at least one element in common. In other words, the two sequences are similar if there is a value that occurs in each of them. Let's count the pairs of sequences that are not similar. There are two possibilities: Each sequence contains the same value three times. For example, one sequence could be {1,1,1} and the other {3,3,3}. There are 6 such pairs. One sequence contains the same value three times, and the other contains the other two values, each of them at least once. For example, one sequence could be {2,3,2} and the other {1,1,1}. There are 2 * 3 * (2^3 - 2) = 36 such pairs. Thus, the total number of pairs of similar sequences is 3^6 - 6 - 36 = 687.
```
8
```
```
1
```
```
Returns: 1
```
```
100
```
```
123456789
```
```
Returns: 439681851
```
```
1
```
```
1000000000
```
```
Returns: 81
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.