TopCoder problem "UnfriendlyMultiPermutation" used in TCCC07 Semi 1 (Division I Level Two)



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

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

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8246

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10956&pm=8246

Writer:

andrewzta

Testers:

PabloGilberto , vorthys , Olexiy , misof , ivan_metelsky

Problem categories:

Dynamic Programming