TopCoder Statistics - Problem Statement

Problem Statement

Basha recently had to endure a long flight between two continents. To keep herself occupied, she generated a very long pseudorandom sequence A and then she modified this sequence by performing a sequence of s steps. Your task is to compute and return a int[] with two elements: the first and the last element of Basha's final sequence.

You are given the long n: the length of Basha's original sequence. You are also given the ints a0, a1, c1, c2, and add: parameters of the pseudorandom generator Basha used. Her initial sequence can be generated by following this pseudocode:

A[0] = a0
A[1] = a1
for i = 2 to n-1:
    A[i] = ( c1*A[i-1] + c2*A[i-2] + add ) modulo (10^9 + 7)

You are also given longs b (block size) and s (number of steps). The modification Basha applied to the sequence in each of the s steps looks as follows:

Remove the first b elements of the sequence (or all elements if the sequence has fewer than b elements already).
Let r be the sum of the removed elements, modulo 10^9 + 7.
Append r to the current sequence.

Definition

Class:: SequenceEvolution
Method:: findEndpoints
Parameters:: long, int, int, int, int, int, long, long
Returns:: int[]
Method signature:: int[] findEndpoints(long n, int a0, int a1, int c1, int c2, int add, long b, long s)
(be sure your method is public)

Constraints

n will be between 2 and 10^18, inclusive.
a0, a1, c1, c2, and add will each be between 0 and 10^9 + 6, inclusive.
b will be between 1 and 10^18, inclusive.
s will be between 0 and 10^18, inclusive.

Examples

11

0

10

1

0

10

3

3

Returns: {90, 210 }

See Example #1 annotation below.
11

0

10

1

0

10

3

4

Returns: {120, 220 }

Both Example 0 and Example 1 define the same sequence A = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100}. In both examples Basha is using block size b = 3. Her first four steps produce the following sequences, in order: {30, 40, 50, 60, 70, 80, 90, 100, 30} {60, 70, 80, 90, 100, 30, 120} {90, 100, 30, 120, 210} {120, 210, 220} Example #0 asked about the sequence after three steps, this example is asking about the sequence after four steps.
100

0

1

1

1

0

5

20

Returns: {7, 688840473 }

Here the sequence A are the first 100 Fibonacci numbers, modulo 1,000,000,007.
100

47

47

0

0

47

2

12345

Returns: {4700, 4700 }

Here the initial sequence A are simply 100 copies of the number 47. Her final sequence is the one-element sequence {4700}. Thus, the first and the last element of her final sequence is the same.
47

12

3

456

7

89

100000000000000047

1

Returns: {398925423, 398925423 }
47

12

3

456

7

89

100000000000000047

0

Returns: {12, 752439360 }
47

12

3

456

7

89

1

100000000000000047

Returns: {148546581, 320490412 }
999999999999999953

12

3

456

7

89

1

100000000000000047

Returns: {437315184, 668690887 }
5478157726378

2

1

14

46894042

10443

1019364323

371326025158911

Returns: {931982879, 931982879 }
9429819185964396

661

10113

401

434443676

63733890

138227000977

68215

Returns: {825149354, 723795565 }
31

51157

5908700

6

51

1836

25

0

Returns: {51157, 723846152 }
4232015358

214568

100501984

1488411

1411

17744

2894005358

1

Returns: {608588884, 178174211 }
290398

387510

395

31

1158010

116

3

145196

Returns: {254843776, 420933694 }
4

2064

69588483

58

965

251198

131726137233808253

2125791734898537

Returns: {486849053, 486849053 }
13076173

29519644

55

0

0

12693

2

223534128

Returns: {5357040, 5357040 }
212

26

114374022

126046819

122556038

3385

7

26

Returns: {5199418, 875702028 }
4257005366473230

219433123

5

537531658

1

503519408

434898604927

9779

Returns: {10567911, 899638096 }
1722

233847

9

1

932313676

343

27799727

1848

Returns: {19723929, 19723929 }
57545926

3269795

202423619

395200

1636

8935

27272680405117

751264730686810080

Returns: {237351981, 237351981 }
342

591

20

28464643

117

188624

2

339

Returns: {141817165, 83164392 }
242590961295512

12783837

283

4528

49712

1790

10375

23384515251

Returns: {468512493, 837122073 }
36163737729656045

3882

810

130506421

69989423

950

17860121

2024831730

Returns: {698628609, 706026569 }
2

9

96921

152

0

1643432

56971958226

3895893420126833

Returns: {96930, 96930 }
137196165614168

57354

229079152

13

25853962

60

248

436

Returns: {505629817, 416127767 }
2223327926572783

1834882

423257

29409459

3

495

20177703

110187370

Returns: {195953393, 561579322 }
15

5

13

3

9

764257484

578

580

Returns: {437538919, 437538919 }
517600130750380423

0

146

8401266

16765935

468795861

42367277467799

12207

Returns: {106900296, 684172403 }
735957887

484

8363486

2422

29979

47

533346

6

Returns: {624255547, 978424643 }
1345820099

58398157

1

377862282

350135

105641

4027007670155

1681

Returns: {440014130, 440014130 }
1378719763303187

113449226

603

923424

44

51

28531336472

114931

Returns: {324250299, 324250299 }
218972632642925436

256927

57996

712

30532433

299335279

71716153986927613

51

Returns: {913564206, 913564206 }
18

43896695

1368

152824425

7097

11619167

1225102182

1097611289606

Returns: {948480112, 948480112 }
163561

116

25418141

7397407

4631555

1945062

678

35394722

Returns: {444045195, 444045195 }
7413209941848

514081411

7757

3

69926329

95721

1707097

1012

Returns: {107657291, 832305985 }
3050794751147

405542780

1292952

12357

8727

190

750844

4063154

Returns: {894886253, 515003586 }
14076125801504068

7

70199149

2

4

2

12412722491

53590213456618368

Returns: {104086340, 104086340 }
102416458321058994

506747857

1486

68686

57

6

37078589398

144673465

Returns: {128948948, 128948948 }
17441

220182

1

13030407

45377965

64

14654484

46070672370719

Returns: {749405598, 749405598 }
167512489

53

75029365

1441738

65015325

665206428

2156

77730

Returns: {737219914, 91307159 }
948869291

9

925525295

478200

4845

51

27942643

31

Returns: {797422037, 510561293 }
62977

30902640

573926915

670

3503

2715897

11953684077751

4

Returns: {673255172, 673255172 }
1593960

10448

32678

2187

536

762883

3787

413

Returns: {346236898, 586596230 }
387872325

3

392899322

69549216

75959230

23069293

845571

457

Returns: {697636777, 877077598 }
4644770215972

3

379580742

115

969400

5529447

32938895728830629

553456663108475

Returns: {108280546, 108280546 }
52604999125

448235433

13627686

111321050

135045222

382

61854330631070384

10136

Returns: {812471700, 812471700 }
124504892

61943927

167

16107456

42438

8

80

1576010

Returns: {550652689, 15801578 }
2393994563828151

46

4966

4093

13462553

33565

40043358

59785052

Returns: {727855673, 648354083 }
18139267

1734656

4024460

2

45

12

61272550969

118914434613

Returns: {891158271, 891158271 }
16499

34431

1880351

365961

37202

5

1746

5

Returns: {967618019, 23637711 }
1772130802

339

150101

6

2

55356

3880

456851

Returns: {920692932, 667170752 }
2359401

127999536

1588441

14972245

3

1

64327

34

Returns: {925303944, 915414273 }
5342896079316136

115498285

6

7

98872

6469

7905

675973694245

Returns: {880977321, 669685644 }
4213628354389281

4472651

63688

547601

23309

3907570

1986

2122734687342

Returns: {422966857, 566374574 }
202638922910962

36654

0

18702005

1

137

56891188189

464327283

Returns: {31088563, 31088563 }
82935657678

262681514

745160

447979042

21969

2352664

84

0

Returns: {262681514, 826376973 }
1013579507214

427485

5190410

26

382175789

75

15738116876

63

Returns: {722782243, 924018555 }
35

7

2092964

5291829

94

141

11

41314

Returns: {668013991, 668013991 }
231270611439004

3

16

12

23147

10053

23898643099592

3326147995

Returns: {315054271, 315054271 }
930411975609403

7957955

3

