Problem Statement
We have a strip of N cells. Each cell can be one of C colors. The cells of the strip are numbered from 0 to N-1, left to right. The colors are numbered from 0 to C-1. Initially, all cells have color 0.
You are going to perform a sequence of Q operations.
The operations are numbered from 0 to Q-1. In each operation you will take some contiguous segment of the strip and repaint it in a new color.
The segment for operation i will start at index QL[i], end at index QR[i], and the new color for all its cells (including both endpoints) will be QC[i].
The hash of a sequence S = { s[0], s[1], ..., s[k-1] } is the value h(S) = sum( s[i]*10^i ) modulo (10^9 + 7).
For example, the hash of the sequence {2, 10, 4} is 2 + 10*10 + 4*100 = 502, and the hash of the sequence {0, 0, 0, 0, 0, 0, 0, 0, 0, 2} is 2,000,000,000 mod (10^9 + 7) = 999,999,993.
Given a state of the strip, its color distribution is the sequence P = { p[0], p[1], ..., p[C-1] } where p[i] is the number of cells that currently have the color i. The value h(P) will be called the fingerprint.
Consider the sequence F = { f[0], f[1], ..., f[Q-1] }, where f[i] is the fingerprint after performing the i-th operation. Calculate and return the value h(F).
In order to keep the input small, all operations are pseudorandom. Please use the pseudocode below to generate them.
state = seed
for i = 0 to Q-1:
state = (state * 1103515245 + 12345) modulo 2^31
qlen = 1 + (state modulo maxL)
state = (state * 1103515245 + 12345) modulo 2^31
QL[i] = state modulo (N+1-qlen)
QR[i] = QL[i] + qlen - 1
state = (state * 1103515245 + 12345) modulo 2^31
QC[i] = state modulo C
Definition
- Class:
- ColorfulStrip
- Method:
- recolor
- Parameters:
- int, int, int, int, int
- Returns:
- int
- Method signature:
- int recolor(int N, int C, int Q, int maxL, int seed)
- (be sure your method is public)
Notes
- The pseudocode used to generate QL and QR ensures that for each i we have QL[i] <= QR[i].
- The reference solution does not depend on the input being pseudorandom. It would correctly solve any input of the same size.
Constraints
- N will be between 1 and 10^9, inclusive.
- C will be between 1 and 10^9, inclusive.
- Q will be between 1 and 250,000, inclusive.
- maxL will be between 1 and N, inclusive.
- seed will be between 0 and 2^31 - 1, inclusive.
Examples
100
1
12
13
47
Returns: 111033323
There are 100 cells, 1 color, and 12 queries. As there is only one color, after each operation there will be 100 cells of color 0, so the color distribution will always be {100} and the fingerprint will always be 100. The correct return value is therefore the hash of the sequence {100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100}.
997
10
5
350
474747
Returns: 530787752
You should generate the following operations: QL = { 135, 800, 247, 554, 735 } QR = { 255, 969, 557, 819, 953 } QC = { 2, 3, 8, 3, 0 } The color distributions after each of these steps look as follows: after operation 0: 876, 0, 121, 0, 0, 0, 0, 0, 0, 0 after operation 1: 706, 0, 121, 170, 0, 0, 0, 0, 0, 0 after operation 2: 404, 0, 112, 170, 0, 0, 0, 0, 311, 0 after operation 3: 162, 0, 112, 416, 0, 0, 0, 0, 307, 0 after operation 4: 381, 0, 112, 197, 0, 0, 0, 0, 307, 0 The sequence of fingerprints: { 12976, 182806, 100181387, 700427152, 700208371 }.
999999973
99997
250000
923456789
12125
Returns: 728566493
2
12345
12345
2
12345
Returns: 473696403
999999973
999999998
250000
1
111
Returns: 28621520
4718803
7
240387
116202
440044526
Returns: 293905398
1
24174
248573
1
1542245923
Returns: 652271267
398384431
6050
240578
301155393
539016619
Returns: 212148709
2507971
15909
241804
93
1789542187
Returns: 776019340
6596116
20117
243392
4657910
1631517495
Returns: 387187717
966
9779
244354
175
2046595582
Returns: 678913147
232351988
2
243462
163152532
1485905588
Returns: 368928252
183614149
16762
241612
126109085
586949650
Returns: 649904050
7485663
1
246784
2238628
288469429
Returns: 665242611
8736258
96882
248383
5
2108757054
Returns: 454133049
8148
19736
248903
1
1453170456
Returns: 249443619
5
2912
241451
4
1300208178
Returns: 295340668
12
72081
249498
10
1173215853
Returns: 297429057
63
288
248321
9
502796335
Returns: 874112629
3
122
247545
2
1188790660
Returns: 61014378
2
102
242029
1
729061624
Returns: 867095556
224588210
3592
240701
197167964
780112910
Returns: 233348818
2367
73426
246375
1
3240676
Returns: 234922902
33531870
75
246886
10443553
1769321186
Returns: 640592554
86
20
247989
57
1430484067
Returns: 59128321
96
51715
241332
54
963098471
Returns: 302013331
12413
63999
243953
12
1736740490
Returns: 231987959
49341891
20589
249664
107
454791749
Returns: 216451704
44775
94213
242710
9288
331716879
Returns: 423538282
40
14
241656
2
1885893272
Returns: 852801146
152
679
244736
3
311775786
Returns: 72026275
12
33579
245647
11
825599650
Returns: 560132689
14243
6
249873
359
1286708360
Returns: 632336082
81979605
35465
246644
7
251147389
Returns: 74672187
3
54
245554
2
1894985334
Returns: 988265234
18
49
246478
4
1494062160
Returns: 369822241
4
73552
243650
2
370670828
Returns: 880205855
1
6
242320
1
2007325964
Returns: 381214935
40355407
48205
245573
39783052
633475780
Returns: 462168685
1
44180
246498
1
1300856391
Returns: 304429688
6173
31839
242860
5560
1514336675
Returns: 398297839
4895554
8977
244267
102315
2092700209
Returns: 489148839
19967
6391
242628
3673
693409053
Returns: 248354587
1369931
51255
243593
399195
952639852
Returns: 578019900
2401
4
249091
988
948638990
Returns: 885761704
9933
1
245904
8183
1803768730
Returns: 174585323
75
74627
245140
5
977288327
Returns: 401867375
12231791
7574
243054
8197946
1991163376
Returns: 49333708
17549
1
247853
1
1349659236
Returns: 958231605
918057
28510
243580
706932
2109852989
Returns: 69225939
536003762
85577
240865
42946417
923918555
Returns: 828818289
12
50387
248091
2
884899815
Returns: 150758932
1777
72080
243905
1143
2068126907
Returns: 190334835
15
1375
243245
9
1428186349
Returns: 182379346
1
6
246132
1
1600369265
Returns: 497627084
11039855
63241
248784
4313022
2005272623
Returns: 344749776
3720760
58370
246933
1237437
1137788003
Returns: 596285654
48562
39973
246872
10280
2124614898
Returns: 550277841
46659
8821
245269
45446
1176713079
Returns: 378706531
469
69509
242937
60
779601002
Returns: 359942436
228
72762
246875
37
661904857
Returns: 35185847
2737
8
245294
22
835923665
Returns: 571511303
17202818
19948
244093
13188065
857086325
Returns: 933268150
25423429
46578
249761
1341
1506823224
Returns: 703759909
560
23538
240826
131
51078785
Returns: 695705316
5963236
3994
245627
4246605
1086346993
Returns: 381732232
971493483
1351
248690
480732219
1831387875
Returns: 351952451
294941836
2
249535
469
1970538630
Returns: 305145680
990577757
15687
247272
299751650
803977018
Returns: 154105183
125807844
47754
249304
53020426
263520458
Returns: 339632489
214138776
1
243632
2981937
907313320
Returns: 387688436
462528780
87051
241900
208402007
554921977
Returns: 844287948
621850841
32652
246738
7
199399791
Returns: 523183324
770313812
26745
241505
503916150
2141553494
Returns: 287575207
634607007
25380
245414
344290557
962310932
Returns: 861885409
4718803
1945526
243769
116202
1021093428
Returns: 603071946
34947
234754154
245471
6050
420679459
Returns: 145336067
14823990
6596116
243915
93
1123519141
Returns: 525322215
4530769
255986
247137
938976
1570148161
Returns: 592404947
6
547594739
241209
1
752144434
Returns: 766866928
858
864765051
241003
637
1626629292
Returns: 726007368
133
688255571
245040
78
1027003835
Returns: 714979852
791
2316021
241877
577
1775873863
Returns: 686742842
114587400
556067011
247120
19
284290351
Returns: 90190533
519151
478160092
245424
395813
716905769
Returns: 42866103
561131087
137306
249178
493352293
812974551
Returns: 637420337
928718827
13618016
246751
19
879909240
Returns: 166187381
650176498
230996570
240823
55885287
1502298833
Returns: 749588418
780685373
991161
247216
93141
1363446327
Returns: 510293084
723077931
104066
241679
1
1301697396
Returns: 74439101
554286950
729607861
246177
50010
183808378
Returns: 388613004
769887201
725753527
249796
520715736
1708937855
Returns: 968154908
898054733
10443553
248376
601501272
1720060055
Returns: 822264170
947718052
814165864
248168
81102786
2043547395
Returns: 751601444
524668443
38560077
242171
187003764
2094311409
Returns: 623915640
1000000000
1000000000
250000
1000000000
53425
Returns: 837826199
1000000000
1000000000
250000
500000000
123
Returns: 316580880