NMNMX - Editorial

I used Chinese remainder theorem and Gaussian algorithm to find the remainder modulo (p-1) which is a composite number. Since p-1 = 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. p-1) will work as expected.

For those who are not aware:

Chinese remainder theorem

Let n1,n2,…,nr be positive integers such that gcd(ni,nj)=1 for i ≠ j. Then the system of linear congruences

x ≡ c1 (mod n1); x ≡ c2 (mod n2); … ; x ≡ cr (mod nr)
has a simultaneous solution which is unique modulo n1n2…nr.

Gauss’s algorithm

If x ≡ c1 (mod n1); x ≡ c2 (mod n2); … ; x ≡ cr (mod nr) and
let N=n1n2n3…nr then

x ≡ c1N1d1 + c2N2d2 + … + crNrdr (mod N)
where Ni = N/ni and di ≡ (Ni)-1 (mod ni).

Hence, in our case, N = 10^9 + 6. n1 = 2 and n2 = 500000003.

N1 = 500000003 and N2 = 2.

Also, the remainders w.r.t. 2 and 500000003 can easily be calculated and applied in the Gaussian formula above.

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

3 Likes

One can also read “Euler Totient Function” theory for understanding the modulo part. Link : Euler's totient function - Wikipedia

A beautiful problem and equally beautiful editorial - Thank You

What is the use of Fermat little theorem here ? could it be done just by using modular exponentiation ?

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?

For people having difficulty in understanding why we mod the power with (m-1) :

This is a very neat proof.

Please upvote if I helped so that I can qualify to upvote others. :))

1 Like

Hello everyone Refer my answer for query about \mod{p-1}

#link: NMNMX whats wrong - #4 by l_returns - general - CodeChef Discuss
Feel free to ask queries :smiley:

Some good discussion also happened here- https://discuss.codechef.com/questions/131430/july-18-problem-discussion?sort=votes&page=1

Do have a look :slight_smile:

1 Like

You’re counting some cases more than once. Say, i is 5 and k is 4. You pick index 3 in your ‘pick a smaller number’ part and pick index 2 (there is only one number left to pick) in your (n-3, k-3) part. But that case is counted again when you pick index 2 in your ‘pick a smaller number’ part and index 3 for the (n-3,k-3) part.

I’m not 100% sure though. Try to calculate some values and see if they’re greater than expected.

Answer my question instead, please.

this link gives answer to your question only… I commented for only u but thought someone else also get the same doubt…

Since a^{p-1}=a^0 \mod p we can say that a^{x-k \cdot (p-1)}=a^x \mod p. If we take k = \left\lfloor\dfrac x {p-1} \right\rfloor, we will get mentioned equation.

Thanks to both. A little query, why can’t I add comment to any other answer except this one?

you need to have 50 reputation points for that. Currently you have 13.

Refer “new karma system” blog on discuss… For knowing minimum reputation to do stuff…

https://discuss.codechef.com/questions/68246/karma-on-codechef

Yes I gave same answer

This is the euler totient function
For prime numbers it is (p - 1). for the rest
https://en.wikipedia.org/wiki/Euler’s_totient_function#Computing_Euler’s_totient_function

thanks till now the clearest explanation.

1 Like