441591588

7828172

746

1956993460

307613060924242

Returns: {187086820, 187086820 }
8194012123

1251

27643212

66453

88714

0

878638413847

3846502963402

Returns: {865819859, 865819859 }
3305027043

1896

79

919475

2963

18174926

289

7828767250366475

Returns: {697037306, 697037306 }
35501

174

0

10

429

2

66

537

Returns: {10042825, 999191517 }
34

7048113

256

55787

552

65828908

3

15

Returns: {21546823, 109655371 }
122764972962126

14

206600791

105

0

328138137

3027213606440

152683544

Returns: {131183320, 131183320 }
950712643

23

97092606

13010

324166

504

6124925195422

8215914695

Returns: {800182718, 800182718 }
15403921014250

9074

5886

21473208

57527331

0

14772643799993

0

Returns: {9074, 495925255 }
17317300184275

9164

847677

12831683

4

62732

3093481483

5595

Returns: {821635703, 269598753 }
49698

2343250

51

14

2909571

379441942

16452081

1567934

Returns: {494550003, 494550003 }
1272833918

2221861

19505956

11645

52859

71

177541

7166

Returns: {167874256, 409589205 }
8039194

964

80299180

552

499

475811

488486637

3212279408598

Returns: {588334382, 588334382 }
138932467202044069

2415

117365

2255738

12

289423

519333707720

267517

Returns: {130245356, 469913590 }
83397357003016513

121012714

177825

367

3651625

37835

670680634752724677

26410

Returns: {51244886, 51244886 }
27928

965042886

7733657

234499

697

8174

15468499784333103

43765

Returns: {333073791, 333073791 }
12671207427

513334

0

24

736599787

5885

1875933919074928

11001728371804160

Returns: {143586310, 143586310 }
189

110

939642

60673251

23558998

29528

51152851

16042303951475

Returns: {948956901, 948956901 }
255

314346

3763

110

32332727

1593

442450331348932

3

Returns: {598801200, 598801200 }
242875616696547

6

4565

1

13185

79241

6471015540980

29044

Returns: {6926389, 6926389 }
48

1490968

4278947

3026952

5700

1715

29103

22669417707022343

Returns: {21185992, 21185992 }
546

482069

4558

93410

3

83006

41598970

93

Returns: {534561925, 534561925 }
11140604688293

1

52556

43163702

253313647

675

6126355171

174

Returns: {879162893, 79658657 }
15909595289509

544471298

24670945

5089493

1183406

620

22387

710693964

Returns: {336047266, 77701500 }
55

12630467

46

1506916

655138955

57247150

12

4

Returns: {372835594, 105130993 }
24

396074085

862433180

87484676

214763

101747469

2175270247099198

5681228

Returns: {793276805, 793276805 }
8031

6742729

921

925897

79

34026163

1

11253344

Returns: {15410911, 932893394 }
3373555

31762

23070

31

12031324

784933

3401

36409400079124

Returns: {153276189, 153276189 }
5388

4681243

1512

74763998

754985

16040639

171

23

Returns: {383694222, 400787901 }
210421706777277867

28150

199192215

3

3531242

3025

704245939046970

293

Returns: {587896916, 617341136 }
807096867913548233

88651

7821

810106

1942

6106583

4

179141

Returns: {830529354, 53907007 }
1534235583633

14

1

58

377659

46291063

22

73058837315

Returns: {790660332, 501790378 }
67286

475915

396

26

127481012

891267346

216

39

Returns: {462238945, 209886454 }
4177026676981756

12

13817070

425165925

759

1766

13254

315175935776

Returns: {747168867, 521168651 }
1561054

187164

1894538

5969418

218

1

436

84949232133989983

Returns: {970521787, 970521787 }
6

649

575160542

29246

202109

3

6

5941982212007193

Returns: {298157932, 298157932 }
153

216

20403951

123721

0

117

13

2

Returns: {371990867, 64445592 }
64561456824922

55920

84694

414

143197

116015323

15534795988

33074659987941

Returns: {422072837, 422072837 }
1145

423498

112775183

6

44764

707

13

88

Returns: {403061468, 287973691 }
287321737731266

971703

700575736

1

199808

8

9651115

70

