Statistics

Problem Statement for "OddPairRemoval"

Problem Statement

You are given the int[] a of length 2*n. This array contains each of the integers 1 through n exactly twice.

A removal is the following action:

  • choose two indices i and j such that j-i is odd and a[i] = a[j]
  • delete a[i] and a[j] from the array
  • concatenate the remaining parts of a into a shorter array
For example, consider the array a = {1, 2, 4, 1, 2, 3, 4, 3}.
  • You may pick i = 1, j = 4 to remove both occurrences of the integer 2 and obtain the new array {1, 4, 1, 3, 4, 3}.
  • You may not pick i = 1, j = 2, as a[i] != a[j].
  • You may not pick i = 2, j = 6, as j-i is even.

You may perform zero or more removals, with the additional constraint that the removed values must be strictly increasing.

Return the long[] res of length n+1, where res[i] is the number of ways to remove exactly i pairs of integers from a.

Definition

Class:
OddPairRemoval
Method:
waysToRemove
Parameters:
int[]
Returns:
long[]
Method signature:
long[] waysToRemove(int[] a)
(be sure your method is public)

Constraints

  • n will be between 1 and 52, inclusive.
  • The length of a will be exactly 2*n.
  • Each integer between 1 and n, inclusive, will have exactly two occurrences in a.

Examples

  1. {1, 2, 1, 3, 2, 3}

    Returns: {1, 1, 1, 0 }

    We have the following options: We don't remove anything. We remove the 2s and then stop. We remove the 2s, producing the array {1, 1, 3, 3}, and then we remove the 3s. There is 1 way to remove no pairs, 1 way to remove one pair, 1 way to remove two pairs, and 0 ways to remove all three pairs. Therefore, the correct return value is {1, 1, 1, 0}. Note that in the beginning we cannot remove the 1s because their distance is even. Once we remove the 2s, the distance between the 1s becomes odd. However, now we cannot remove them due to the additional constraint that removed values must be increasing.

  2. {1, 2, 3, 1, 2, 3}

    Returns: {1, 3, 0, 0 }

    We can remove any number. Afterwards, all the other pairs will be at even distance and further removal will be impossible.

  3. {1, 1, 2, 2, 3, 3, 4, 4}

    Returns: {1, 4, 6, 4, 1 }

    The numbers are independent, hence any subset can be removed.

  4. {2, 3, 1, 6, 2, 5, 3, 7, 4, 1, 4, 7, 5, 6}

    Returns: {1, 3, 5, 6, 6, 6, 4, 1 }

  5. {1, 1}

    Returns: {1, 1 }

  6. {1, 1, 2, 2, 3, 3, 4, 4, 5, 5}

    Returns: {1, 5, 10, 10, 5, 1 }

  7. {1,1}

    Returns: {1, 1 }

  8. {2,1,2,1}

    Returns: {1, 0, 0 }

  9. {1,2,3,3,1,2}

    Returns: {1, 1, 0, 0 }

  10. {4,2,3,3,4,1,1,2}

    Returns: {1, 2, 1, 0, 0 }

  11. {2,1,4,1,5,2,3,5,4,3}

    Returns: {1, 3, 3, 1, 0, 0 }

  12. {4,4,5,2,6,1,6,1,2,3,3,5}

    Returns: {1, 4, 6, 4, 1, 0, 0 }

  13. {1,4,5,7,1,2,4,2,6,5,6,3,3,7}

    Returns: {1, 3, 5, 4, 1, 0, 0, 0 }

  14. {1,8,4,3,8,5,3,2,5,7,6,1,2,7,6,4}

    Returns: {1, 6, 13, 16, 8, 5, 2, 0, 0 }

  15. {5,4,6,6,1,9,4,8,3,2,1,7,2,5,8,7,3,9}

    Returns: {1, 5, 13, 18, 13, 4, 0, 0, 0, 0 }

  16. {5,4,6,6,8,2,4,2,1,5,7,1,10,7,10,3,8,9,3,9}

    Returns: {1, 6, 18, 31, 33, 22, 10, 4, 1, 0, 0 }

  17. {2,9,1,3,6,1,3,5,4,7,5,4,10,9,2,8,7,8,11,11,10,6}

    Returns: {1, 7, 19, 26, 20, 7, 0, 0, 0, 0, 0, 0 }

  18. {11,8,7,12,6,6,3,1,9,12,1,2,2,4,5,10,11,8,3,7,4,9,10,5}

    Returns: {1, 8, 29, 59, 79, 73, 43, 14, 2, 0, 0, 0, 0 }

  19. {11,3,1,13,12,7,1,4,12,6,5,10,3,4,13,11,8,9,9,7,2,8,10,6,5,2}

    Returns: {1, 7, 21, 36, 52, 63, 49, 20, 3, 0, 0, 0, 0, 0 }

  20. {1,3,4,5,13,9,7,9,12,7,11,14,13,6,2,8,11,10,6,14,4,2,5,1,10,3,12,8}

    Returns: {1, 6, 24, 62, 121, 157, 151, 98, 39, 12, 2, 0, 0, 0, 0 }

  21. {14,2,9,12,8,3,13,15,14,12,6,8,4,7,11,1,9,15,13,10,3,5,11,5,4,2,1,10,7,6}

    Returns: {1, 5, 28, 58, 89, 98, 61, 38, 19, 7, 3, 2, 0, 0, 0, 0 }

  22. {8,9,5,16,13,2,7,6,13,4,10,12,8,9,11,12,7,1,5,16,15,2,6,10,14,15,4,3,11,1,3,14}

    Returns: {1, 6, 24, 56, 92, 122, 125, 84, 37, 14, 3, 0, 0, 0, 0, 0, 0 }

  23. {7,14,8,4,5,2,3,1,9,4,12,1,16,11,11,6,14,9,12,8,10,13,5,13,7,15,17,10,16,17,6,15,3,2}

    Returns: {1, 7, 24, 41, 51, 41, 21, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  24. {11,14,6,3,5,2,9,1,10,11,10,7,18,14,12,4,18,16,17,9,1,3,8,5,8,4,6,15,13,17,12,13,7,16,2,15}

    Returns: {1, 8, 34, 95, 179, 272, 357, 371, 314, 224, 129, 58, 15, 1, 0, 0, 0, 0, 0 }

  25. {8,13,16,15,11,12,15,19,5,18,1,18,4,2,3,6,7,17,13,12,5,9,2,14,11,4,8,7,14,10,16,17,19,10,1,9,3,6}

    Returns: {1, 7, 32, 84, 179, 193, 164, 100, 50, 25, 8, 1, 0, 0, 0, 0, 0, 0, 0, 0 }

  26. {3,13,3,20,9,14,8,7,1,17,19,15,8,14,15,10,4,2,11,6,12,4,11,13,20,16,1,5,17,5,9,6,16,10,19,2,12,18,18,7}

    Returns: {1, 6, 17, 31, 47, 60, 58, 43, 24, 9, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  27. {19,13,4,9,7,1,18,4,7,2,14,10,1,12,2,13,6,14,17,19,5,20,18,9,15,5,12,6,8,21,8,11,17,3,16,15,16,20,11,3,10,21}

    Returns: {1, 11, 61, 203, 481, 867, 1212, 1361, 1213, 871, 504, 229, 76, 16, 1, 0, 0, 0, 0, 0, 0, 0 }

  28. {22,20,22,2,13,15,7,17,19,11,14,21,16,9,1,1,17,20,11,10,16,10,12,5,18,4,3,2,6,13,6,5,3,8,8,18,14,9,19,15,4,12,21,7}

    Returns: {1, 10, 54, 187, 439, 776, 1081, 1204, 1107, 846, 518, 249, 95, 29, 7, 1, 0, 0, 0, 0, 0, 0, 0 }

  29. {14,10,12,7,8,9,5,21,6,2,3,15,22,11,9,2,19,10,16,22,15,4,19,23,13,14,4,12,1,17,13,17,21,5,8,11,6,20,18,7,16,18,23,20,3,1}

    Returns: {1, 11, 56, 195, 509, 995, 1506, 1824, 1840, 1536, 1050, 593, 253, 77, 16, 3, 0, 0, 0, 0, 0, 0, 0, 0 }

  30. {9,1,5,16,2,10,17,13,5,24,14,4,12,10,22,20,11,6,19,9,3,11,7,8,15,18,12,6,22,13,21,15,2,1,8,4,16,20,17,18,23,3,19,14,21,23,7,24}

    Returns: {1, 8, 53, 191, 441, 768, 1078, 1295, 1349, 1149, 851, 539, 282, 109, 27, 5, 1, 0, 0, 0, 0, 0, 0, 0, 0 }

  31. {11,10,16,15,4,17,17,18,8,16,19,19,4,25,10,12,5,6,3,22,18,12,24,1,2,7,5,20,14,21,2,23,6,11,13,8,25,22,15,23,20,13,7,9,3,14,9,1,21,24}

    Returns: {1, 17, 102, 375, 936, 1705, 2478, 2927, 2727, 2024, 1229, 606, 244, 71, 9, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  32. {1,25,11,24,3,14,19,2,5,10,20,11,6,17,12,9,5,1,22,25,26,3,23,16,8,17,7,18,13,22,12,15,20,24,2,7,16,10,14,9,19,4,4,6,21,26,18,21,13,23,8,15}

    Returns: {1, 14, 105, 463, 1387, 3079, 5239, 6936, 7311, 6268, 4463, 2650, 1366, 672, 282, 90, 21, 5, 3, 1, 0, 0, 0, 0, 0, 0, 0 }

  33. {19,19,16,18,26,23,11,15,5,21,20,22,17,16,8,2,20,13,22,10,18,3,7,8,14,4,15,17,1,6,5,10,21,25,2,24,7,12,24,27,13,1,23,4,25,26,12,27,6,3,9,14,9,11}

    Returns: {1, 19, 131, 554, 1691, 3984, 7441, 11331, 14354, 15234, 13506, 9927, 6096, 3148, 1306, 424, 119, 25, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  34. {17,26,20,27,10,9,3,8,15,13,14,10,20,16,3,23,5,22,5,12,27,1,21,28,19,11,11,2,15,18,17,8,23,4,6,4,9,13,14,25,18,16,24,22,26,21,7,19,25,1,24,6,12,28,7,2}

    Returns: {1, 12, 70, 260, 669, 1349, 2212, 2793, 2616, 1885, 1079, 465, 148, 35, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  35. {18,12,21,28,2,10,11,17,5,14,25,16,18,14,11,4,3,10,27,13,7,20,1,2,21,8,6,16,28,22,12,15,25,6,1,13,29,24,7,20,15,26,27,17,9,8,3,26,9,29,23,19,5,23,24,4,22,19}

    Returns: {1, 9, 52, 191, 632, 1704, 3777, 7514, 12621, 17625, 20557, 19997, 16790, 12307, 7716, 4112, 1850, 706, 229, 60, 13, 2, 0, 0, 0, 0, 0, 0, 0, 0 }

  36. {23,11,13,28,29,25,17,10,7,29,30,18,1,9,16,4,27,8,28,13,27,6,15,14,2,20,30,23,24,21,10,15,17,7,19,20,14,3,1,25,26,26,6,16,12,22,19,2,4,5,24,9,12,3,11,21,5,22,8,18}

    Returns: {1, 16, 139, 692, 2326, 5991, 12642, 22101, 32563, 40789, 44374, 42897, 36757, 27517, 17733, 9712, 4492, 1804, 657, 223, 77, 21, 2, 0, 0, 0, 0, 0, 0, 0, 0 }

  37. {19,25,12,23,2,3,4,13,2,6,20,1,25,9,5,19,28,20,22,14,21,30,13,9,7,22,10,17,11,14,24,1,15,4,24,16,23,31,6,11,5,3,10,31,26,12,30,28,17,27,18,29,8,16,7,21,27,8,18,15,26,29}

    Returns: {1, 17, 102, 445, 1461, 3690, 7490, 12833, 18975, 24360, 27201, 26409, 22181, 15994, 9763, 5008, 2114, 672, 146, 18, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  38. {28,4,20,11,24,4,30,5,24,25,29,30,31,7,21,5,17,26,25,2,1,3,7,27,18,19,29,15,6,27,31,6,23,16,16,22,28,14,14,18,10,1,8,10,13,9,17,32,22,12,8,21,23,26,2,12,15,3,32,19,11,9,13,20}

    Returns: {1, 16, 145, 810, 3165, 9522, 23034, 45465, 74011, 100891, 116715, 115174, 97198, 70489, 43797, 22921, 9984, 3662, 1155, 323, 82, 15, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  39. {26,11,14,13,17,20,9,32,19,6,31,33,1,8,30,1,2,18,2,14,26,30,29,25,8,11,15,18,9,16,24,10,21,6,25,24,28,15,5,16,20,7,7,31,21,27,23,27,22,19,3,10,4,28,29,3,17,33,22,23,12,5,4,12,32,13}

    Returns: {1, 17, 140, 725, 2597, 6799, 13683, 21955, 28791, 31264, 28284, 21557, 14078, 7949, 3863, 1591, 537, 139, 24, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  40. {7,24,26,4,5,7,28,29,14,10,23,20,14,11,9,1,15,12,33,31,3,5,18,4,11,24,16,8,31,26,22,19,25,34,15,27,12,3,2,10,6,20,21,18,21,8,32,13,13,1,34,17,29,25,22,28,2,6,9,23,33,32,27,16,30,19,17,30}

    Returns: {1, 20, 161, 759, 2682, 7573, 17509, 33552, 53953, 74116, 88505, 93050, 86538, 71033, 51616, 33540, 19619, 10384, 4932, 2022, 694, 200, 44, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  41. {21,12,18,19,10,31,16,13,12,9,34,2,23,18,1,28,27,11,27,32,26,31,8,9,3,25,5,28,17,32,30,21,11,17,30,4,23,5,19,25,33,6,10,22,22,20,16,34,33,26,14,20,3,7,13,4,15,35,2,14,29,7,15,24,24,8,1,29,35,6}

    Returns: {1, 17, 136, 724, 2877, 9245, 24981, 56868, 108983, 176980, 245778, 294501, 306812, 279446, 223105, 155851, 94443, 48816, 20966, 7229, 1942, 410, 73, 11, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  42. {14,22,2,16,15,28,9,24,25,30,27,12,23,32,11,31,17,30,35,2,20,29,4,7,15,11,18,13,1,34,20,10,19,22,6,33,9,10,14,35,8,36,31,6,32,5,33,28,29,7,12,23,17,24,19,21,4,8,36,21,26,13,34,3,26,16,3,5,1,25,18,27}

    Returns: {1, 16, 111, 549, 2165, 6848, 17422, 35791, 60684, 85515, 101563, 103308, 91001, 69703, 46654, 27367, 14058, 6330, 2562, 911, 278, 65, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  43. {8,25,22,3,37,3,5,36,19,28,27,10,19,15,7,30,29,33,14,6,13,26,13,11,34,22,37,14,9,32,16,32,34,1,8,28,35,10,16,26,18,15,21,23,5,2,21,7,4,24,31,12,20,35,33,27,9,31,24,18,20,25,6,11,36,17,23,30,29,17,1,4,2,12}

    Returns: {1, 15, 114, 641, 2504, 7230, 16656, 31671, 50747, 70264, 87025, 96463, 98455, 92308, 80676, 65708, 49517, 34446, 21610, 11705, 5264, 1912, 567, 169, 26, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  44. {16,23,9,5,6,25,7,26,10,1,21,4,15,2,20,21,12,19,8,25,4,5,12,17,37,27,1,13,34,22,31,3,30,35,20,33,38,28,9,22,15,19,32,6,11,17,36,3,32,26,35,24,8,14,18,11,30,14,34,13,2,36,24,37,33,10,23,16,27,38,7,29,31,28,29,18}

    Returns: {1, 18, 158, 994, 4638, 17108, 51136, 124366, 251943, 431100, 631761, 806358, 907877, 908796, 810175, 641143, 446605, 270909, 141637, 63154, 24058, 7914, 2188, 458, 68, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  45. {16,18,26,16,19,31,17,12,4,20,23,6,24,6,3,39,35,8,26,7,21,32,14,27,9,15,25,1,13,34,9,38,18,24,28,22,37,4,32,28,11,13,17,12,33,3,39,5,27,25,1,36,31,2,37,30,38,22,20,14,10,5,36,29,10,34,23,33,19,15,30,8,2,21,29,35,11,7}

    Returns: {1, 23, 213, 1219, 5384, 19033, 54763, 130661, 263128, 454368, 678591, 881935, 1000187, 996024, 880635, 697052, 498592, 323201, 190221, 100072, 47439, 19688, 7077, 2357, 587, 136, 12, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  46. {22,21,11,3,38,1,33,23,19,19,13,30,35,12,7,35,33,24,27,39,36,16,10,5,30,6,21,15,7,37,36,17,32,29,31,2,40,9,17,31,15,24,26,28,8,10,32,16,40,29,37,2,23,28,6,25,14,11,34,20,8,26,14,12,5,34,39,18,3,27,22,18,38,25,20,1,4,13,9,4}

    Returns: {1, 22, 229, 1523, 7318, 27299, 82546, 208070, 447468, 836087, 1371924, 1984373, 2528739, 2832207, 2779045, 2382892, 1786486, 1177889, 690412, 364269, 174666, 76435, 30547, 11142, 3688, 1088, 277, 59, 10, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  47. {6,7,25,14,8,22,29,9,35,16,15,5,32,25,36,5,23,4,21,40,12,4,2,33,29,40,31,30,39,38,6,11,8,1,20,37,24,26,31,14,28,15,3,41,9,26,18,13,13,17,18,11,12,10,34,17,32,16,36,24,38,3,39,19,1,10,28,7,30,19,22,33,23,35,34,27,37,41,27,21,2,20}

    Returns: {1, 15, 142, 845, 3875, 13585, 39473, 94996, 193586, 339151, 514559, 688769, 822455, 880872, 848768, 731243, 559101, 377548, 223655, 114802, 50350, 18807, 6041, 1742, 442, 86, 16, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  48. {31,4,9,22,17,42,22,21,16,24,23,26,4,20,11,5,36,20,10,6,32,27,13,8,2,38,33,34,30,15,28,9,12,16,14,30,37,34,33,5,39,29,41,7,28,31,25,19,17,7,40,39,3,24,29,35,42,10,23,38,1,3,35,18,26,18,36,37,2,6,14,1,32,40,12,21,25,8,13,15,27,11,41,19}

    Returns: {1, 18, 165, 1035, 4451, 15670, 45978, 112870, 238998, 438349, 708041, 1014506, 1287282, 1451728, 1455847, 1297934, 1033201, 731617, 459236, 256264, 126619, 55097, 21059, 6729, 1852, 323, 47, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  49. {33,41,23,7,20,8,21,42,35,40,11,39,4,37,18,12,17,6,37,17,29,39,22,14,31,1,22,36,24,13,42,23,15,18,20,29,15,38,2,13,34,1,25,33,43,9,30,16,28,28,5,10,4,2,3,36,40,32,16,38,14,27,11,3,26,31,41,9,34,10,27,30,5,19,19,26,32,24,8,21,12,35,25,7,43,6}

    Returns: {1, 25, 270, 1819, 8721, 32422, 98575, 252260, 553606, 1055205, 1762080, 2596924, 3399775, 3971910, 4152009, 3893088, 3285596, 2503030, 1722916, 1072343, 604448, 308605, 142308, 59080, 22109, 7491, 2286, 627, 160, 38, 8, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  50. {40,2,29,9,37,24,33,1,22,11,3,14,35,32,42,19,20,25,17,31,34,41,10,33,5,4,39,25,44,12,29,23,3,11,26,19,16,5,31,43,35,17,38,18,21,4,26,38,6,42,10,34,12,30,6,41,7,2,27,9,22,30,36,13,28,15,27,18,24,39,8,43,37,44,7,23,8,15,36,14,13,20,28,16,32,21,1,40}

    Returns: {1, 18, 162, 1020, 4654, 16623, 49618, 128183, 289804, 575615, 1008480, 1562898, 2145888, 2624646, 2881923, 2860509, 2586423, 2144540, 1636591, 1154755, 756840, 461169, 260810, 136062, 64750, 27831, 10724, 3682, 1135, 304, 56, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  51. {44,8,30,37,45,37,25,29,34,25,15,32,36,17,5,38,15,21,39,41,42,13,6,12,43,4,31,3,26,40,11,31,2,21,7,22,18,45,14,14,43,24,4,39,42,34,35,16,32,1,36,19,44,29,9,17,2,23,30,1,3,27,5,23,41,28,16,26,33,11,12,19,18,35,20,7,10,40,8,24,10,33,9,22,13,6,28,20,38,27}

    Returns: {1, 23, 271, 2036, 10729, 42990, 134243, 337320, 699401, 1219991, 1817351, 2337720, 2622772, 2591755, 2277562, 1790274, 1257867, 785276, 430187, 202741, 80077, 26097, 7032, 1473, 231, 30, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  52. {42,23,24,25,32,1,12,28,15,33,3,10,30,22,33,5,8,7,24,11,4,2,30,26,13,25,21,38,20,6,18,29,41,45,41,14,3,11,2,6,44,44,35,26,40,9,43,16,19,37,45,7,22,27,31,1,15,39,21,42,8,39,18,9,28,5,34,40,16,36,14,4,32,34,43,17,23,37,13,27,19,36,35,31,38,12,17,29,46,20,46,10}

    Returns: {1, 18, 177, 1222, 6267, 26083, 90788, 269051, 689139, 1544589, 3058937, 5383006, 8437914, 11803759, 14767496, 16557476, 16673431, 15119920, 12382352, 9180107, 6173206, 3768496, 2085359, 1041978, 468486, 189620, 69194, 22617, 6544, 1631, 315, 35, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  53. {16,43,15,47,17,3,40,16,4,7,6,20,14,8,21,29,23,4,40,2,28,12,44,7,22,45,2,22,34,19,33,36,14,11,13,27,29,30,3,38,46,27,1,10,1,30,32,33,23,15,18,32,44,25,5,26,37,45,37,10,38,36,47,13,28,25,9,24,35,39,31,12,11,19,26,24,41,17,41,20,39,42,31,35,34,5,8,42,21,6,9,46,18,43}

    Returns: {1, 21, 240, 1842, 10353, 45027, 158295, 463471, 1154018, 2483977, 4677825, 7786693, 11559608, 15429739, 18689828, 20741597, 21279162, 20326838, 18175506, 15267070, 12062135, 8947298, 6196388, 3977241, 2349924, 1269546, 621179, 271681, 104760, 35004, 9910, 2294, 389, 40, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  54. {33,6,15,14,44,27,4,22,10,40,29,43,17,11,42,13,25,34,30,41,43,3,47,11,31,15,19,48,18,28,10,45,28,32,4,26,39,26,46,1,13,20,9,29,5,37,38,45,17,1,7,36,19,9,7,34,39,27,21,40,20,23,5,41,46,16,6,32,3,35,8,18,16,30,42,25,35,22,37,2,31,47,24,14,8,12,44,12,24,48,38,33,23,21,36,2}

    Returns: {1, 20, 229, 1604, 8002, 30389, 91706, 227382, 476098, 858556, 1345047, 1840507, 2215561, 2360372, 2232961, 1882627, 1418349, 956670, 577843, 311421, 148535, 62303, 23092, 7437, 2039, 442, 85, 11, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  55. {33,2,16,29,11,19,18,28,30,16,41,25,38,4,21,2,7,34,12,31,36,45,8,4,10,39,14,48,34,13,35,43,5,5,11,6,28,43,26,32,42,47,10,37,41,19,21,17,31,45,36,24,39,33,24,48,49,7,23,18,20,1,25,49,44,22,12,3,27,46,17,42,32,40,37,23,46,35,27,13,47,29,40,20,15,30,1,6,9,15,14,8,3,9,22,44,38,26}

    Returns: {1, 31, 384, 3020, 17075, 74418, 261463, 764766, 1908034, 4134554, 7889005, 13381763, 20303575, 27666469, 33937928, 37520682, 37417851, 33692776, 27415015, 20155482, 13380131, 8020332, 4341248, 2118068, 928608, 364837, 127853, 39793, 11153, 2901, 686, 141, 29, 7, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  56. {36,21,29,17,35,39,49,25,13,8,41,44,32,46,38,50,43,9,50,31,28,15,5,1,41,21,30,24,10,26,32,24,33,36,9,23,45,14,6,18,22,27,19,20,5,46,33,37,40,34,23,14,42,37,17,3,16,1,11,3,22,8,12,31,35,47,47,44,42,28,18,30,49,7,7,27,19,48,4,6,34,45,25,11,26,15,29,39,4,38,2,2,13,16,10,48,43,40,20,12}

    Returns: {1, 22, 270, 2036, 11337, 50247, 183061, 562646, 1489621, 3452347, 7096709, 13073750, 21751670, 32863364, 45242308, 56851534, 65259696, 68460464, 65650381, 57564765, 46179630, 33915120, 22803114, 14030944, 7902241, 4074803, 1921113, 825545, 322051, 113327, 35667, 9953, 2417, 493, 84, 12, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  57. {25,23,43,30,12,33,51,6,50,1,4,5,20,50,2,31,27,18,10,21,3,31,27,48,34,29,21,19,2,11,10,35,18,16,7,38,34,13,46,16,51,12,44,35,22,8,19,36,47,49,9,3,38,22,20,45,11,8,39,23,26,14,5,41,13,28,15,7,44,26,49,28,24,15,40,24,37,30,37,17,17,40,47,42,33,6,32,36,29,14,1,48,41,45,32,25,9,39,4,43,42,46}

    Returns: {1, 27, 363, 3129, 19390, 93366, 367563, 1220298, 3480641, 8628192, 18743584, 35935328, 61199551, 93141297, 127385614, 157382571, 176523499, 180583060, 169225003, 145847490, 116011170, 85414294, 58343156, 37024004, 21827446, 11938207, 6048086, 2837734, 1233621, 496229, 184267, 62953, 19531, 5365, 1292, 281, 53, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  58. {28,24,45,24,13,14,17,12,40,46,1,15,47,4,20,10,51,50,30,43,7,51,41,49,26,48,9,18,36,38,34,8,6,19,33,23,7,3,16,34,52,2,13,36,41,28,2,50,29,44,11,15,44,43,35,22,6,12,25,1,16,45,38,10,5,8,3,37,35,4,27,48,27,37,31,14,9,46,18,52,33,40,21,21,39,32,17,30,26,29,19,47,20,11,23,25,31,39,42,42,5,22,49,32}

    Returns: {1, 24, 270, 2048, 11921, 56392, 222624, 747872, 2168093, 5481198, 12181398, 23948887, 41886902, 65520156, 92086918, 116732263, 133887885, 139380689, 132145181, 114529248, 91100745, 66784939, 45323327, 28599138, 16834032, 9251821, 4736173, 2244391, 974941, 383214, 134420, 41863, 11783, 3083, 753, 169, 31, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  59. {1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24,25,25,26,26,27,27,28,28,29,29,30,30,31,31,32,32,33,33,34,34,35,35,36,36,37,37,38,38,39,39,40,40,41,41,42,42,43,43,44,44,45,45,46,46}

    Returns: {1, 46, 1035, 15180, 163185, 1370754, 9366819, 53524680, 260932815, 1101716330, 4076350421, 13340783196, 38910617655, 101766230790, 239877544005, 511738760544, 991493848554, 1749695026860, 2818953098830, 4154246671960, 5608233007146, 6943526580276, 7890371113950, 8233430727600, 7890371113950, 6943526580276, 5608233007146, 4154246671960, 2818953098830, 1749695026860, 991493848554, 511738760544, 239877544005, 101766230790, 38910617655, 13340783196, 4076350421, 1101716330, 260932815, 53524680, 9366819, 1370754, 163185, 15180, 1035, 46, 1 }

  60. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46}

    Returns: {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  61. {1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24,25,25,26,26,27,27,28,28,29,29,30,30,31,31,32,32,33,33,34,34,35,35,36,36,37,37,38,38,39,39,40,40,41,41,42,42,43,43,44,44,45,45,46,46,47,47,48,48,49,49,50,50,51,51,52,52}

    Returns: {1, 52, 1326, 22100, 270725, 2598960, 20358520, 133784560, 752538150, 3679075400, 15820024220, 60403728840, 206379406870, 635013559600, 1768966344600, 4481381406320, 10363194502115, 21945588357420, 42671977361650, 76360380541900, 125994627894135, 191991813933920, 270533919634160, 352870329957600, 426384982032100, 477551179875952, 495918532948104, 477551179875952, 426384982032100, 352870329957600, 270533919634160, 191991813933920, 125994627894135, 76360380541900, 42671977361650, 21945588357420, 10363194502115, 4481381406320, 1768966344600, 635013559600, 206379406870, 60403728840, 15820024220, 3679075400, 752538150, 133784560, 20358520, 2598960, 270725, 22100, 1326, 52, 1 }

  62. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52}

    Returns: {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  63. {1, 2, 2, 1}

    Returns: {1, 2, 1 }

  64. {41, 52, 12, 18, 25, 36, 18, 37, 27, 50, 16, 40, 32, 3, 24, 5, 8, 19, 33, 41, 40, 35, 6, 13, 15, 43, 28, 11, 12, 7, 31, 45, 14, 17, 4, 36, 20, 51, 10, 23, 15, 29, 52, 28, 38, 30, 22, 1, 43, 42, 37, 29, 1, 44, 17, 9, 50, 49, 33, 21, 30, 10, 7, 46, 2, 25, 9, 34, 38, 16, 26, 4, 19, 32, 31, 48, 49, 11, 39, 35, 24, 23, 26, 20, 34, 45, 42, 3, 46, 2, 39, 44, 5, 22, 48, 6, 27, 14, 51, 47, 8, 47, 13, 21 }

    Returns: {1, 32, 416, 3756, 24348, 121601, 494485, 1688395, 4934342, 12537807, 28036991, 55691013, 98984594, 158421949, 229511439, 302233678, 362929639, 398358898, 400196067, 368230926, 310410815, 239752844, 169669383, 110041854, 65434102, 35695767, 17859718, 8196183, 3450661, 1330567, 469055, 150326, 43644, 11431, 2691, 630, 143, 27, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

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: