Statistics

Problem Statement for "NumberPyramids"

Problem Statement

Suppose that there are N numbers written in a row. A row above this one consists of N-1 numbers, the i-th of which is the sum of the i-th and (i+1)-th elements of the first row. Every next row contains one number less than the previous one and every element is the sum of the two corresponding elements in the row below. The N-th row contains a single number. For example, if the initial numbers are {2,1,2,4}, the whole structure will look like this:
	   15
	  6 9
	 3 3 6
	2 1 2 4
We shall refer to such a structure as a number pyramid. Two number pyramids are equal if all the numbers at corresponding positions are equal.

Given ints baseLength and top, compute the total number of different number pyramids consisting of positive integers, having baseLength elements in the first row and the value at the top equal to top. Since the number of such pyramids might be enormous, return the result modulo 1,000,000,009.

Definition

Class:
NumberPyramids
Method:
count
Parameters:
int, int
Returns:
int
Method signature:
int count(int baseLength, int top)
(be sure your method is public)

Constraints

  • baseLength will be between 2 and 1,000,000, inclusive.
  • top will be between 1 and 1,000,000, inclusive.

Examples

  1. 3

    5

    Returns: 2

    The following are two possible pyramids with 3 numbers in the base and the number 5 at the top:

  2. 5

    16

    Returns: 1

    The only number pyramid with base of size 5 and 16 at the top looks like this:

  3. 4

    15

    Returns: 24

  4. 15

    31556

    Returns: 74280915

  5. 150

    500

    Returns: 0

  6. 2

    1

    Returns: 0

  7. 2

    2

    Returns: 1

  8. 2

    31

    Returns: 30

  9. 2

    99921

    Returns: 99920

  10. 2

    1000000

    Returns: 999999

  11. 3

    3

    Returns: 0

  12. 3

    4

    Returns: 1

  13. 3

    11

    Returns: 20

  14. 3

    6114

    Returns: 9339136

  15. 4

    1

    Returns: 0

  16. 4

    6

    Returns: 0

  17. 4

    8

    Returns: 1

  18. 4

    600000

    Returns: 964500728

  19. 4

    600001

    Returns: 964200549

  20. 4

    878909

    Returns: 919

  21. 5

    1

    Returns: 0

  22. 5

    17

    Returns: 2

  23. 5

    26

    Returns: 41

  24. 5

    663

    Returns: 79881120

  25. 5

    20912

    Returns: 201215843

  26. 5

    230319

    Returns: 155695707

  27. 5

    233336

    Returns: 28102304

  28. 5

    892319

    Returns: 305826445

  29. 5

    1000000

    Returns: 541033786

  30. 6

    38

    Returns: 11

  31. 6

    46990

    Returns: 1489

  32. 6

    96177

    Returns: 999999968

  33. 7

    221232

    Returns: 995

  34. 7

    221233

    Returns: 63045094

  35. 7

    221234

    Returns: 480190354

  36. 8

    128

    Returns: 1

  37. 8

    129

    Returns: 2

  38. 8

    745

    Returns: 502606384

  39. 8

    8456

    Returns: 588866907

  40. 8

    909201

    Returns: 606368952

  41. 8

    997231

    Returns: 518871768

  42. 8

    1000000

    Returns: 957757377

  43. 9

    261348

    Returns: 176

  44. 9

    800455

    Returns: 46210630

  45. 9

    821882

    Returns: 591474169

  46. 10

    900

    Returns: 3065245

  47. 10

    9000

    Returns: 237517869

  48. 10

    900000

    Returns: 160724396

  49. 10

    982217

    Returns: 54835737

  50. 10

    1000000

    Returns: 249398805

  51. 11

    2100

    Returns: 650490618

  52. 11

    62149

    Returns: 112922875

  53. 12

    234700

    Returns: 649632950

  54. 12

    995458

    Returns: 215

  55. 13

    7271

    Returns: 857222592

  56. 13

    12859

    Returns: 995324611

  57. 13

    99218

    Returns: 133737713

  58. 13

    100000

    Returns: 102817532

  59. 13

    881233

    Returns: 698094460

  60. 13

    1000000

    Returns: 988435748

  61. 14

    218

    Returns: 0

  62. 14

    3157

    Returns: 0

  63. 14

    777459

    Returns: 97961327

  64. 14

    909909

    Returns: 12791298

  65. 14

    999998

    Returns: 178936545

  66. 15

    66218

    Returns: 729885187

  67. 15

    126694

    Returns: 30567351

  68. 15

    606216

    Returns: 561886284

  69. 16

    49612

    Returns: 228423174

  70. 16

    77777

    Returns: 712432757

  71. 16

    612899

    Returns: 971102494

  72. 17

    65534

    Returns: 0

  73. 17

    65535

    Returns: 0

  74. 17

    65536

    Returns: 1

  75. 17

    666666

    Returns: 112553535

  76. 17

    862196

    Returns: 583103723

  77. 17

    1000000

    Returns: 676430199

  78. 18

    90521

    Returns: 0

  79. 18

    877049

    Returns: 999999843

  80. 18

    956903

    Returns: 752034524

  81. 19

    671238

    Returns: 258044316

  82. 19

    739033

    Returns: 453899991

  83. 19

    991000

    Returns: 90063078

  84. 19

    1000000

    Returns: 497295279

  85. 20

    3313

    Returns: 0

  86. 20

    524287

    Returns: 0

  87. 20

    524288

    Returns: 1

  88. 20

    531000

    Returns: 606695

  89. 20

    700000

    Returns: 20981017

  90. 20

    832966

    Returns: 252176906

  91. 20

    928156

    Returns: 133045640

  92. 20

    959712

    Returns: 900986492

  93. 20

    991727

    Returns: 817719810

  94. 20

    999999

    Returns: 293463623

  95. 20

    1000000

    Returns: 503596690

  96. 21

    1000000

    Returns: 0

  97. 22

    251

    Returns: 0

  98. 22

    885655

    Returns: 0

  99. 23

    251875

    Returns: 0

  100. 25

    997592

    Returns: 0

  101. 26

    1000000

    Returns: 0

  102. 27

    1000000

    Returns: 0

  103. 28

    905285

    Returns: 0

  104. 28

    1000000

    Returns: 0

  105. 29

    1000000

    Returns: 0

  106. 30

    882568

    Returns: 0

  107. 30

    1000000

    Returns: 0

  108. 31

    1000000

    Returns: 0

  109. 32

    1000000

    Returns: 0

  110. 33

    1000000

    Returns: 0

  111. 71

    1

    Returns: 0

  112. 89

    7

    Returns: 0

  113. 217

    61

    Returns: 0

  114. 217

    969257

    Returns: 0

  115. 1002

    92925

    Returns: 0

  116. 15852

    1000000

    Returns: 0

  117. 34744

    963081

    Returns: 0

  118. 70066

    618081

    Returns: 0

  119. 418145

    598281

    Returns: 0

  120. 572551

    946971

    Returns: 0

  121. 597232

    662821

    Returns: 0

  122. 645043

    380891

    Returns: 0

  123. 696406

    864131

    Returns: 0

  124. 717129

    618561

    Returns: 0

  125. 999999

    15215

    Returns: 0

  126. 1000000

    768276

    Returns: 0

  127. 1000000

    1000000

    Returns: 0

  128. 3

    1000000

    Returns: 998997760

  129. 4

    1000000

    Returns: 130353854

  130. 6

    1000000

    Returns: 866729335

  131. 7

    1000000

    Returns: 943949925

  132. 9

    1000000

    Returns: 267893633

  133. 11

    1000000

    Returns: 608237055

  134. 12

    1000000

    Returns: 989024786

  135. 14

    1000000

    Returns: 661570834

  136. 15

    1000000

    Returns: 388830591

  137. 16

    1000000

    Returns: 926227824

  138. 18

    1000000

    Returns: 378681417

  139. 20

    924288

    Returns: 453121764

  140. 19

    524288

    Returns: 922026758

  141. 19

    999999

    Returns: 781161529

  142. 1000000

    15

    Returns: 0

  143. 999900

    999941

    Returns: 0

  144. 17

    100000

    Returns: 502869195

  145. 20

    999997

    Returns: 873197498

  146. 22

    999999

    Returns: 0

  147. 33

    59279

    Returns: 0

  148. 9

    999998

    Returns: 674956729

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: