I have used python3. So I need not have to bother about a^m mod p for large value of m. The in-build pow(a,m,p) would do that in an efficient way.
Now suppose we have n=6, k=3 and we have sorted array -
A = [1 2 3 4 5 6]
If we consider every element in every subset then each of the elements comes \binom{n-1}{k-1} times. In this case total = \binom 5 2
If we consider all the 3 element subsequences involving 1(A[0]) then the number of subsequences where 1 is minimum is equal to number of ways to choose 2 elements from the array (2..6) i.e. ( A[1]…A[n-1]) = \binom 5 2 as A[] is already sorted
Similarly the number of subsequences where 2 is minimum is equal to number of ways to choose 2 elements from array (3..6) i.e. (A[2]..A[n-1]) = \binom 4 2 and so on.
So we have created an array min_count[] where i^{th} element represents the number of times A[i] is minimum in a 3 element subsequences involving A[i].
In this case min_count = [\binom 5 2\ \binom 4 2\ \binom3 2\ \binom 2 2\ {0}\ {0} ]
Look carefully, element 5,6 will never be minimum in any 3 element subsequences .In general if i>n-k then i^{th} element will never be minimum.
So, in general min_count = [\binom {n-1} {k-1}\ \binom {n-2} {k-1}\ \binom{n-k-1} {k-1}\ \binom {n-k}{k-1}\ {0}\ {0} ..0 ]
Using Similar logic we created an array max_count[] where i^{th} element represents the number of times A[i] is maximum in a 3 element subsequences involving A[i].
max_count = [0\ 0...\binom {k-1} {k-1}\ \binom {k} {k-1}\ \binom{k+1} {k-1}....\binom {n-1}{k-1}\ ]
Now come to main problem. The total number of A[i] comes in all the subsequences excluding minimum and maximum = total -(min_count[i]+max_count[i]) which is our Power[i]
Our answer will be Ans = \prod\ A[i]^{Power[i]} mod p
Wow, We are getting right answer. But wait, what if N = 5000 ?
It will take too much time to calculate min_count if we individually calculate \binom {n-1} {k-1} , \binom {n-2} {k-1}…\binom {n-k} {k-1} .
So we have used little combinational knowledge to calculate \binom {n-2} {k-1} from \binom {n-1} {k-1} by this - \binom {n-2} {k-1} = \binom {n-1} {k-1}\ * (n-k)/(n-1)
Now think carefully, the max_count is the reverse of min_count. i.e max_count[i]=min_count[n-i-1]
So Power[i]= total - (min_count[i] + min_count[n-i-1])
Again you will see Power[i] = Power[n-i-1]. i.e A[i] and A[n-i-1] will come same number of times.
Now we have to calculate product from i= 0 to n/2
Ans will be \prod\ (A[i]*A[n-i-1]^{Power[i]}) mod p
Here is my solution -
link text