Statistics

Problem Statement for "UnfriendlyDoublePermutation"

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

  1. 2

    2

    Returns: 2

    There are two such multipermutations: (1, 2, 1, 2) and (2, 1, 2, 1).

  2. 3

    2

    Returns: 30

  3. 5

    1

    Returns: 120

    All 1-multipermutations (or simply permutations) are unfriendly.

  4. 2

    4

    Returns: 2

  5. 1

    1

    Returns: 1

  6. 1

    2

    Returns: 0

  7. 1

    3

    Returns: 0

  8. 1

    4

    Returns: 0

  9. 1

    5

    Returns: 0

  10. 2

    1

    Returns: 2

  11. 2

    3

    Returns: 2

  12. 2

    5

    Returns: 2

  13. 3

    1

    Returns: 6

  14. 3

    3

    Returns: 174

  15. 3

    4

    Returns: 1092

  16. 3

    5

    Returns: 7188

  17. 4

    1

    Returns: 24

  18. 4

    2

    Returns: 864

  19. 4

    3

    Returns: 41304

  20. 4

    4

    Returns: 2265024

  21. 4

    5

    Returns: 134631576

  22. 5

    2

    Returns: 39480

  23. 5

    3

    Returns: 19606320

  24. 5

    4

    Returns: 804626003

  25. 5

    5

    Returns: 203219378

  26. 6

    1

    Returns: 720

  27. 6

    2

    Returns: 2631600

  28. 6

    3

    Returns: 438575488

  29. 6

    4

    Returns: 140277386

  30. 6

    5

    Returns: 317165676

  31. 7

    1

    Returns: 5040

  32. 7

    2

    Returns: 241133760

  33. 7

    3

    Returns: 418092294

  34. 7

    4

    Returns: 728992941

  35. 7

    5

    Returns: 118448843

  36. 8

    1

    Returns: 40320

  37. 8

    2

    Returns: 83420597

  38. 8

    3

    Returns: 469661638

  39. 8

    4

    Returns: 479268411

  40. 8

    5

    Returns: 342975242

  41. 9

    1

    Returns: 362880

  42. 9

    2

    Returns: 124981851

  43. 9

    3

    Returns: 836854787

  44. 9

    4

    Returns: 898235419

  45. 9

    5

    Returns: 479234341

  46. 10

    1

    Returns: 3628800

  47. 10

    2

    Returns: 254405203

  48. 10

    3

    Returns: 670231580

  49. 10

    4

    Returns: 453649723

  50. 10

    5

    Returns: 477459983

  51. 11

    1

    Returns: 39916800

  52. 11

    2

    Returns: 515604999

  53. 11

    3

    Returns: 34608874

  54. 11

    4

    Returns: 971175096

  55. 11

    5

    Returns: 871121441

  56. 12

    1

    Returns: 479001600

  57. 12

    2

    Returns: 888465295

  58. 12

    3

    Returns: 494181873

  59. 12

    4

    Returns: 819729140

  60. 12

    5

    Returns: 415683080

  61. 13

    1

    Returns: 227020758

  62. 13

    2

    Returns: 185598136

  63. 13

    3

    Returns: 375090565

  64. 13

    4

    Returns: 867560825

  65. 13

    5

    Returns: 835823803

  66. 14

    1

    Returns: 178290591

  67. 14

    2

    Returns: 856777481

  68. 14

    3

    Returns: 894602506

  69. 14

    4

    Returns: 396144007

  70. 14

    5

    Returns: 346215517

  71. 15

    1

    Returns: 674358851

  72. 15

    2

    Returns: 673809918

  73. 15

    3

    Returns: 18793148

  74. 15

    4

    Returns: 306729903

  75. 15

    5

    Returns: 348841564

  76. 16

    1

    Returns: 789741546

  77. 16

    2

    Returns: 836310995

  78. 16

    3

    Returns: 79198411

  79. 16

    4

    Returns: 851182610

  80. 16

    5

    Returns: 634037248

  81. 17

    1

    Returns: 425606191

  82. 17

    2

    Returns: 446761327

  83. 17

    3

    Returns: 469592108

  84. 17

    4

    Returns: 567408557

  85. 17

    5

    Returns: 698689526

  86. 18

    1

    Returns: 660911389

  87. 18

    2

    Returns: 370796721

  88. 18

    3

    Returns: 327901318

  89. 18

    4

    Returns: 180505980

  90. 18

    5

    Returns: 43859891

  91. 19

    1

    Returns: 557316307

  92. 19

    2

    Returns: 462465806

  93. 19

    3

    Returns: 438075748

  94. 19

    4

    Returns: 292781823

  95. 19

    5

    Returns: 366406363

  96. 20

    1

    Returns: 146326063

  97. 20

    2

    Returns: 626079153

  98. 20

    3

    Returns: 187620998

  99. 20

    4

    Returns: 770414171

  100. 20

    5

    Returns: 218637437

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.
This problem was used for: