Statistics

Problem Statement for "GreaterThanAll"

Problem Statement

Given a sequence A = (a1, a2, ..., an) (where a[i] >= 1 are integers), of length n, we define the Peak_Set as
Peak_Set(A) = { a[i] : a[i] > a[j] for all j < i }

For example, for the sequence A = {2, 1, 5, 6, 3, 3, 2, 8, 10, 4}, Peak_Set(A) = {2, 5, 6, 8, 10}.

For a given integers N and K, you need to count the number of Sequences 'X' of length N with Peak_Set(X) = {1, 2, 3,..., K}, modulo (109 + 7).

Definition

Class:
GreaterThanAll
Method:
count
Parameters:
int, int
Returns:
int
Method signature:
int count(int n, int k)
(be sure your method is public)

Constraints

  • The number of elements of the sequence, N ranges from 1 to 106, inclusive.
  • The value of K is between 1 and N.

Examples

  1. 3

    2

    Returns: 3

    The only possible sequences are "112", "121" and "122" whose Peak_Set is {1, 2}.

  2. 762476

    157929

    Returns: 441862509

  3. 827329

    254322

    Returns: 801382793

  4. 812215

    610951

    Returns: 375724243

  5. 506277

    454955

    Returns: 317906005

  6. 305164

    17049

    Returns: 689989886

  7. 799745

    776433

    Returns: 164647106

  8. 1000000

    1000000

    Returns: 1

  9. 1000000

    1

    Returns: 1

  10. 999995

    954215

    Returns: 809401501

  11. 279866

    264516

    Returns: 492364696

  12. 170283

    136213

    Returns: 208361490

  13. 391787

    14082

    Returns: 369524912

  14. 651790

    291996

    Returns: 775883210

  15. 498201

    319574

    Returns: 752053917

  16. 234200

    26813

    Returns: 623752087

  17. 27172

    26384

    Returns: 12020218

  18. 862881

    404824

    Returns: 775375777

  19. 46349

    44318

    Returns: 226760578

  20. 634934

    297600

    Returns: 215540901

  21. 120611

    70922

    Returns: 375007106

  22. 988756

    447915

    Returns: 201119111

  23. 505932

    487038

    Returns: 111159450

  24. 41278

    22942

    Returns: 35520939

  25. 739514

    301081

    Returns: 192480900

  26. 554861

    204175

    Returns: 749050055

  27. 796426

    318040

    Returns: 551640119

  28. 837901

    733523

    Returns: 583775153

  29. 919669

    345023

    Returns: 402283886

  30. 634554

    138157

    Returns: 276450777

  31. 141095

    71847

    Returns: 444284206

  32. 10351

    468

    Returns: 128558183

  33. 458055

    215029

    Returns: 166200507

  34. 702324

    285771

    Returns: 293985905

  35. 987304

    10831

    Returns: 65574589

  36. 289566

    264506

    Returns: 234309219

  37. 562222

    347382

    Returns: 75156755

  38. 455083

    389827

    Returns: 545620864

  39. 333001

    133654

    Returns: 50653011

  40. 87020

    34178

    Returns: 771575699

  41. 954816

    836594

    Returns: 979833418

  42. 194801

    171423

    Returns: 600992257

  43. 71208

    3999

    Returns: 485940048

  44. 701570

    181632

    Returns: 248996753

  45. 244400

    34980

    Returns: 47109599

  46. 338343

    318765

    Returns: 672516097

  47. 700519

    136200

    Returns: 917294859

  48. 722524

    429083

    Returns: 800300175

  49. 920304

    484913

    Returns: 693404759

  50. 655531

    60913

    Returns: 16163135

  51. 876338

    232823

    Returns: 129511336

  52. 448291

    289243

    Returns: 206645847

  53. 180261

    8881

    Returns: 873824940

  54. 856098

    755143

    Returns: 92944902

  55. 808232

    677661

    Returns: 641169416

  56. 426217

    59709

    Returns: 923272131

  57. 989367

    53544

    Returns: 966275128

  58. 96750

    49040

    Returns: 270618580

  59. 671539

    129865

    Returns: 328586877

  60. 854338

    783520

    Returns: 966199944

  61. 616010

    340074

    Returns: 432437436

  62. 798379

    488392

    Returns: 53659943

  63. 793499

    409126

    Returns: 728007860

  64. 906358

    367782

    Returns: 913095050

  65. 323491

    291296

    Returns: 653592597

  66. 727079

    384535

    Returns: 721424991

  67. 60485

    10991

    Returns: 468946747

  68. 551102

    92394

    Returns: 645251191

  69. 208707

    84736

    Returns: 447277314

  70. 146539

    115237

    Returns: 685496707

  71. 387856

    180328

    Returns: 199294956

  72. 671431

    622835

    Returns: 572203630

  73. 554155

    524236

    Returns: 799598225

  74. 663703

    652053

    Returns: 770226763

  75. 320815

    135972

    Returns: 163402173

  76. 180340

    170678

    Returns: 134234228

  77. 842264

    52939

    Returns: 176975639

  78. 707409

    97880

    Returns: 558434599

  79. 197763

    81862

    Returns: 537183082

  80. 34702

    31576

    Returns: 145254342

  81. 354819

    311149

    Returns: 20263552

  82. 789823

    561009

    Returns: 869060603

  83. 500436

    327079

    Returns: 219981312

  84. 166796

    43539

    Returns: 725515342

  85. 188510

    14683

    Returns: 835269143

  86. 23507

    16086

    Returns: 88072910

  87. 21456

    2415

    Returns: 169959623

  88. 458897

    423885

    Returns: 38803504

  89. 486922

    138496

    Returns: 970937770

  90. 699008

    419758

    Returns: 500922774

  91. 455757

    439794

    Returns: 855499250

  92. 434872

    245048

    Returns: 72531213

  93. 249164

    69883

    Returns: 673153387

  94. 619662

    190983

    Returns: 988159634

  95. 331612

    120951

    Returns: 16249519

  96. 852574

    468089

    Returns: 572671550

  97. 968693

    854974

    Returns: 399629984

  98. 148185

    80474

    Returns: 914696991

  99. 338960

    290202

    Returns: 546376162

  100. 62083

    33669

    Returns: 627335640

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: