Problem Statement
This problem has an unusual time limit of 5 seconds.
Teja and Raja are experienced players in CSGo (Catch the Strawberry and go). CSGo is a two-player game consisting of n rounds. Teja and Raja play alternate rounds, Teja goes first. (Thus, Teja plays rounds 1, 3, 5, ..., while Raja plays rounds 2, 4, 6, ...)
At the beginning of the entire game Teja and Raja each have zero strawberries. In each round of CSGo, the active player can gain between 0 and 2*k strawberries. The actual number of strawberries gained is a random event (more details below) and all these random events are mutually independent.
You are given the values n, k, Arange, Brange, and seed. Use the following pseudocode to generate arrays A and B, each of length 2*k+1:
state = seed
for i = 0 .. 2*k:
state = (1103515245 * state + 12345)
state = state modulo 2^31
A[i] = state modulo Arange
state = (1103515245 * state + 12345)
state = state modulo 2^31
B[i] = state modulo Brange
For each valid index i, let pA(i) = A[i] / sum(A) and let pB(i) = B[i] / sum(B). The value pA(i) is the probability that Teja gains exactly i strawberries in any one round in which he is the active player. The value pB(i) is the same for Raja.
For spectators a game of CSGo is competitive if the absolute difference between the number of Teja's and the number of Raja's strawberries never exceeds k. (I.e., after each round the difference must be k or less.)
What is the probability with which the game between Teja and Raja will be competitive? It can be shown that the answer is always rational. Let X/Y be the answer in reduced form. Let Z = Y^(-1) be the inverse element to Y when computing modulo 10^9 + 7. Compute and return the value (X*Z) modulo 10^9 + 7.
Definition
- Class:
- StrawberryHard
- Method:
- competitive
- Parameters:
- int, int, int, int, int
- Returns:
- int
- Method signature:
- int competitive(int n, int k, int Arange, int Brange, int seed)
- (be sure your method is public)
Notes
- The inverse element to Y when computing modulo 10^9 + 7 is the only Z in the range [0, 10^9 + 6] such that Y*Z = 1 (modulo 10^9 + 7).
- The constraints ensure that the answer is always well-defined: the probability is always a fraction X/Y such that Y has a unique inverse element.
Constraints
- n will be between 1 and 17 inclusive.
- k will be between 1 and 7000 inclusive.
- Arange and Brange will be between 1 and 10^9+7 inclusive.
- seed will be between 0 and 10^9+6 inclusive.
- Sum of elements of A will not be a multiple of 10^9+7.
- Sum of elements of B will not be a multiple of 10^9+7.
Examples
15
1596
750210936
595502725
350348366
Returns: 282765234
1
1673
864461633
165070685
666663580
Returns: 561063812
15
1183
557777258
738042995
693722696
Returns: 764916223
15
1862
401673940
74036498
438933226
Returns: 905150019
16
1033
523882665
929880015
242088165
Returns: 777221174
15
1962
466520881
558223176
783862666
Returns: 343544208
1
1384
465146766
405115508
938856082
Returns: 672311359
17
1149
819233702
901747811
546641884
Returns: 122050798
16
1860
590693447
190747631
384909075
Returns: 407166778
15
1833
104154976
415569232
779157255
Returns: 761046694
15
6817
801230931
203833176
778264399
Returns: 231642140
1
6998
823344263
150395448
609202958
Returns: 287159806
15
6867
49262863
845687682
635416410
Returns: 310981531
16
6972
644347827
319809696
327864704
Returns: 293449593
16
6872
255773761
297356911
622339044
Returns: 879842786
15
6879
915730077
590967688
878656139
Returns: 891899014
1
6833
133050746
745149413
637523041
Returns: 422750640
16
6815
378921912
640622953
729317556
Returns: 503059759
15
6969
378102176
605874303
12830618
Returns: 535903595
17
6860
597027298
727759046
715559461
Returns: 780577509
15
6943
55850007
865638858
31915635
Returns: 11991512
17
7000
60222102
533242220
424685931
Returns: 905413783
17
7000
864747368
611132341
364054687
Returns: 894075822
17
7000
672080193
232427765
335555868
Returns: 477829983
17
7000
581235569
792058265
857523149
Returns: 717530351
17
7000
247942479
242830790
234779452
Returns: 604976857
17
7000
93151840
313704175
975913057
Returns: 615580144
17
7000
631758052
514899397
24007390
Returns: 321780741
17
7000
983619973
494690713
73367748
Returns: 247256682
17
7000
126338602
467625876
938384394
Returns: 424247138
17
7000
379709908
421529313
297113494
Returns: 10184130
17
7000
330006809
204025156
713703073
Returns: 459278004
17
7000
953909302
774177995
484270763
Returns: 579431423
17
7000
120203446
978056998
803306522
Returns: 580851084
17
7000
968590349
32452513
87340317
Returns: 955668072
17
7000
539082636
940119720
238252598
Returns: 193129869
17
7000
543016878
493053950
679145356
Returns: 917117539
17
7000
132327305
957195318
43894525
Returns: 883912299
17
7000
347630187
566961559
100142229
Returns: 389053023
17
7000
711530950
554234990
356313026
Returns: 234814204
17
7000
28361752
380994624
21806218
Returns: 510595143
17
7000
757497488
43391478
54628733
Returns: 34089248
17
7000
53387256
505972344
757857602
Returns: 275411837
17
7000
83251177
800675050
860948549
Returns: 572725115
17
7000
637609668
500633681
320543280
Returns: 43293015
17
7000
184842143
200873469
403456425
Returns: 391131509
17
7000
481373891
923139299
139571540
Returns: 286955985
17
7000
658122436
439460867
37931818
Returns: 57041398
17
7000
510686640
120957680
629433731
Returns: 760107109
17
7000
1000000007
1000000007
1000000006
Returns: 629612553
1
3
2
7
0
Returns: 571428576
The pseudocode should give you the arrays A = {1,1,1,1,1,1,1} and B = {2,3,0,0,1,1,0}. This game consists of just one round in which Teja gains some strawberries. If Teja gains between 0 and 3 strawberries, the game will be competitive, if he gains more, it won't be. The probability that Teja gains between 0 and 3 strawberries is 4/7. Thus, we have X = 4 and Y = 7. We can compute that Z = 142,857,144 and therefore the answer you should return is (X*Z) modulo (10^9 + 7) = 571,428,576.
6
3
3
3
740562
Returns: 1
The arrays are A = {1, 2, 0, 0, 0, 0, 0} and B = {1, 1, 0, 0, 0, 0, 0}. This game has six rounds. In each round, the active player gains at most one strawberry. (Note that the probability of gaining more strawberries is zero.) Thus, the difference between the numbers of Teja's and Raja's strawberries never exceeds 3 and the game is guaranteed to be competitive.
7
3
3
3
740562
Returns: 753086426
If Teja always gains a strawberry and Raja never does, the game will not be competitive. Thus, the probability that this game won't be competitive is (2/3)^4 * (1/2)^3.
7
5
11
13
47
Returns: 931930680
17
7000
101
103
47
Returns: 78840230
17
7000
11
13
47
Returns: 365138596
17
7000
7000
10000
1
Returns: 990546039
17
7000
34
432
22
Returns: 562849213
17
7000
6999
6997
47
Returns: 945117911
17
7000
123456789
21366544
342
Returns: 335263892
17
7000
2
7
0
Returns: 725214606
17
7000
11451400
11111111
364364
Returns: 953851821
17
7000
3
3
740562
Returns: 709004894
17
7000
12324551
43278155
4123789
Returns: 936870352
17
7000
100500
435503
5454
Returns: 385560673