Statistics

Problem Statement for "CountPaths"

Problem Statement

There is a rectangular table divided into r rows and c columns, for a total of r * c fields. The rows are numbered 1 to r, from bottom to top, and the columns are numbered 1 to c, from left to right. All coordinates in this problem will be given as (row, column).


You are given int[]s fieldrow and fieldcol containing a list of special fields in the table, where (fieldrow[i], fieldcol[i]) are the coordinates of the i-th field. For each number n, where 0 <= n <= the number of elements in fieldrow, you must count the number of different paths from field (1, 1) to field (r, c) that contain exactly n special fields. These paths are called paths of length n.


There are two rules you must follow. First, you are only allowed to make moves that are straight up or to the right. In other words, from each field (row, column), you can only move to field (row+1, column) or field (row, column+1). Second, in each path, all the special fields must appear in the same order that they appear in the input. In other words, if the path contains field a = (fieldrow[idxa], fieldcol[idxa]) and field b = (fieldrow[idxb], fieldcol[idxb]), and a appears before b in the path, then idxa must be less than idxb.


Return a int[] containing exactly k+1 elements, where k is the number of elements in fieldrow. The i-th element (0-indexed) must be the number of different paths of length i modulo 1000007.

Definition

Class:
CountPaths
Method:
difPaths
Parameters:
int, int, int[], int[]
Returns:
int[]
Method signature:
int[] difPaths(int r, int c, int[] fieldrow, int[] fieldcol)
(be sure your method is public)

Constraints

  • r and c will each be between 1 and 50, inclusive.
  • fieldrow will contain between 0 and 50 elements, inclusive.
  • fieldcol and fieldrow will contain same number of elements.
  • Each element of fieldrow will be between 1 and r, inclusive.
  • Each element of fieldcol will be between 1 and c, inclusive.
  • For all i and j, where i < j, the pairs (fieldrow[i], fieldcol[i]) and (fieldrow[j], fieldcol[j]) will be different.

