Statistics

Problem Statement for "Visitors"

Problem Statement

Patrik runs a local game store. Recently, a flood damaged their records and he is now trying to reconstruct them from pieces of information he recovered.

You are given all the information Patrik has: a int[] visitors. For each i, visitors[i] is the number of unique people who took part in exactly i events that occurred in the store this year. The events occurred sequentially with no overlaps. Each event had one or more participants. Note that Patrik doesn't know the actual number of events that occurred.

Two schedules are different if they have a different number of events. Two schedules are also different if they have the same number of events, but for some i the i-th event (in chronological order) in the first schedule and the i-th event in the second schedule have a different set of participants.

Count all valid schedules and return their count modulo (10^9 + 7).

Definition

Class:
Visitors
Method:
countSchedules
Parameters:
int[]
Returns:
int
Method signature:
int countSchedules(int[] visitors)
(be sure your method is public)

Constraints

  • visitors will contain between 2 and 50 elements, inclusive.
  • Each element of visitors will be between 0 and 50, inclusive.
  • visitors[0] will be 0.
  • The sum of visitors will be positive.
  • The sum of i * visitors[i] will not exceed 3000.

Examples

  1. {0,1}

    Returns: 1

    There was a single person and they visited the store once. There is only one valid schedule: there was one event and the person took part in that event.

  2. {0,0,0,1}

    Returns: 1

    Again, there is only one valid schedule: there were three events and the only visitor attended each of them.

  3. {0,3}

    Returns: 13

    There were three people (A, B, C) who attended one event each. One valid schedule is that A attended event 1, then C attended event 2, and then B attended event 3. Another valid schedule is that B attended event 1, A attended event 2, and C attended event 3. Yet another valid schedule: A and C attended event 1 and then B attended event 2.

  4. {0,1,1}

    Returns: 5

    Note that the schedule in which A attends event 1 and then B attends events 2 and 3 is different from the schedule in which B attends event 1, then A attends event 2, and then B attends event 3.

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

    Returns: 119998118

    Don't forget to use the modular arithmetic.

  6. {0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,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,11,50 }

    Returns: 707233733

  7. {0,47,50,50,50,50,50,50,50,50,50,23}

    Returns: 560846601

  8. {0, 0, 15, 0, 29, 27, 16, 0, 23, 12, 25, 0, 0, 15, 12, 0, 0, 15, 9, 0, 12, 22, 0, 26}

    Returns: 328121394

  9. {0, 0, 8, 0, 0, 12, 11, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 28, 0, 0, 0, 0, 5, 0, 0, 0, 10, 0, 0, 14, 7, 0, 0, 12, 0, 0, 10, 0, 0}

    Returns: 291626328

  10. {0, 0, 0, 0, 15, 0, 16, 0, 0, 2, 0, 11, 0, 6, 0, 3, 2, 14, 16, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 14, 0, 0, 6, 0, 12, 0, 0, 0, 0, 0, 0, 17, 0, 2}

    Returns: 105191764

  11. {0, 45, 40, 3, 12, 14, 41, 1, 11, 13, 39, 30, 42, 16}

    Returns: 214754921

  12. {0, 14, 18, 38, 13, 36, 47}

    Returns: 276685330

  13. {0, 22, 34, 2, 22, 5, 49, 35, 8, 15, 31, 38, 43, 41}

    Returns: 912219222

  14. {0, 31, 9, 22, 21, 0, 2, 31, 8, 8, 20, 44, 0, 27, 37, 30, 27}

    Returns: 987926593

  15. {0, 41, 7, 35, 24, 39, 28, 24, 7, 38, 27, 20, 9, 8, 3, 33, 36}

    Returns: 745510286

  16. {0, 13, 16, 0, 18, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 11, 0, 0, 0, 0, 0, 0, 0, 0, 6, 5, 0, 15, 14, 8, 5, 0}

    Returns: 950732081

  17. {0, 19, 25, 24, 21}

    Returns: 396423348

  18. {0, 42, 3, 9, 17, 20, 15, 39, 1, 17, 36, 11, 16, 13, 26, 44, 9, 13}

    Returns: 184133606

  19. {0, 5, 0, 0, 0, 0, 2, 8, 0, 0, 0, 11, 0, 0, 0, 0, 10, 0, 2, 0, 4, 14, 10, 7, 10, 0, 0, 0, 5, 0, 20, 21, 0, 0, 0, 6}

    Returns: 394377708

  20. {0, 0, 10, 16, 3, 19, 16, 0, 0, 11, 13, 0, 4, 8, 0, 5, 0, 0, 5, 4, 13, 12, 9, 4, 17, 0, 0, 0, 3, 0, 0, 10, 9, 0, 0, 6}

    Returns: 647744711

  21. {0, 0, 0, 17, 0, 0, 16, 0, 1, 0, 19, 10, 14, 12, 16, 0, 21, 0, 0, 18, 0, 2, 0, 15, 0, 0, 0, 0, 17, 0, 0, 0, 14, 0, 0}

    Returns: 780553403

  22. {0, 14, 17, 0, 23, 10, 0, 0, 26, 0, 17, 11, 0, 0, 0, 0, 0, 0, 15, 0, 0, 9, 0, 10, 14, 0, 0, 4, 0, 0, 14, 0, 10, 13}

    Returns: 952692091

  23. {0, 5, 9, 16, 12, 3, 0, 9, 0, 0, 0, 22, 0, 23, 18, 0, 0, 0, 13, 0, 0, 7, 2, 2, 0, 0, 0, 0, 11, 21, 0, 0, 0, 0, 18, 0}

    Returns: 462244934

  24. {0, 20, 0, 0, 0, 0, 0, 0, 0, 8, 13, 0, 15, 0, 16, 0, 0, 0, 0, 0, 0, 0, 22, 0, 16, 0, 0, 0, 17, 0, 0, 0, 0, 0, 0, 12, 0, 0, 6, 0, 0, 0, 9}

    Returns: 574803088

  25. {0, 4, 20, 12, 0, 4, 7, 19, 0, 34, 16, 0, 20, 8, 0, 0, 0, 0, 12, 0, 0, 14, 0, 0, 4, 9, 0, 0, 0, 11, 0, 1, 0, 0, 7, 14, 0, 0, 0, 0, 0, 0}

    Returns: 201510271

  26. {0, 21, 11, 18, 10, 1, 35, 45}

    Returns: 857613342

  27. {0, 0, 1, 17, 0, 2, 25, 0, 0, 0, 25, 14, 16, 22, 22, 0, 0, 9, 16, 0, 0, 0, 0, 31, 0, 0, 17, 0}

    Returns: 832203773

  28. {0, 0, 18, 0, 29, 0, 0, 0, 7, 0, 0, 0, 0, 0, 12, 6, 0, 15, 3, 0, 0, 0, 1, 16, 0, 19, 14, 0, 0, 19, 0, 14}

    Returns: 973707483

  29. {0, 11, 0, 0, 0, 19, 1, 11, 1, 0, 0, 0, 0, 0, 5, 12, 21, 0, 23, 14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 17, 12, 0, 0, 15, 0}

    Returns: 719586427

  30. {0, 2, 0, 4, 0, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 1, 22, 0, 0, 23, 7, 0, 26, 0, 0, 0, 14, 0, 0, 0, 0, 20}

    Returns: 551820632

  31. {0, 35, 40, 2, 6, 16, 29, 27, 0, 34, 14, 0, 30, 24, 19, 1, 30, 8, 17, 0, 0, 4}

    Returns: 19957860

  32. {0, 42, 45, 46, 27, 0}

    Returns: 722730741

  33. {0, 0, 24, 0, 0, 0, 12, 1, 0, 7, 0, 12, 22, 0, 27, 8, 3, 0, 0, 0, 9, 0, 17, 0, 0, 0, 6, 3, 0, 0, 14, 21, 0, 0}

    Returns: 407000947

  34. {0, 0, 6, 2, 2, 0, 0, 14, 0, 0, 4, 7, 0, 0, 2, 0, 10, 0, 0, 0, 6, 0, 14, 3, 0, 0, 0, 16, 0, 0, 0, 1, 0, 19, 0, 0, 7, 0, 19}

    Returns: 668089325

  35. {0, 0, 0, 0, 0, 13, 19, 10, 8, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 11, 0, 0, 0, 0, 0, 0, 0, 10, 0, 0, 0, 18, 0, 0, 2, 0, 6, 12, 0, 12, 0, 0, 0, 0, 4}

    Returns: 144695583

  36. {0, 16, 5, 9, 20, 30, 17, 17, 0, 29, 0, 22, 0, 0, 22, 11, 3, 0, 10, 0, 8, 0, 0, 4, 16, 9, 16, 0}

    Returns: 398518496

  37. {0, 1, 16, 26, 28, 4}

    Returns: 480150874

  38. {0, 6, 0, 24, 1, 0, 0, 29, 0, 4, 0, 21, 0, 14, 0, 0, 0, 0, 7, 19, 17, 10, 0, 16, 11, 0, 0, 0, 21, 0, 0, 0}

    Returns: 470147796

  39. {0, 24, 46, 20, 47, 50, 17, 26, 15, 43, 33, 49, 46, 12}

    Returns: 706092565

  40. {0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 13, 0, 3, 0, 0, 1, 0, 0, 0, 0, 14, 0, 7, 18, 0, 0, 20, 1, 16, 0, 0, 0, 13, 0}

    Returns: 916633412

  41. {0, 0, 4, 13, 0, 15, 0, 0, 0, 0, 0, 3, 13, 0, 0, 0, 0, 8, 0, 2, 13, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 12, 0, 0, 8, 19, 0, 14, 0, 0, 7}

    Returns: 920452864

  42. {0, 0, 0, 0, 0, 16, 0, 0, 0, 9, 17, 14, 3, 0, 10, 0, 7, 0, 0, 0, 19, 18, 5, 9, 0, 0, 0, 11, 6, 5, 6, 0, 0, 1, 0, 9}

    Returns: 510871560

  43. {0, 0, 0, 0, 11, 0, 17, 0, 22, 18, 3, 0, 0, 1, 0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 22, 9, 21, 0, 16, 7, 0, 1}

    Returns: 409199301

  44. {0, 0, 33, 31, 0, 0, 0, 0, 1, 22, 12, 33, 16, 2, 0, 0, 3, 0, 0, 14, 32, 6, 29, 0, 0, 8}

    Returns: 283890886

  45. {0, 22, 28, 34, 50, 26, 5, 28, 50}

    Returns: 539044234

  46. {0, 0, 0, 0, 0, 0, 0, 11, 5, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 18, 5, 7, 0, 0, 0, 0, 0, 0, 0, 0, 2, 12, 7, 0, 0, 0, 12, 0, 15}

    Returns: 580150370

  47. {0, 46, 14, 1, 38, 18, 7, 2, 2, 37, 38, 20, 42, 47, 14, 13, 10}

    Returns: 971151304

  48. {0, 29, 48}

    Returns: 199506731

  49. {0, 5, 23, 0, 4, 0, 12, 0, 21, 29, 8, 0, 0, 21, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 22, 0, 0, 2, 0, 0, 2, 0, 0, 0, 20, 2, 7, 0}

    Returns: 784582860

  50. {0, 40, 1, 46, 44}

    Returns: 413615422

  51. {0, 0, 0, 0, 0, 0, 0, 1, 1, 21, 0, 0, 1, 7, 13, 0, 4, 0, 0, 0, 0, 0, 18, 0, 0, 0, 23, 0, 13, 7, 0, 7, 9, 0, 0, 0, 0, 0, 10}

    Returns: 59549076

  52. {0, 0, 0, 2, 0, 0, 21, 4, 0, 0, 0, 0, 0, 0, 7, 0, 0, 8, 2, 7, 0, 0, 4, 0, 0, 0, 1, 17, 0, 20, 0, 0, 0, 0, 8, 1, 0, 6, 0, 0, 0, 18, 0, 0, 0}

    Returns: 485908108

  53. {0, 24, 0, 0, 0, 7, 0, 0, 5, 0, 15, 0, 8, 0, 16, 0, 0, 5, 25, 22, 0, 12, 8, 22, 0, 8, 13}

    Returns: 885333846

  54. {0, 0, 0, 0, 0, 14, 22, 29, 22, 0, 0, 24, 15, 41, 11, 29, 36, 0, 15, 0}

    Returns: 344048341

  55. {0, 0, 35, 21, 15, 0, 9, 31, 11, 0, 0, 16, 13, 23, 0, 33, 3, 11, 14, 6, 0, 0, 4, 0, 26}

    Returns: 208139320

  56. {0, 19, 31, 35}

    Returns: 225381555

  57. {0, 25, 26, 10, 1, 2, 0, 0, 0, 24, 0, 0, 0, 4, 11, 0, 0, 0, 13, 16, 13, 0, 18, 0, 17, 0, 0, 8, 3, 19}

    Returns: 375980103

  58. {0, 16, 4, 24, 10, 0, 0, 0, 0, 10, 0, 0, 7, 25, 14, 0, 0, 0, 0, 15, 0, 0, 30, 16, 0, 14, 3, 0, 15, 0}

    Returns: 88134120

  59. {0, 21, 18, 0, 4, 0, 0, 0, 7, 0, 11, 0, 0, 15, 0, 0, 0, 0, 0, 0, 16, 0, 0, 15, 0, 10, 0, 0, 0, 18, 0, 0, 5, 24, 0, 5, 0, 0, 0, 0, 0, 0}

    Returns: 127453771

  60. {0, 0, 20, 4, 23, 23, 25, 33, 25, 8, 48, 39, 3, 28, 39}

    Returns: 101834408

  61. {0, 45, 27, 33, 5, 45, 5, 30}

    Returns: 41891042

  62. {0, 7, 19, 35, 50, 36, 12}

    Returns: 852126283

  63. {0, 0, 0, 0, 4, 0, 9, 0, 0, 19, 0, 0, 0, 13, 32, 0, 9, 0, 22, 0, 27, 0, 17, 29, 0}

    Returns: 204444407

  64. {0, 0, 0, 0, 31, 3, 12, 20, 28, 6, 36, 0, 0, 23, 28, 17, 10, 9, 0, 0, 0, 17, 0, 14, 3}

    Returns: 544717437

  65. {0, 9, 0, 12, 0, 0, 0, 0, 4, 0, 0, 0, 0, 1, 21, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 17, 0, 5, 0, 13, 0, 0, 6, 0, 0, 5, 2, 0, 0, 5, 8, 9, 0, 0, 1}

    Returns: 869233158

  66. {0, 0, 0, 0, 0, 13, 0, 0, 0, 0, 0, 13, 15, 0, 0, 0, 24, 0, 0, 0, 0, 0, 10, 0, 0, 11, 0, 12, 0, 7, 0, 4, 13, 0, 0, 19}

    Returns: 175913862

  67. {0, 17, 19, 14, 0, 8, 0, 0, 26, 0, 0, 7, 11, 0, 3, 0, 0, 0, 30, 3, 0, 33, 22, 27}

    Returns: 685675031

  68. {0, 31, 37, 40, 31, 20, 40}

    Returns: 746162290

  69. {0, 10, 11, 3, 22, 4, 3, 14, 7, 9, 20, 0, 30, 6, 24, 0, 0, 0, 0, 20, 11, 32, 16, 0}

    Returns: 65886931

  70. {0, 42, 35, 10, 44, 43, 0, 34}

    Returns: 318578980

  71. {0, 30, 11, 3, 13}

    Returns: 341412171

  72. {0, 0, 0, 0, 0, 24, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 3, 4, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 14, 11, 0, 10, 21, 0}

    Returns: 280013780

  73. {0, 37, 37, 30, 30, 47, 32, 11, 23, 12, 23, 47, 16, 10}

    Returns: 185942853

  74. {0, 33, 0, 16, 6, 22, 7, 38, 30, 34, 37, 1, 18, 42}

    Returns: 584774706

  75. {0, 45, 47, 31, 1, 17, 44, 28, 15, 39, 22, 8}

    Returns: 305966761

  76. {0, 18, 1, 1}

    Returns: 184191949

  77. {0, 0, 0, 0, 0, 0, 5, 5, 0, 0, 5, 0, 26, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 2, 13, 10, 0, 0, 3, 0, 0, 0, 0, 0, 15, 8, 8, 11, 0, 0, 0, 0, 0, 8, 0}

    Returns: 952814822

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: