Morphling | Topcoder Archive

Problem Statement

You are given the ints N and K.

Let S be the set of all arrays that have the following properties:

The length of the array is exactly N.
Each element in the array is an integer between 1 and N, inclusive.
Each number occurs in the array at most K times.

Morphing an array A is an operation that consists of three steps:

Choose two distinct integers x and y, each between 1 and N, inclusive.
Change the values of some elements of A: All elements of A that had the value x will now have the value y and vice versa.
Finally, swap two elements of A: the elements with the 1-based indices x and y.

For example, suppose that A = [1,3,3,4]. One possible morphing of this array will look as follows:

We choose x=1 and y=3.
After changing the values in A, we have the array [3,1,1,4].
Then, after the swap we have the final result: the array [1,1,3,4].

Note that if we morph an array that belongs into S, the result will always belong into S as well.

We are interested in a subset T of S with the property that any array in S can be produced from some array in T by a sequence of zero or more morphing operations. Find the smallest possible size of such subset T, and return its size modulo 1,000,000,007.

Definition

Class:: Morphling
Method:: findsz
Parameters:: int, int
Returns:: int
Method signature:: int findsz(int N, int K)
(be sure your method is public)

Constraints

N will be between 1 and 100, inclusive.
K will be between 1 and min(25, N), inclusive.

Examples

```
1
```
```
1
```
```
Returns: 1
```
The only valid array is [1]. The subset T must contain this array.
```
2
```
```
1
```
```
Returns: 2
```
There are two arrays in S: [1,2] and [2,1]. The morphing operation always changes [1,2] into [1,2] and it always changes [2,1] into [2,1]. Therefore we need to include both arrays into T.
```
2
```
```
2
```
```
Returns: 3
```
There are four arrays in S: [1,2], [2,1], [1,1], [2,2]. The morphing operation allows to transform [1,1] to [2,2], so only one of this should be included into T.
```
3
```
```
1
```
```
Returns: 3
```
```
3
```
```
3
```
```
Returns: 7
```
Here the set S contains 27 different arrays. Some of these arrays can be produced from other arrays by morphing. The smallest possible subset T with the required property consists of only 7 of these arrays.
```
10
```
```
1
```
```
Returns: 42
```
```
48
```
```
18
```
```
Returns: 270440792
```
```
100
```
```
25
```
```
Returns: 796177038
```

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.