SimilarSequences | Topcoder Archive

Problem Statement

Two sequences A and B are called similar if they are both non-empty, have the same length, and have the following property: we can obtain two identical sequences by deleting one element of A and one element of B. (The deleted elements do not necessarily have to have the same index. The order of the remaining elements in each sequence has to be preserved.)

You are given a int[] seq and a int bound. Consider all sequences such that each element is an integer between 1 and bound, inclusive. Count how many of such sequences are similar to seq. Return this count modulo 1,000,000,009.

Definition

Class:: SimilarSequences
Method:: count
Parameters:: int[], int
Returns:: int
Method signature:: int count(int[] seq, int bound)
(be sure your method is public)

Constraints

seq will contain between 1 and 40 elements, inclusive.
bound will be between 1 and 1,000,000,000, inclusive.
Each element in seq will be between 1 and bound, inclusive.

Examples

```
{1, 1}
```
```
3
```
```
Returns: 5
```
We need to count the number of sequences which consist of elements in [1, 3] and are similar to (1, 1). These sequences are (1, 1), (1, 2), (2, 1), (1, 3) and (3, 1).
```
{1, 2}
```
```
2
```
```
Returns: 4
```
Any valid sequence is similar to (1, 2).
```
{999999999}
```
```
1000000000
```
```
Returns: 1000000000
```
Note that after deleting the elements from the sequences, the resulting sequences may be empty.
```
{1, 2, 3, 4, 5}
```
```
5
```
```
Returns: 97
```

{5, 8, 11, 12, 4, 1, 7, 9}

1000000000

Returns: 999999363

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.