Examples

  1. 3

    3

    {2, 3}

    {2, 2}

    Returns: {1, 3, 2 }

    Path of length 0: (1, 1) -> (1, 2) -> (1, 3) -> (2, 3) -> (3, 3) Paths of length 1: (1, 1) -> (2, 1) -> (2, 2) -> (2, 3) -> (3, 3) (1, 1) -> (1, 2) -> (2, 2) -> (2, 3) -> (3, 3) (1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3) Paths of length 2: (1, 1) -> (2, 1) -> (2, 2) -> (3, 2) -> (3, 3) (1, 1) -> (1, 2) -> (2, 2) -> (3, 2) -> (3, 3)

  2. 6

    4

    {3, 5}

    {2, 3}

    Returns: {14, 24, 18 }

  3. 6

    4

    {5, 3}

    {3, 2}

    Returns: {14, 24, 0 }

  4. 30

    30

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

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

    Returns: {0, 980196, 492851, 420437, 242629, 75394, 25153, 54279, 263790, 360516, 177345, 686437, 258400, 451652, 248564, 573042, 12035, 194248, 726779, 353374, 901839, 620764, 524091, 981772, 709090, 280008, 568983, 170599, 253917, 439999, 606924, 716612, 242394, 153622, 418219, 323651, 336646, 410897, 424702, 786576, 24281, 562034, 94208, 0, 0, 0, 0, 0, 0, 0, 0 }

  5. 5

    5

    {1, 2, 3}

    {3, 4, 5}

    Returns: {42, 14, 10, 4 }

  6. 8

    8

    {1, 2, 5, 5, 6, 7, 8, 8}

    {3, 4, 5, 6, 7, 7, 7, 8}

    Returns: {0, 63, 767, 843, 775, 574, 308, 86, 16 }

  7. 25

    35

    {14, 17, 24, 9, 5, 1, 21, 25, 15, 15, 15, 9, 18, 18, 6, 11, 4}

    {20, 11, 2, 18, 1, 30, 15, 15, 17, 27, 25, 14, 12, 30, 14, 11, 35}

    Returns: {52340, 454768, 685027, 726633, 38057, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  8. 11

    9

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

    {8, 9, 9, 8, 1, 7, 7, 6, 9, 6, 3, 1, 9, 4, 7}

    Returns: {9358, 18900, 5955, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  9. 31

    33

    {16, 15, 19, 19, 25, 19, 16, 24, 31, 6, 30, 31, 9, 10, 23, 7, 15, 14, 16, 2, 17}

    {8, 13, 13, 9, 9, 31, 1, 18, 16, 22, 31, 21, 24, 13, 2, 23, 22, 17, 25, 8, 24}

    Returns: {868541, 491090, 726643, 605443, 345038, 544050, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  10. 23

    48

    {5, 18, 18, 1, 1, 16, 7, 18, 7, 1, 14, 8, 14, 11}

    {48, 32, 46, 13, 6, 11, 39, 12, 9, 24, 12, 21, 14, 8}

    Returns: {662438, 969822, 262493, 752237, 342978, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  11. 35

    37

    {3, 28, 28, 27, 27, 5, 15, 23, 21, 3, 8, 25, 34, 31, 33, 35, 13, 34}

    {12, 34, 3, 9, 34, 3, 18, 17, 26, 5, 23, 14, 20, 7, 3, 20, 19, 23}

    Returns: {830519, 709835, 755976, 219563, 868547, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  12. 6

    39

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

    {6, 14, 31, 4, 20, 34, 29, 28, 22, 20, 5, 36, 14, 24, 12, 6, 5, 10}

    Returns: {2850, 115537, 43329, 4320, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  13. 50

    24

    {17, 36, 29, 31, 10, 48, 1, 3, 20, 23, 48, 24, 25, 18, 12, 17, 18, 45, 36, 8, 36, 22, 38, 48, 14, 17, 47, 42, 23, 47}

    {18, 20, 8, 6, 20, 16, 1, 13, 17, 10, 2, 10, 13, 5, 8, 9, 14, 4, 5, 16, 17, 16, 7, 18, 20, 6, 15, 6, 5, 13}

    Returns: {0, 701755, 670229, 160764, 499858, 898766, 64080, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  14. 1

    42

    {1, 1, 1, 1, 1, 1, 1}

    {29, 23, 19, 10, 34, 4, 24}

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

  15. 29

    7

    {14, 2, 4, 14, 4, 19, 23, 21, 17, 23, 27, 23, 9, 12, 15, 16, 5, 22, 9, 18, 2, 1, 19, 26, 7, 2, 8, 1, 3, 25, 19, 23, 7, 2, 17, 22, 9, 8, 22, 6}

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

    Returns: {0, 0, 720, 2416, 716, 152, 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 }

  16. 11

    3

    {1, 11, 10, 5, 9, 6, 1, 5, 9, 3, 8, 8, 8, 11, 7, 1}

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

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

  17. 16

    11

    {13, 9, 10, 10, 9, 13, 1, 8, 15, 10}

    {4, 10, 11, 6, 2, 2, 3, 10, 4, 8}

    Returns: {27666, 638801, 317003, 360, 0, 0, 0, 0, 0, 0, 0 }

  18. 1

    26

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

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

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

  19. 18

    16

    {18, 16, 2, 1, 9, 18, 15, 6}

    {1, 9, 1, 12, 4, 4, 2, 6}

    Returns: {911376, 679422, 35457, 120, 0, 0, 0, 0, 0 }

  20. 29

    29

    {23, 22, 24, 14, 16, 13, 11, 7, 18, 9, 18, 9, 27, 22, 24}

    {29, 17, 1, 9, 29, 24, 17, 21, 3, 21, 25, 9, 26, 13, 2}

    Returns: {828166, 505212, 839676, 280386, 533618, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  21. 6

    16

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

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

    Returns: {0, 0, 0, 6, 10, 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 }

  22. 24

    22

    {12, 19, 1, 15, 19, 7, 24, 9, 1, 18, 12, 22}

    {10, 9, 11, 6, 15, 12, 19, 15, 7, 9, 18, 20}

    Returns: {437047, 696174, 299603, 170592, 582199, 0, 0, 0, 0, 0, 0, 0, 0 }

  23. 15

    44

    {4, 15, 4, 14, 7, 4, 15, 15, 7, 7, 13, 5, 6, 5, 5}

    {21, 41, 11, 23, 27, 32, 40, 31, 3, 23, 24, 35, 7, 9, 11}

    Returns: {240003, 721554, 366451, 925197, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  24. 41

    46

    {17, 34, 12, 17, 18, 5, 41, 30, 7, 26, 36, 15, 5, 35, 40, 37, 10}

    {21, 44, 39, 44, 16, 25, 31, 8, 32, 40, 4, 31, 43, 14, 2, 35, 45}

    Returns: {146298, 479355, 179906, 43024, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  25. 23

    30

    {4, 2}

    {19, 11}

    Returns: {934294, 535717, 0 }

  26. 30

    28

    {26, 19, 11, 19, 30, 26, 9, 15, 1, 15, 15}

    {8, 13, 20, 21, 2, 10, 21, 10, 15, 1, 20}

    Returns: {966293, 466840, 946426, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  27. 50

    50

    {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}

    {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}

    Returns: {351538, 896709, 192270, 783406, 838564, 627763, 213005, 718301, 650731, 101906, 553819, 490519, 88703, 820109, 240589, 515746, 97458, 162367, 958738, 422881, 505263, 302773, 512554, 30814, 469206, 96188, 586981, 447904, 510153, 449355, 701858, 594049, 465410, 993621, 580434, 102916, 937164, 253231, 72870, 831654, 790629, 805098, 724478, 542039, 992612, 85115, 288724, 625008, 766470, 596994, 951461 }

  28. 50

    50

    {1, 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}

    {2, 1, 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}

    Returns: {0, 518607, 300150, 152424, 285070, 667406, 619034, 324713, 997629, 194639, 408496, 26373, 622745, 637278, 82991, 249067, 619040, 914211, 1764, 417990, 150170, 151046, 854651, 737569, 187062, 910503, 849825, 273534, 891276, 86350, 808244, 178987, 86671, 997343, 874307, 803610, 247952, 615039, 141920, 833466, 703627, 314476, 806548, 921678, 175102, 688750, 248008, 848453, 57971, 854369, 0 }

  29. 10

    10

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

    {3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2}

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

  30. 4

    4

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

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

    Returns: {0, 0, 0, 0, 0, 0, 0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  31. 5

    10

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

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

    Returns: {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 715, 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 }

  32. 10

    10

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

    {3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2}

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

  33. 30

    30

    {}

    {}

    Returns: {148830 }

  34. 1

    1

    {}

    {}

    Returns: {1 }

  35. 1

    1

    {1}

    {1}

    Returns: {0, 1 }

  36. 50

    50

    {}

    {}

    Returns: {337966 }

  37. 50

    50

    {50, 1}

    {50, 1}

    Returns: {0, 0, 0 }

    There is no path that passes through (50, 50) before (1, 1).

  38. 35

    37

    {3, 28, 28, 27, 27, 5, 15, 23, 21, 3, 8, 25, 34, 31, 33, 35, 13, 34 }

    {12, 34, 3, 9, 34, 3, 18, 17, 26, 5, 23, 14, 20, 7, 3, 20, 19, 23 }

    Returns: {830519, 709835, 755976, 219563, 868547, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  39. 50

    50

    {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 }

    {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 }

    Returns: {0, 0, 292146, 584292, 804054, 879048, 450457, 586612, 980113, 112114, 99354, 403390, 87479, 473344, 207211, 729737, 924463, 677898, 503550, 897128, 117307, 443166, 23229, 175827, 125077, 490071, 92800, 397677, 944704, 534325, 793382, 959465, 552363, 967904, 952882, 915124, 644670, 9135, 143347, 296728, 993134, 50620, 911128, 583747, 376372, 382743, 916916, 99754, 771587, 181339, 799228 }

  40. 3

    3

    { }

    { }

    Returns: {6 }

  41. 50

    50

    {46, 9, 24, 20, 42, 47, 16, 1, 5, 1, 22, 20, 22, 27, 8, 26, 27, 22, 2, 43, 1, 19, 46, 23, 34, 28, 14, 26, 44, 47, 45, 24, 23, 7, 20, 4, 12, 50, 39, 29, 47, 47, 11, 50, 16, 33, 26, 38, 36, 46 }

    {16, 2, 12, 36, 5, 45, 13, 1, 12, 8, 48, 3, 23, 7, 6, 30, 50, 31, 29, 13, 29, 47, 20, 33, 31, 38, 19, 26, 41, 34, 47, 40, 5, 7, 24, 41, 10, 31, 47, 22, 17, 16, 35, 50, 7, 42, 29, 16, 23, 38 }

    Returns: {0, 0, 522192, 463544, 984180, 622678, 570327, 768380, 678656, 547090, 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 }

  42. 50

    49

    {21, 21, 3, 5, 1, 1, 35, 3, 5, 13, 5, 23, 25, 17, 5, 32, 5, 43, 13, 12, 34, 23, 4, 23, 44, 23, 1, 12, 3, 12, 3, 12, 3, 12, 3, 12, 4, 2, 1, 4, 23, 4, 8, 18, 19, 39, 36, 49, 49, 22 }

    {8, 35, 43, 5, 1, 4, 45, 3, 24, 6, 11, 14, 29, 5, 12, 43, 31, 43, 5, 21, 34, 1, 2, 43, 5, 12, 33, 5, 31, 9, 5, 1, 4, 8, 21, 36, 6, 43, 7, 5, 48, 47, 8, 44, 49, 34, 25, 1, 49, 22 }

    Returns: {0, 851243, 221907, 560734, 395039, 234067, 340542, 201791, 286731, 671574, 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 }

  43. 1

    1

    {1 }

    {1 }

    Returns: {0, 1 }

  44. 4

    4

    {1, 4, 2 }

    {1, 4, 2 }

    Returns: {0, 0, 8, 0 }

  45. 50

    50

    {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 }

    {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 }

    Returns: {0, 292146, 584292, 804054, 879048, 450457, 586612, 980113, 112114, 99354, 403390, 87479, 473344, 207211, 729737, 924463, 677898, 503550, 897128, 117307, 443166, 23229, 175827, 125077, 490071, 92800, 397677, 944704, 534325, 793382, 959465, 552363, 967904, 952882, 915124, 644670, 9135, 143347, 296728, 993134, 50620, 911128, 583747, 376372, 382743, 916916, 99754, 771587, 181339, 799228 }

  46. 2

    2

    {2 }

    {2 }

    Returns: {0, 2 }

  47. 50

    50

    {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 }

    {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, 49 }

    Returns: {0, 146073, 438219, 694173, 841551, 164749, 18531, 283359, 46110, 105734, 251372, 745438, 780415, 840281, 468474, 827100, 301177, 590724, 700339, 7214, 780240, 733201, 99528, 150452, 307574, 791439, 745242, 171187, 239511, 163850, 376420, 755914, 260130, 960393, 934003, 779897, 826906, 76241, 720041, 644931, 521877, 480874, 247434, 980063, 879561, 149826, 508335, 935674, 476463, 990287, 399614 }

  48. 50

    50

    {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 }

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

    Returns: {0, 0, 730481, 676106, 625654, 953957, 41023, 845862, 494543, 163371, 190873, 603950, 429619, 418989, 870920, 242268, 906627, 459584, 379678, 134582, 470778, 285155, 587033, 180928, 358150, 475658, 829458, 304790, 926202, 532498, 26622, 604795, 733004, 343360, 274427, 820787, 417455, 947662, 307864, 181540, 331296, 502947, 564745, 576810, 614143, 147822, 498360, 716549, 423975, 585813, 599421 }

  49. 5

    5

    {2, 3, 4, 1 }

    {2, 3, 4, 1 }

    Returns: {0, 10, 0, 0, 0 }

  50. 50

    50

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

    {1, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 50, 48, 46, 44, 42, 40, 38, 36, 34, 32, 30, 28, 26, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2 }

    Returns: {0, 0, 655172, 27281, 512393, 123531, 747409, 630529, 966376, 242339, 63041, 891715, 313816, 295447, 109644, 256248, 141233, 823447, 383116, 767117, 751805, 191922, 65258, 388189, 610300, 994005, 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 }

  51. 5

    5

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

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

    Returns: {0, 0, 0, 0, 0, 0, 0, 0, 0, 70, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  52. 10

    10

    {1 }

    {1 }

    Returns: {0, 48620 }

  53. 50

    50

    {1, 3, 4, 5, 34, 45, 13, 32, 43, 42, 34, 50, 33, 45, 13, 14, 15, 16, 17, 12, 23, 24, 25, 26, 27, 34, 35, 35, 36, 47, 5, 4, 3, 2, 1, 47, 5, 22, 11, 12, 12, 13, 14, 15, 16, 17, 27, 45, 6, 43 }

    {45, 13, 32, 43, 42, 34, 50, 11, 12, 13, 14, 15, 16, 17, 12, 23, 24, 25, 26, 27, 34, 35, 35, 36, 47, 5, 4, 3, 2, 1, 47, 5, 22, 11, 12, 12, 13, 14, 15, 16, 17, 27, 45, 6, 23, 1, 3, 4, 5, 34 }

    Returns: {732757, 590083, 242579, 535397, 432745, 321379, 369330, 474832, 564823, 305813, 194703, 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 }

  54. 3

    3

    {1, 2 }

    {1, 2 }

    Returns: {0, 2, 4 }

  55. 3

    3

    {3, 2 }

    {3, 2 }

    Returns: {0, 2, 0 }

  56. 50

    49

    {1, 1, 2, 3, 3, 4, 6, 8, 8, 9, 11, 12, 14, 15, 15, 17, 18, 19, 20, 22, 23, 25, 26, 27, 29, 29, 29, 31, 32, 35, 35, 39, 39, 39, 40, 40, 42, 44, 49, 49, 6, 48, 32, 17, 47, 42, 19, 25, 50, 33 }

    {1, 8, 40, 34, 39, 1, 3, 4, 5, 6, 10, 11, 13, 16, 17, 20, 20, 21, 22, 22, 23, 23, 24, 24, 24, 25, 26, 28, 28, 29, 32, 33, 34, 35, 36, 38, 38, 42, 42, 43, 44, 44, 44, 45, 49, 26, 18, 37, 49, 12 }

    Returns: {0, 0, 714538, 441026, 648997, 628023, 267692, 387530, 965290, 144324, 216420, 245742, 820722, 967647, 34316, 132600, 646346, 363238, 797320, 135831, 953795, 633631, 829107, 890755, 924070, 230144, 453473, 457724, 950697, 429929, 894405, 315243, 98854, 445003, 859486, 829040, 315505, 708444, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  57. 50

    50

    {40, 5, 28, 24, 22, 25, 21, 28, 48, 37, 12, 6, 6, 32, 1, 42, 17, 8, 8, 4, 46, 10, 22, 23, 7, 14, 1, 13, 11, 25, 49, 46, 3, 42, 25, 47, 49, 19, 32, 4, 19, 1, 28, 29, 8, 11, 14, 10, 36, 1 }

    {9, 31, 7, 37, 46, 23, 30, 24, 13, 41, 37, 18, 25, 3, 1, 25, 31, 42, 38, 34, 10, 9, 39, 47, 31, 19, 42, 6, 10, 38, 34, 42, 1, 37, 21, 22, 50, 35, 35, 50, 39, 39, 18, 44, 22, 18, 15, 17, 2, 50 }

    Returns: {0, 696112, 702048, 753112, 821323, 380579, 113855, 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 }

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: