Game of Length solution codechef

Game of Length solution codechef

Alice and Bob are given an array of length of NN. They decide to play a game with it.

Initially, Alice randomly shuffles the array, and then Bob takes NN turns. In each turn, Bob chooses an index which he has not already chosen and then Alice reveals the number on that index to Bob. If this number is either the first number to be chosen or strictly larger than previously chosen numbers by Bob then he takes it and adds to his array else he throws it. Game of Length solution codechef

You only know the initial unshuffled array and want to know the expected length of Bob’s array at the end of the game.

The final expected length can be represented as a fraction of the form PQPQ. You are required to print PQ1mod998244353P⋅Q−1mod998244353.

Input Format Game of Length solution codechef

  • First line will contain TT, number of testcases. Then the testcases follow.
  • Each testcase contains two lines of input.
  • The first line contains NN the length of the array.
  • The second line contains NN space-separated integers A1,A2,...,ANA1,A2,…,AN representing the initial array.

Output Format

For each testcase, output in a single line the expected length of Bob’s array at the end of the game modulo 998244353998244353.

Constraints Game of Length solution codechef

  • 1T21041≤T≤2⋅104
  • 1N51051≤N≤5⋅105
  • 1Ai51051≤Ai≤5⋅105
  • Sum of NN does not exceeds 51055⋅105 over all testcases.

Sample Input 1  Game of Length solution codechef 

4
2
1 2
3
1 2 3
3
1 1 1
3
2 3 2

Sample Output 1  Game of Length solution codechef 

499122178
831870296
1
665496237

Explanation Game of Length solution codechef

Test case 11: The possible final arrays will be [2,1][2,1] or [1,2][1,2]. If Bob chooses indexes in the order [2,1][2,1] then he will end up with 22 elements in the first case and 11 element in the second case, if he chooses indexes in the order [1,2][1,2] then he will end up with 11 element in the first case and 22 elements in the case. Hence his probability ending up with 22 elements is 1212 and with 11 element is also 1212. Hence the final answer will be calculated as 212+1122⋅12+1⋅12 which is equal to 3232.

Test case 22: The probability of Bob ending up with all three elements is 1616, the probability that he ends up with any two elements is 1212 and the probability that he ends with only a single element is 1313. Hence the final answer is calculated as 316+212+1133⋅16+2⋅12+1⋅13 which is equal to 116116.

Test case 33: No matter what index Bob chooses initially he will only end up with 11 element in his final array. Hence the final expected value is equal to 11.

Test case 44: The probability of Bob ending up with all three elements is 00, the probability that he ends up with any two elements is 2323 and the probability that he ends with only a single element is 1313. Hence the final answer is calculated as 223+1132⋅23+1⋅13 which is equal to 5353.

Leave a Comment