Problem Statement
This problem has a non-standard time limit: 3 seconds.
There are N boxes in a row. The boxes are labeled 0 through N-1. Box i currently contains C[i] marbles.
Consider all possible ways of distributing M additional marbles into the boxes. We are going to choose one of these ways uniformly at random and we will distribute M additional marbles accordingly.
Formally, we are going to choose one sequence of nonnegative integers X[0], X[1], ..., X[N-1] such that sum(X) = M, and we will increment each C[i] by the corresponding X[i].
Once we distributed all the additional marbles, we will compute the product of the new numbers of marbles in all boxes. Let A/B be the expected value of that product as a reduced fraction, and let P be the prime number 998,244,353. Calculate and return the value (A*B-1) modulo P, where B-1 is the inverse of B modulo P.
You are given the
A[0] = seed
for i=1 to N-1:
A[i] = (A[i-1]*1103515245 + 12345) modulo 2147483648
C = B
for i=size(B) to N-1:
C[i] = A[i] modulo 998244353
Definition
- Class:
- ProductAndProduct
- Method:
- findExpectedProduct
- Parameters:
- int, int[], int, int
- Returns:
- int
- Method signature:
- int findExpectedProduct(int N, int[] B, int M, int seed)
- (be sure your method is public)
Notes
- Two ways of distributing the marbles (X0,X1,..XN-1) and (Y0,Y1,..YN-1) are considered different if Xi ≠ Yi for some i.
Constraints
- N will be between 1 and 100,000, inclusive.
- Number of elements in B will between 0 and min(N, 100), inclusive.
- Each element of B will be between 0 and 998,244,352, inclusive.
- M will be between 0 and 100,000, inclusive.
- seed will be between 0 and 2,147,483,647, inclusive.
Examples
6
{}
9
1022219453
Returns: 349570005
5
{}
5
1888563433
Returns: 629258651
9
{}
10
796932720
Returns: 610929501
2
{}
7
295050285
Returns: 714395600
2
{}
8
162766991
Returns: 463554205
4
{}
8
152920465
Returns: 692953010
4
{}
1
444077075
Returns: 102982316
1
{}
10
330119984
Returns: 330119994
9
{}
0
1545006115
Returns: 283745292
3
{}
3
478987731
Returns: 779288826
8
{}
1
1774577444
Returns: 862267529
8
{}
10
1849300380
Returns: 141151418
6
{}
7
50952706
Returns: 101139856
1
{}
2
258992885
Returns: 258992887
4
{}
0
177454525
Returns: 253423351
7
{}
2
1742541753
Returns: 349535076
8
{}
10
110208823
Returns: 805466554
6
{}
10
668058785
Returns: 585920520
2
{}
9
1097364796
Returns: 308835588
6
{}
3
682981105
Returns: 353731167
406
{}
15884
704741586
Returns: 713438792
789
{}
37628
1163007587
Returns: 415103068
38
{}
70112
204135364
Returns: 581586422
460
{}
62482
19368788
Returns: 606277290
795
{}
18467
713517418
Returns: 39726550
561
{}
70056
1229778221
Returns: 17900736
725
{}
92893
1447648699
Returns: 399134698
306
{}
80013
2287893
Returns: 395469819
55
{}
13207
1807634069
Returns: 471236698
504
{}
31602
1132800213
Returns: 183663772
625
{}
9380
1607222091
Returns: 194648518
487
{}
59910
595510796
Returns: 428881430
726
{}
9361
2015587952
Returns: 645499741
611
{}
78457
168301972
Returns: 112917069
935
{}
27766
945323491
Returns: 984152990
294
{}
69387
1799509812
Returns: 139581596
159
{}
68456
1201122588
Returns: 970528295
599
{}
89624
222303623
Returns: 302028193
456
{}
99024
124323254
Returns: 755681768
205
{}
32813
787431980
Returns: 241011807
814
{}
69755
575830589
Returns: 548213758
988
{}
37946
2070698544
Returns: 622961277
474
{}
83081
189056825
Returns: 175524820
799
{}
74778
1109663416
Returns: 897480066
681
{}
57013
854345339
Returns: 291223169
815
{}
11776
552840691
Returns: 718443092
998
{}
31169
1081548967
Returns: 53321136
978
{}
21853
1009584192
Returns: 487692767
989
{}
78999
1852213506
Returns: 962226250
351
{}
25803
1699237275
Returns: 223747973
64459
{}
47753
64024446
Returns: 577637365
81320
{}
39543
341327694
Returns: 951537334
73887
{}
27865
1700222212
Returns: 49575972
88721
{}
50778
1314050517
Returns: 145351712
82132
{}
29541
959983105
Returns: 525395124
71510
{}
28962
992271122
Returns: 267171720
69864
{}
81547
1436450612
Returns: 530150371
94850
{}
8809
379201714
Returns: 424404396
60869
{}
13671
298590391
Returns: 383373899
74362
{}
65841
1721862879
Returns: 143201900
88017
{}
54638
1883919179
Returns: 133923516
62655
{}
91335
480157480
Returns: 310527985
58702
{}
36776
1948521448
Returns: 354927749
90796
{}
5716
1855023021
Returns: 891500837
66250
{}
24506
999414149
Returns: 741885876
74067
{}
74669
1142815375
Returns: 625780613
61888
{}
84945
1236183333
Returns: 564139983
51153
{}
63624
1395447191
Returns: 786924261
54715
{}
35085
1158327331
Returns: 763659482
75601
{}
79106
1278648869
Returns: 567773464
69936
{}
370
209171647
Returns: 597073350
83056
{}
41361
1603564892
Returns: 531126745
65458
{}
24308
2088787176
Returns: 871883915
98823
{}
86433
530569357
Returns: 718677960
82200
{}
91661
1624943436
Returns: 157954460
88519
{}
37508
1196172769
Returns: 687895329
58833
{}
98347
202599070
Returns: 407817942
50001
{}
15484
1047332170
Returns: 472175271
91859
{}
53446
1323802407
Returns: 879735000
75769
{}
21464
609490347
Returns: 548839071
100000
{}
98854
1451607697
Returns: 526595724
100000
{}
90255
984575349
Returns: 677206917
100000
{}
91977
2111616750
Returns: 298476886
100000
{}
99708
1333841391
Returns: 899798481
100000
{}
93429
399665943
Returns: 554837298
100000
{}
92468
1089641270
Returns: 174224683
100000
{}
90392
1893394960
Returns: 809775300
100000
{}
98727
968684896
Returns: 668218399
100000
{}
92818
1754901535
Returns: 413222851
100000
{}
98509
1500954117
Returns: 176076051
100000
{}
95410
1778188112
Returns: 314759848
100000
{}
99900
515032259
Returns: 663386494
100000
{}
99100
1890679793
Returns: 686753586
100000
{}
95927
568722363
Returns: 203831434
100000
{}
97117
1222609174
Returns: 176258647
100000
{}
90265
1797843985
Returns: 915499075
100000
{}
90120
577040662
Returns: 360154143
100000
{}
96358
489013871
Returns: 730247129
100000
{}
96923
1157400076
Returns: 499505356
100000
{}
96682
1741032322
Returns: 54257605
100000
{}
100000
788911703
Returns: 733276232
100000
{}
100000
488419866
Returns: 555569452
100000
{}
100000
896600188
Returns: 19048071
100000
{}
100000
1745697085
Returns: 164785502
100000
{}
100000
752808218
Returns: 846852793
100000
{}
100000
1199695763
Returns: 540916759
100000
{}
100000
1307394961
Returns: 330995684
100000
{}
100000
1677496229
Returns: 325619228
100000
{}
100000
50477756
Returns: 541251578
100000
{}
100000
1377923188
Returns: 678774654
100000
{}
100000
976694394
Returns: 282569688
100000
{}
100000
1999691418
Returns: 44363038
100000
{}
100000
425349482
Returns: 279866623
100000
{}
100000
688905135
Returns: 85035665
100000
{}
100000
215926005
Returns: 381446127
100000
{}
100000
3686381
Returns: 555736347
100000
{}
100000
847118736
Returns: 881303822
100000
{}
100000
1280268823
Returns: 566329748
100000
{}
100000
1388207426
Returns: 895007364
100000
{}
100000
783034773
Returns: 626793930
100000
{}
100000
499534436
Returns: 187211864
100000
{}
100000
1728354019
Returns: 47935359
100000
{}
100000
1478254759
Returns: 313572488
100000
{}
100000
1611353644
Returns: 347824815
100000
{}
100000
2138075739
Returns: 214822660
100000
{}
100000
1782456370
Returns: 753197820
100000
{}
100000
512373230
Returns: 821757339
100000
{}
100000
1556024688
Returns: 429645272
100000
{}
100000
1044261810
Returns: 467786399
100000
{}
100000
1964007297
Returns: 949276326
100000
{}
100000
1477580770
Returns: 664642163
100000
{}
100000
1496216770
Returns: 752827832
100000
{}
100000
1648740582
Returns: 122309744
100000
{}
100000
168305206
Returns: 482056157
100000
{}
100000
2089171414
Returns: 297982430
100000
{}
100000
2030096298
Returns: 757086387
100000
{}
100000
887390524
Returns: 33802519
100000
{}
100000
1345696281
Returns: 667406314
100000
{}
100000
1962002513
Returns: 737027313
100000
{}
100000
1040500026
Returns: 30010830
100000
{}
100000
1683127765
Returns: 465136461
100000
{}
100000
838110355
Returns: 340828020
100000
{}
100000
1842944005
Returns: 811181333
100000
{}
100000
1328194348
Returns: 271569515
100000
{}
100000
214126972
Returns: 377234741
100000
{}
100000
2084056850
Returns: 551058434
100000
{809781192, 789593200, 154689592, 607589407, 833571747, 350489159, 560096464, 561523319, 372918301, 88516750, 987337805, 866703978, 96823697, 726200118, 55127381, 253401742, 824049134, 183366688, 980462306, 886545980, 92100177, 831925891, 536131234, 103307587, 553966922, 635282063, 459236380, 390559504, 458445945, 486875819, 666635573, 882043408, 19463601, 348041917, 410654833, 918629889, 780408085, 936131320, 791334742, 263710411, 864401670, 555797217, 562082846, 350714094, 76839818, 881541927, 291551968, 968471805, 201596778, 751646022, 792000926, 543766444, 265109103, 270707014, 1655753, 145214447, 943074599, 488619711, 107716602, 995215002, 389641669, 385486588, 494419397, 695423081, 806395773, 86447126, 478474068, 324688946, 334858008, 866799770, 404180009, 899882522, 579654104, 193271550, 996655363, 501285749, 112853262, 883146838, 841270170, 191121877, 690409264, 919299694, 685113998, 815375156, 484845879, 593047506, 543961464, 206171850, 945140901, 183434963, 310791204, 3352622, 325359292, 647961598, 91529912, 843234102, 34013447, 218675674, 402326257, 363380688}
100000
1774700473
Returns: 529295096
100000
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
100000
1795984462
Returns: 206885093
100000
{998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352, 998244352}
100000
1599219247
Returns: 19005717
3
{1, 2, 3}
0
0
Returns: 6
As M=0, we are not distributing any additional marbles. Formally, the only valid sequence is X = {0,0,0}, so we choose and apply this sequence. The final counts of marbles will be {1, 2, 3}, hence the expected value of their product is 1*2*3 = 6.
3
{1, 2, 3}
1
0
Returns: 665496245
Now M=1, which means that we are adding one extra marble somewhere. After we do so, we will obtain one of the following three arrays C: {2, 2, 3}, {1, 3, 3}, or {1, 2, 4}. Each of these arrays will be generated with probability 1/3. Thus, the expected product is (2*2*3 + 1*3*3 + 1*2*4) / 3 = 29 / 3. We have 3-1 (mod P) = 332,748,118, and therefore the correct return value is (29 * 332,748,118) modulo P.
4
{0,0,0,0}
3
0
Returns: 0
Regardless of how we distribute the three additional marbles, at least one C[i] will remain zero, and therefore the product will remain zero as well.
100000
{}
100000
369273885
Returns: 164185046