Returns: {740192512, 370215813 }
327076

945

2091969

98583982

53280

1

15756

12

Returns: {378604036, 778926644 }
602

38655

1860380

814

121

102664739

24281

1229721127781550

Returns: {198316423, 198316423 }
23674242831

31743

79013326

5

13218365

1678136

4487224635056653

25

Returns: {469045977, 469045977 }
466447167693028180

868930

1983374

2213

0

1

4140714644

3470179331972

Returns: {357079810, 357079810 }
7976

1

0

202858

49396710

512310539

4

2650

Returns: {575670378, 194031980 }
1632832348184821

43944

13473491

1352

278434

2

2386

1582941727328

Returns: {172576357, 172576357 }
18591767

3

221412853

3

14904035

14541

14256

1

Returns: {373598781, 195946223 }
55182

83

235851673

1472656

50748

402635150

2192

20

Returns: {521075345, 555697586 }
111967777

145

55

6381

6841462

5636

5628

11947688172040103

Returns: {25825340, 25825340 }
35703155

3220

5

19493325

127568

71

5

175973

Returns: {491933224, 4152169 }
991392501

6213

35736

14737051

175769

0

54565397

10

Returns: {891637494, 731097914 }
2278

1

3606

0

228

6139717

47

3631

Returns: {942466242, 942466242 }
793355765613784

16474

189224137

26

8

11

2581146141

943163724

Returns: {203340373, 203340373 }
3

483276

118

56875014

3

12625

2

1

Returns: {712714063, 483394 }
55875823

24

58619562

56

11348461

138881

185

303663

Returns: {919820241, 885751133 }
5744557

1017

8

32353761

213211056

63

1640545

1

Returns: {543424958, 314205060 }
40

4625284

345

12928057

10

26941

7

3

Returns: {191866967, 198145087 }
20589988161909

8

196

951697

22

183895

1260263

12127865953

Returns: {915530518, 915530518 }
1085381154728

11042

140783122

133

2

3331

30929971520154762

14797877224290

Returns: {914685895, 914685895 }
258115737276215

668

241

2908

15639219

81857

57273802422837789

2196719299335

Returns: {195688037, 195688037 }
4

45

739045531

2

1

64199

3

0

Returns: {45, 695420321 }
1026765276850283

43

159376807

27762840

93501882

940695

1329933631454

766

Returns: {175444277, 576602913 }
396791619

68131599

123757

13846936

883

914757

3307079082074378

1590786

Returns: {688216149, 688216149 }
63501071199916

184466931

17888

31949062

33

264540657

756

84107379066

Returns: {360668389, 935938551 }
36790

1117983

2

53893749

29771631

51265

2948046745456202

190846

Returns: {571577819, 571577819 }
29310

8060298

510527454

440244492

3363

1

3

2687503160848640

Returns: {900514845, 900514845 }
855373124397

5364708

592

1138

1234

142074

30

29495624973

Returns: {593179772, 599044144 }
12807997024753629

1464

32529807

18059570

711

6

24

4132559380

Returns: {939589610, 726270309 }
304478

887154755

52

0

23501724

97896

136

6

Returns: {703830730, 435251607 }
51

4075

325

24263

396804

282550171

29

0

Returns: {4075, 515294086 }
33074324523927629

28

53296792

36

1

2024

3578489

978699

Returns: {253560767, 18867428 }
1000000000000000000

666

1337

13

42

17

3

499999999999999908

Returns: {520772211, 387674334 }
11

0

10

1

0

10

1

3

Returns: {30, 20 }
100000000000000

1

1

1

1

1

835391290974666743

461319601325209534

Returns: {491453849, 491453849 }
11

0

10

1

0

10

3

0

Returns: {0, 100 }
999999999999999999

12423432

13432

113234321

2345569

13432

102

999999999999999999

Returns: {547913130, 547913130 }
1000000000000000000

12

3

456

7

89

1000000000000000000

1000000000000000000

Returns: {449349796, 449349796 }
1000000000000000000

1583916

294671496

928461943

71538065

13598176

2

999999999999999995

Returns: {112192638, 468902362 }

Statistics

Problem Statement for "SequenceEvolution"

Problem Statement

Definition

Constraints

Examples