Connection Status:
Competition Arena > UnfriendlyDoublePermutation

UnfriendlyDoublePermutation

TCCC07 Semi 1 · 2007-07-30 · by andrewzta

TCCC07 Semi 1 · 2007-07-30 · by andrewzta · Dynamic Programming
Class Name: UnfriendlyMultiPermutation
Return Type: int
Method Name: count
Arg Types: (int, int)
Problem Statement

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.

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
4)
1
1
Returns: 1

Submissions are judged against all 100 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class UnfriendlyMultiPermutation with a public method int count(int n, int k) · 100 test cases · 2 s / 256 MB per case

Submitting as anonymous