PROBLEM LINK:Author: Full name Tester: Full name Editorialist: Oleksandr Kulkov DIFFICULTY:EASY PREREQUISITES:Fermat's little theorem, modular arithmetics, basic combinatorics PROBLEM:You're given sequence of distinct integers $a_1,\dots,a_N$ and integer $K$. For each of its subsequences of size $K$ you have to calculate product of all the elements except for minimum and maximum ones. After that you have to calculate product of these values among all subsequences. QUICK EXPLANATION:Sort the sequence, after that multiply all elements raised to power $\binom{N1}{K1}\binom{i1}{K1}\binom{Ni}{K1}$ using Fermat's theorem. EXPLANATION:Since it doesn't matter in this problem if we consider subsequences or subsets, we can suppose that array is sorted. Now element $a_i$ will occur in $\binom{N1}{K1}$ subsequences. Among them in $\binom{i1}{K1}$ it will be the maximum element and in $\binom{Ni}{K1}$ it will be minimum element, so you should subtract these values from $\binom{N1}{K1}$ to get number of subsequences in which particular element $a_i$ will actually be counted in product. Now to calculate final product we can raise each element to the power equals to number of subsequences it will be counted in. To do this we'll use Fermat's little theorem: $$a^{p1}=1 \pmod p$$ Which is true for prime $p$ and $a \neq 0 \pmod p$. Since $1=a^0$ for any $a$, we could say that $a^x=a^{x \pmod{p1}}\pmod p$. Now the only thing left to do for us is to calculate binomial coefficients modulo $p1$. This is not prime number thus we can't do it by calculating factorials and their reverses in advance but since $N$ is sufficiently small, we can just calculate all binomial coefficients in $N^2$ using following recurrent formula: $$\binom{n}{r}=\binom{n1}{r}+\binom{n1}{r1}$$ This one is very famous, has many interpretations and can be easily proven. For example, number of ways to choose $r$ items among $n$ can be split between subsets having $n$th item and subsets which don't have it. Number of first ones is $\binom{n1}{r1}$ and number of second ones is $\binom{n1}{r}$. Given all that you can solve the problem precalculating all binomial coefficients modulo $p1$ and using binary exponentiation to raise $a_i$ in corresponding powers. Complexity of whole solution should be $O(N^2+N \log p)$. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. Tester's solution can be found here.
This question is marked "community wiki".
asked 16 Jul '18, 05:16

I have used python3. So I need not have to bother about $a^m mod p$ for large value of m. The inbuild pow(a,m,p) would do that in an efficient way. Now suppose we have n=6, k=3 and we have sorted array 
If we consider every element in every subset then each of the elements comes $\binom{n1}{k1}$ 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[n1]) = $\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[n1])$ = $\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>nk$ then $i^{th}$ element will never be minimum. So, in general min_count = $[\binom {n1} {k1}\ \binom {n2} {k1}\ \binom{nk1} {k1}\ \binom {nk}{k1}\ {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 {k1} {k1}\ \binom {k} {k1}\ \binom{k+1} {k1}....\binom {n1}{k1}\ ]$ 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 {n1} {k1}$ , $\binom {n2} {k1}$....$\binom {nk} {k1}$ . So we have used little combinational knowledge to calculate $\binom {n2} {k1}$ from $\binom {n1} {k1}$ by this  $\binom {n2} {k1} = \binom {n1} {k1}\ * (nk)/(n1)$ Now think carefully, the max_count is the reverse of min_count. i.e max_count[i]=min_count[ni1] So Power[i]= total  (min_count[i] + min_count[ni1]) Again you will see Power[i] = Power[ni1]. i.e A[i] and A[ni1] 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[ni1]^{Power[i]}) mod p$ Here is my solution  link text answered 17 Jul '18, 17:25

a^x=a^x(modp−1)(modp) how??? answered 16 Jul '18, 23:14
Hello everyone Refer my answer for query about $\mod{p1}$link: https://discuss.codechef.com/questions/131526/nmnmxwhatswrong/131541Feel free to ask queries :D
(16 Jul '18, 23:19)
Answer my question instead, please.
(17 Jul '18, 18:23)
this link gives answer to your question only... I commented for only u but thought someone else also get the same doubt...
(17 Jul '18, 21:15)
Since $a^{p1}=a^0 \mod p$ we can say that $a^{xk \cdot (p1)}=a^x \mod p$. If we take $k = \left\lfloor\dfrac x {p1} \right\rfloor$, we will get mentioned equation.
(18 Jul '18, 00:46)
Thanks to both. A little query, why can't I add comment to any other answer except this one?
(18 Jul '18, 08:13)
you need to have 50 reputation points for that. Currently you have 13.
(18 Jul '18, 08:30)
Refer "new karma system" blog on discuss... For knowing minimum reputation to do stuff...
(18 Jul '18, 11:15)
https://blog.codechef.com/2014/11/18/thenewkarmasystem/
(18 Jul '18, 11:18)
This is the euler totient function For prime numbers it is (p  1). for the rest https://en.wikipedia.org/wiki/Euler%27s_totient_function#Computing_Euler's_totient_function
(18 Jul '18, 19:23)
showing 5 of 9
show all

For people having difficulty in understanding why we mod the power with (m1) : This is a very neat proof. Please upvote if I helped so that I can qualify to upvote others. :)) answered 30 Jul '18, 04:07

I used Chinese remainder theorem and Gaussian algorithm to find the remainder modulo (p1) which is a composite number. Since p1 = 10^9+6 has only two prime factors (2 and 500000003). Calculating modulo w.r.t. 2 and 500000003 and then using Gaussian algorithm to find the remainder w.r.t. the product (i.e. p1) will work as expected. For those who are not aware: Chinese remainder theorem Let n_{1},n_{2},...,n_{r} be positive integers such that gcd(n_{i},n_{j})=1 for i ≠ j. Then the system of linear congruences x ≡ c_{1} (mod n_{1}); x ≡ c_{2} (mod n_{2}); ... ; x ≡ c_{r} (mod n_{r}) has a simultaneous solution which is unique modulo n_{1}n_{2}...n_{r}. Gauss's algorithm If x ≡ c_{1} (mod n_{1}); x ≡ c_{2} (mod n_{2}); ... ; x ≡ c_{r} (mod n_{r}) and let N=n_{1}n_{2}n_{3}...n_{r} then x ≡ c_{1}N_{1}d_{1} + c_{2}N_{2}d_{2} + ... + c_{r}N_{r}d_{r} (mod N)
where N_{i} = N/n_{i} and d_{i} ≡ (N_{i})^{1} (mod n_{i}).
N_{1} = 500000003 and N_{2} = 2. Also, the remainders w.r.t. 2 and 500000003 can easily be calculated and applied in the Gaussian formula above. answered 17 Jul '18, 05:44
@ritam777 During the contest, I was trying to do this but could not. Thank you so much as I now understand it :)) Sorry I am not qualifed to upvote otherwise I would have.
(30 Jul '18, 04:08)

One can also read "Euler Totient Function" theory for understanding the modulo part. Link : https://en.wikipedia.org/wiki/Euler%27s_totient_function answered 18 Jul '18, 12:45

A beautiful problem and equally beautiful editorial  Thank You answered 18 Jul '18, 21:29

What is the use of Fermat little theorem here ? could it be done just by using modular exponentiation ? answered 20 Jul '18, 13:53

Since 1=a0 for any a, we could say that a^x=a^x(modp−1)(modp). I am trying but not able to figure out how the statement comes out of Fermat's little theorem and the fact that a raised to 0 becomes 1. Can someone please elaborate? answered 26 Jul '18, 18:02

Some good discussion also happened here https://discuss.codechef.com/questions/131430/july18problemdiscussion?sort=votes&page=1
Do have a look :)
Why do subset or subsequence doesn't matter?