Statistics

Problem Statement for "ProductOfPrices"

Problem Statement

There are N trees numbered 0 to N-1, and you must plant them along a straight line. Tree i will be planted at coordinate X[i], where X is constructed using the following recursive definition:
X[0] = X0 MOD L
X[i] = (X[i-1]*A+B) MOD L (note that X[i-1]*A+B may overflow a 32-bit integer)
The price of planting tree i is the sum of the distances between tree i and each tree numbered less than i. Calculate the product of the prices of all the trees (except tree 0), and return this number modulo 1,000,000,007.

Definition

Class:
ProductOfPrices
Method:
product
Parameters:
int, int, int, int, int
Returns:
int
Method signature:
int product(int N, int L, int X0, int A, int B)
(be sure your method is public)

Constraints

  • N will be between 2 and 200,000, inclusive.
  • L will be between 1 and 200,000, inclusive.
  • X0,A,B will each be between 0 and 1,000,000,000, inclusive.

Examples

  1. 5

    10

    3

    1

    1

    Returns: 180

    The trees are planted at positions: 3, 4, 5, 6, 7. Their prices are (starting from tree 1): 1, 3, 6, 10. The product of prices is 1 * 3 * 6 * 10 = 180.

  2. 3

    20

    5

    2

    3

    Returns: 64

  3. 4

    21

    1

    7

    1

    Returns: 3087

  4. 10

    100

    4

    37

    11

    Returns: 591860767

  5. 13581

    95224

    350

    92105

    7812

    Returns: 425853540

  6. 32587

    72963

    858

    57778

    15129

    Returns: 873253283

  7. 6393

    85434

    19434

    28677

    81819

    Returns: 936153250

  8. 25435

    68151

    8486

    53726

    54733

    Returns: 52874401

  9. 1350

    61602

    33120

    56633

    7108

    Returns: 719507598

  10. 23301

    66993

    18052

    61204

    14102

    Returns: 124349808

  11. 21142

    17989

    13131

    12663

    8305

    Returns: 14469149

  12. 44016

    37799

    14927

    22974

    14193

    Returns: 100706128

  13. 33201

    33547

    27394

    24075

    29660

    Returns: 530872757

  14. 27301

    61816

    34438

    25550

    44538

    Returns: 396374845

  15. 30818

    91558

    52102

    70697

    42268

    Returns: 949547358

  16. 2526

    19991

    17815

    17571

    7841

    Returns: 793586311

  17. 2407

    38520

    247

    22469

    30071

    Returns: 828290093

  18. 1227

    58191

    29113

    27041

    28658

    Returns: 346407296

  19. 19736

    10003

    3039

    1678

    4843

    Returns: 955301883

  20. 48318

    17478

    14601

    847

    5638

    Returns: 294755456

  21. 11092

    17597

    17395

    10850

    9477

    Returns: 26934147

  22. 48838

    3744

    1920

    608

    3146

    Returns: 660894866

  23. 17124

    85887

    19591

    71228

    48195

    Returns: 88064867

  24. 8531

    39958

    6893

    7255

    38435

    Returns: 228638846

  25. 30572

    37655

    15312

    14475

    718

    Returns: 736603828

  26. 10113

    94972

    53507

    16248

    73321

    Returns: 107751165

  27. 26171

    58377

    54646

    25112

    19293

    Returns: 677427515

  28. 21301

    40949

    18444

    9959

    24319

    Returns: 231911130

  29. 2023

    75163

    44017

    1422

    55302

    Returns: 658964165

  30. 20484

    10811

    7998

    2674

    1965

    Returns: 981910604

  31. 12388

    70517

    34089

    26554

    66754

    Returns: 311468353

  32. 40050

    13353

    1835

    2036

    8572

    Returns: 420465876

  33. 41901

    64956

    53878

    25052

    49369

    Returns: 501018975

  34. 28250

    66466

    35109

    36140

    38324

    Returns: 43524289

  35. 17051

    69954

    58152

    35465

    36515

    Returns: 92318821

  36. 43787

    31570

    1645

    465

    15941

    Returns: 982368909

  37. 1517

    50473

    46468

    27278

    89

    Returns: 77747239

  38. 28613

    94639

    36937

    58671

    70752

    Returns: 517332894

  39. 42450

    48475

    13227

    26688

    34939

    Returns: 787721080

  40. 32639

    90765

    26079

    67169

    86382

    Returns: 416241334

  41. 21973

    94060

    17339

    3642

    85831

    Returns: 877812144

  42. 8673

    12119

    10495

    4108

    6172

    Returns: 837580511

  43. 39508

    27106

    4112

    21

    19624

    Returns: 498491

  44. 32673

    65923

    32266

    10144

    40888

    Returns: 609727347

  45. 135035

    200000

    160896

    188253

    164579

    Returns: 225360414

  46. 56027

    91714

    37679

    79857

    29983

    Returns: 502723285

  47. 159167

    158159

    144403

    109260

    31426

    Returns: 939542237

  48. 133506

    63956

    44366

    13405

    40355

    Returns: 198420718

  49. 87903

    102154

    39621

    72647

    81439

    Returns: 366060051

  50. 105083

    131673

    104542

    10253

    128840

    Returns: 395301960

  51. 62492

    187471

    123475

    109454

    115033

    Returns: 724482282

  52. 200000

    200000

    96826

    92288

    76859

    Returns: 966728250

  53. 150507

    200000

    144526

    196414

    81964

    Returns: 300128655

  54. 200000

    146857

    143819

    87990

    62518

    Returns: 303911806

  55. 92681

    200000

    32261

    146108

    190794

    Returns: 703116537

  56. 200000

    200000

    176100

    28551

    157621

    Returns: 485400433

  57. 200000

    200000

    113701

    80020

    168689

    Returns: 821676669

  58. 200000

    200000

    53631

    81883

    75644

    Returns: 51745470

  59. 200000

    200000

    130279

    194876

    143888

    Returns: 351328776

  60. 200000

    200000

    114880

    168329

    4021

    Returns: 83526623

  61. 200000

    200000

    52590

    93116

    158850

    Returns: 442195328

  62. 200000

    200000

    37193

    94162

    69515

    Returns: 1787913

  63. 200000

    200000

    10405

    121012

    118630

    Returns: 261044987

  64. 200000

    200000

    140219

    185071

    1479

    Returns: 909353568

  65. 5

    200000

    999999999

    123456789

    987654321

    Returns: 499739175

  66. 199999

    200000

    999999999

    123456789

    987654321

    Returns: 988935907

  67. 43661

    200000

    999999999

    123456789

    987654321

    Returns: 498323077

  68. 200000

    200000

    999999999

    123456789

    987654321

    Returns: 725110457

  69. 200000

    200000

    200000

    200000

    200000

    Returns: 0

  70. 200000

    100

    4

    37

    11

    Returns: 118468348

  71. 200000

    199997

    999999999

    123456789

    987654321

    Returns: 435256351

  72. 200000

    17

    1276512

    12675127

    1276182

    Returns: 262774090

  73. 200000

    199967

    999999999

    123456789

    987654321

    Returns: 27701017

  74. 200000

    200000

    1

    1

    1

    Returns: 407222067

  75. 200000

    200000

    999999997

    999999995

    999999993

    Returns: 623728084

  76. 200000

    199999

    999999999

    999999999

    999999999

    Returns: 826784755

  77. 200000

    197637

    693997111

    979735977

    345999

    Returns: 857097268

  78. 200000

    200000

    1000000

    1000000

    1000000

    Returns: 0

  79. 200000

    194673

    1000000000

    999999998

    77697697

    Returns: 604808605

  80. 2

    11

    22

    0

    5

    Returns: 5

  81. 200000

    200000

    1000000000

    1000000000

    1000000000

    Returns: 0

  82. 200000

    200000

    5

    6

    7

    Returns: 661005811

  83. 200000

    200000

    392032

    328943

    4894343

    Returns: 804429083

  84. 200000

    200000

    2432434

    3235323

    13213212

    Returns: 403372060

  85. 200000

    98765

    500000

    1234567

    678912345

    Returns: 568102096

  86. 200000

    200000

    0

    1

    1

    Returns: 407222067

  87. 200000

    200000

    456165158

    489451458

    789484818

    Returns: 465182110

  88. 200000

    197256

    999999999

    999732569

    925943587

    Returns: 576379154

  89. 200000

    1

    15

    15

    15

    Returns: 0

  90. 200000

    100000

    99

    19999999

    999999917

    Returns: 842482663

  91. 199937

    184214

    923431534

    923431537

    923431539

    Returns: 10305340

  92. 200000

    1

    1

    7

    1

    Returns: 0

  93. 20

    10000

    999999

    6

    4

    Returns: 225219841

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: