NondistinctSequences | Topcoder Archive

Problem Statement

A sequence of integers is called k-nondistinct if, for every k consecutive elements, there are at least two equal numbers. For example, the sequence {1, 2, 1, 2} is 3-nondistinct, but the sequence {1, 2, 3, 2} is not.

You will be given ints n, k and m. Return the number of sequences containing exactly n elements, where each element is between 1 and m, inclusive, that are k-nondistinct. Since this number can be quite large, return it modulo 1,000,000,007.

Definition

Class:: NondistinctSequences
Method:: count
Parameters:: int, int, int
Returns:: int
Method signature:: int count(int n, int k, int m)
(be sure your method is public)

Constraints

n will be between 1 and 50, inclusive.
k will be between 2 and 7, inclusive.
m will be between 1 and 50, inclusive.

Examples

```
4
```
```
3
```
```
3
```
```
Returns: 51
```
```
3
```
```
2
```
```
10
```
```
Returns: 10
```
In this case any two adjacent elements must be the same, so a sequence must contain all the same elements.
```
10
```
```
3
```
```
2
```
```
Returns: 1024
```
In this case, all sequences are valid. With only two possible values, any three consecutive elements will always contain at least two equal values.
```
35
```
```
6
```
```
37
```
```
Returns: 447605495
```

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.