Game of Length solution codechef

For Solution
Click Here!
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 P⋅Q−1mod998244353P⋅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 spaceseparated 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
 1≤T≤2⋅1041≤T≤2⋅104
 1≤N≤5⋅1051≤N≤5⋅105
 1≤Ai≤5⋅1051≤Ai≤5⋅105
 Sum of NN does not exceeds 5⋅1055⋅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 2⋅12+1⋅122⋅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 3⋅16+2⋅12+1⋅133⋅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 2⋅23+1⋅132⋅23+1⋅13 which is equal to 5353.

For Solution
Click Here!