AlienAndPermutation | Topcoder Archive

Problem Statement

Note that in this problem you are given a int[] that can contain up to 200 elements. You should also be able to submit test cases of this size during the Challenge phase of this SRM.

Alien Fred wants to destroy the Earth. But before he does that, he wants to play with a permutation.

Fred has a permutation of all the integers between 1 and N, inclusive. You are given a int[] P of size N. For each i, the i-th element (0-based index) of P represents the i-th element (again, 0-based index) of Fred's permutation.

Fred will now make a sequence of changes to P. Each change will look as follows: Fred will select a contiguous non-empty segment of P, and change all of its elements to the largest one among them. (Note that after such a change P will most likely stop being a permutation. This is allowed.)

You are also given an int K. Fred is allowed to make at most K consecutive changes to P. He is allowed to make fewer than K changes if he wants to, including the possibility to make no changes at all.

Let X be the total number of different sequences he can produce at the end of the above process. Return the value (X modulo 1,000,000,007).

Definition

Class:: AlienAndPermutation
Method:: getNumber
Parameters:: int[], int
Returns:: int
Method signature:: int getNumber(int[] P, int K)
(be sure your method is public)

Constraints

P will contain between 1 and 200 elements, inclusive.
P will represent a permutation of integers between 1 and N, inclusive, where N is the number of elements in P.
K will be between 0 and 200, inclusive.

Examples

```
{1, 2}
```
```
1
```
```
Returns: 2
```
The following two sequences are possible in this case: (1, 2) and (2, 2).
```
{3, 1, 2}
```
```
2
```
```
Returns: 4
```
Four sequences are possible in this case: (3, 1, 2) (3, 2, 2) (3, 3, 2) (3, 3, 3)
```
{4, 3, 2, 1}
```
```
2
```
```
Returns: 13
```
```
{1, 7, 2, 3, 6, 4, 5}
```
```
3
```
```
Returns: 77
```

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}

Returns: 379796836

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.