UnfriendlyDoublePermutation | Topcoder Archive

Problem Statement

An array a[1], a[2], ... a[k*n] is called a k-multipermutation if each number between 1 and n, inclusive, occurs exactly k times in it.

A k-multipermutation a is called unfriendly if no two adjacent elements in it are equal. For example, the 2-multipermutation (1, 2, 3, 2, 1, 3) is unfriendly, but (1, 2, 2, 3, 1, 3) is not.

You are given ints n and k. Return the number of unfriendly k-multipermutations of size n. The answer can be quite large, so return it modulo 10^9+7.

Definition

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

Constraints

n will be between 1 and 20, inclusive.
k will be between 1 and 5, inclusive.

Examples

```
2
```
```
2
```
```
Returns: 2
```
There are two such multipermutations: (1, 2, 1, 2) and (2, 1, 2, 1).
```
3
```
```
2
```
```
Returns: 30
```
```
5
```
```
1
```
```
Returns: 120
```
All 1-multipermutations (or simply permutations) are unfriendly.
```
2
```
```
4
```
```
Returns: 2
```

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.