Contest Details:

Has become? I don't remember a time when this was not the norm at CodeChef.

Without the MODULO N thing, the answer would be (sum(arr)/n)^k (Handle the MODULO 1e9 + 7)

Because of the MODULO our numerator would change

Consider this case: n = 3, k = 2 ,arr = [a,b,c]

k = 0 numerator = 1%MOD

k = 1 numerator = ((1*a)%n + (1*b)%n + (1*c)%n)%MOD

k = 2 numerator = ((a*a)%n + (b*b)%n + (c*c)%n + 2*(a*b)%n + 2*(b*c)%n + 2(a*c)%n )%MOD

Basically it is a variant of polynomial multiplication (exponentiation) Now while implementing this you need to consider remainder modulo N as the exponent and its number of occurrences as the coefficient.

Let's solve the counting version of this problem, instead of the expectation version.
For each z in [0,N-1], we want to count the number of way the score can equal z.

Think what you could do if K was 2?
Can you come up with a dp solution in O(N^2)? Something like this :

for each i,j < N   
ways [2] [ (i * j) % N ] += ways [1] [i] * ways[1] [j]

Here ways [x] [y] = number of way the score can equal y after first x moves.

Continuing this dp, you definitely can solve the original problem in O(N^2 * K).
But think carefully that you almost repeat the same thing in every step and actually you can do something like binary exponentiation here. Actually you can thus calculate ways[4] from ways[2], ways[8] from ways[4] and so on.

I think you will get the idea if you think a bit.

for me, I do simulation on x and y until 2e9 (I do it on precompute) to get all valid x, then it turns out that it only shows 61 x's, so just precompute it, save it in an array, then do binary search to get answer

Just implement Editorial's approach. You will get AC. My Soln.

Its because the editorial has not beeen published yet.Hopefully I think it will be published in few hours.

Yes, your idea is correct if the move is : S = S * X
But in this problem, we had : S = (S * X) % n
I think that is what you are missing here.