Problem Statement
There are N cities in Absurdistan. They are numbered from 0 to N-1.
For simplicity, we will assume that city x has exactly (x+1) inhabitants.
Initially, no two cities were connected by roads. Then there was a Y-year period of road construction.
During this period, two cities become reachable from each other as soon as there exists a sequence of one or more roads that allows you to travel between them.
The years of the road construction period were numbered from 0 to Y-1. For each year x:
- During July of year x exactly one new road was constructed: a bidirectional road connecting the cities A[x] and B[x].
- Then, during December of year x each inhabitant of the country sent a Christmas postcard to each other inhabitant. All postcards that could reach their destination were delivered. All postcards that could not be delivered were burned by the post office.
Count the total number of delivered postcards during these Y years. Return that count modulo 10^9 + 7.
In order to keep the input small, the arrays A and B are generated pseudorandomly. Please use the following pseudocode to generate them:
state = seed
for i = 0 to Y-1:
state = (state * 1103515245 + 12345) modulo 2^31
A[i] = state modulo N
state = (state * 1103515245 + 12345) modulo 2^31
B[i] = state modulo N
Definition
- Class:
- Postcards
- Method:
- count
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int count(int N, int Y, int seed)
- (be sure your method is public)
Notes
- It is possible that in some years the new road will connect two cities that already were (directly or indirectly) connected. It is also possible that in some years the new road will connect a city to itself. In both cases there will be no changes to reachability between cities.
- The reference solution does not depend on the input being pseudorandom.
Constraints
- N will be between 1 and 10^9, inclusive.
- Y will be between 1 and 150,000, inclusive.
- seed will be between 0 and 2^31 - 1, inclusive.
Examples
7
1
47
Returns: 112
There is only one year. In July the people build a road that connects city 5 to itself. In December the people send postcards. As no two distinct cities are reachable, only postcards within each city will be delivered.
7
1
42
Returns: 122
This time the only road built connects cities 4 and 0. Compared to the previous example, the postcards sent from city 0 to city 4 or vice versa will also get delivered. This gives us an extra 10 postcards.
7
2
100
Returns: 348
The first road connects cities 0 and 6. Once this road is built a total of 126 postcards will be delivered. The second road then connects cities 5 and 6. During the second Christmas season the number of delivered postcards will be 222. (Don't forget about postcards between cities 0 and 5. These can now be delivered too.)
987654321
150000
47
Returns: 783886815
7654321
150000
4747
Returns: 511254732
654321
150000
436434
Returns: 538417691
7
20
100
Returns: 11942
Here is the full list of all 20 rows in the order in which they are built: 0-6, 6-5, 3-1, 3-3, 0-4, 6-3, 5-3, 1-6, 3-1, 3-2, 3-1, 4-5, 2-5, 6-4, 0-6, 3-6, 3-4, 1-4, 0-4, 1-1 In this test case Absurdistan eventually reaches the situation where in December all postcards get delivered: each of the 28 inhabitants of Absurdistan is able to reach each of the 27 other ones.
123
123
123
Returns: 410499337
The exact total is 1,410,499,344. Remember to compute and output it modulo 10^9 + 7.
947224005
7
1948501517
Returns: 865581717
976610214
1551
1660249968
Returns: 926848441
952669103
8
1133040875
Returns: 858582308
964632919
188
1542245923
Returns: 587123589
959353897
136
1607036031
Returns: 343144852
996198169
137
539016619
Returns: 348131818
944819066
13
1647457924
Returns: 709985664
968223645
11
1438208187
Returns: 854785967
929333809
39986
1789542187
Returns: 164668883
981155443
3220
1026423979
Returns: 759000908
974526545
2212
2078532398
Returns: 16847256
941903666
149219
1698564564
Returns: 316586478
934929325
148509
948917258
Returns: 497258896
981382227
141866
889428824
Returns: 861026592
950984921
147952
1087222470
Returns: 805177465
981003095
149142
640818900
Returns: 851108045
959577419
140248
731414135
Returns: 865337971
973416107
141356
320425005
Returns: 60993625
935668351
148376
2046595582
Returns: 682244549
958466976
145989
142514072
Returns: 482264518
802174
149971
2026408624
Returns: 215086031
875092130
140364
1043761029
Returns: 471061315
108
147071
790342737
Returns: 795274447
62
143255
549224465
Returns: 909677511
10
149332
1477705088
Returns: 443491998
116963
141770
1146177193
Returns: 473707604
16398
142005
1778417307
Returns: 843323859
6
140339
1134935596
Returns: 58940974
2
142968
2108757054
Returns: 857808
127
148655
1948158689
Returns: 566423623
267380
141209
752144434
Returns: 737361648
87317652
148903
1453170456
Returns: 424426821
1146483
143842
263002937
Returns: 422611363
5104
140363
380485713
Returns: 935159829
567
148976
1321413367
Returns: 191663764
166
149010
1173215853
Returns: 616048819
608911
149223
2109919775
Returns: 690161480
1130
141877
1775873863
Returns: 527566979
13987
144961
2101334812
Returns: 216324509
670723
141040
502796335
Returns: 89879988
516075037
9276
1235357188
Returns: 303995313
66451348
80495
1052781061
Returns: 309814023
3404
61
97040700
Returns: 225600196
313621
25453
102151484
Returns: 75047007
180692
3
2073107849
Returns: 538822669
4656
11548
392755518
Returns: 495151980
12
6821
1546714289
Returns: 20682374
163423242
2253
1502298833
Returns: 698830183
291753
363
1244362723
Returns: 842656838
123
30816
1363446327
Returns: 985693442
148920230
31
2642986
Returns: 800348459
1
122929
1106908031
Returns: 0
616
638
729061624
Returns: 643362583
13707
60686
1007203776
Returns: 812302788
100021
1071
1629169908
Returns: 16798867
258188223
43
334718070
Returns: 240925081
59704
2
1983085133
Returns: 127706839
57
1
312614420
Returns: 64728
233075
1
2144595767
Returns: 19070669
16024318
118028
438548027
Returns: 926143209
7
9900
750893228
Returns: 7479988
536100867
61554
402545275
Returns: 374096721
6778
11413
1358865986
Returns: 395334561
4707
31
1430484067
Returns: 440688081
1268447
504
398184188
Returns: 449197303
2169
4762
963098471
Returns: 917793232
93163
99310
1316725677
Returns: 676144151
80443
693
2097118814
Returns: 143792021
6218571
7979
30401546
Returns: 811931024
471639
1155
674631869
Returns: 895319746
317660
174
343476289
Returns: 320291987
21
4
540951194
Returns: 16202
468600
14
1266477948
Returns: 686612946
188624
8
866820893
Returns: 188423247
42645783
1210
1371506773
Returns: 117109846
31170965
111693
1827507600
Returns: 492115135
1969481
14960
2107368689
Returns: 493196956
1
1124
1840506704
Returns: 0
322719420
20448
413576938
Returns: 534501325
224053682
9158
1433250621
Returns: 352070647
46135623
63896
513342065
Returns: 956011832
783229648
67
2119888712
Returns: 971879924
1314
4
1282909328
Returns: 29707783
2
432
825599650
Returns: 2592
187448
3566
573850115
Returns: 365775322
121
10007
1815175106
Returns: 529411896
123253758
4086
1103050310
Returns: 504010932
3
197
1741737939
Returns: 5856
2
5658
1792312856
Returns: 33948
2411
3436
1894985334
Returns: 681553879
152412062
50253
276409821
Returns: 892857497
45
236
2029977897
Returns: 196582512
46805254
518
490428354
Returns: 547536935
536727
365
1600605750
Returns: 285023807
46809
1844
164647511
Returns: 146549771
3836615
1729
32134090
Returns: 40728027
8
561
939197325
Returns: 206040
67559935
2
1646888126
Returns: 858854567
517563765
75
1190803699
Returns: 811853941
3755704
111131
162392144
Returns: 758376053
1000000000
150000
1
Returns: 240530864
1000000000
150000
999999999
Returns: 629964670
1000000000
150000
20
Returns: 512516146
1000000000
1
234
Returns: 472949513
1000000000
150000
100
Returns: 303967585
1000000000
100000
111
Returns: 287371035
1000000000
150000
12121212
Returns: 169730998
1000000000
150000
12345
Returns: 461330490