NMNMX whats wrong

general
,
1

I have used that total occurance of an element in subsequence will be (n-1)C(k-1) and total times it will be min will be (x)C(k-1) where x is number of element greater than element and total times it will be max will be (y)C(k-1) where y is number of element lesser than element.

So total occurance of any element will be (n-1)C(k-1)-(x)C(k-1)-(y)C(k-1)

but i am getting only 20 points and cant able to figure out whats wrong please help

https://www.codechef.com/viewsolution/19194234

2

Hi @rk_221b
I too am using same logic and facing same problem as you are.
I am afraid we are not using the right method to calculate nCr%p, and that is the only reason for WA.
I found this comment on other discussion , but wasnt able to make anything out of it, If you are able to make something out of it. Please Do reply.

Here’s the comment:

3

you can use Fermat’s little theorem to optimize ncr for the solution and do this without using big int. I was using big int and getting 20 marks and 3 test cases were not passing due to TLE.

Fermat’s little theorem

ab-1 (modulo b) = 1 (modulo b)

if b is prime

if you would like to see my solution
here is the link https://www.codechef.com/viewsolution/19198262

4

I understood you are calculating :-

Click to view

m=10^9 + 7

FOR each element :

L= number of elements on left side of “element (whose power we r calculating)”

R= number of elements on left side of “element (whose power we r calculating)”

occurrences=( ( \binom{n-1}{k-1}\mod m ) - (\binom {L}{k−1} \mod m) - ( \binom {R}{k−1} \mod m) )\mod m
(element)^{occurrences}\mod m

WHICH IS INCORRECT !!!

Note that (2^{10}\mod 7) = (1024 \mod 7) = 2

BUT ( 2^{(10 \mod 7)} \mod 7 ) = (2^3 \mod 7 ) = ( 8 \mod 7 ) = 1

And 1!=2

So point is you can’t modulo the power with mod you use for ((a^b) \mod m) != (a^{(b \mod m)} \mod m)

Solution for that is ((a^b) \mod m) == (a^{(b \mod (phi(m)))} \mod m)

ONLY WHEN a and b are co-prime

Refer This link for understanding it

Where phi(x) is a function…

And if (x is prime) , phi(x)==x-1

Read more about phi(x) HERE

2 Likes
5

basically phi(n) shows the positive integers up to a given integer n that are relatively prime to n
so when n is prime
phi(n) is always n-1

6

Here m is prime so U can modulo it with m-1…

U can also see that using Fermat’s little theorem

7

7 is also prime hence
( 2^{(10 \mod 6)} \mod 7 ) = (2^4 \mod 7 ) = ( 16 \mod 7 ) = 2
2==2

8

Euler’s theorem generalises Fermat’s theorem

9

i m calculating
Occurrences=(((n−1k−1)modm)-((Lk−1)modm)-((Rk−1)modm))modm
(element)occurrencesmodm

10

yeah and that’s where u r wrong… replace m by m-1 in
Occurrences=(((n−1k−1)modm)-((Lk−1)modm)-((Rk−1)modm))modm

11

ALSO IN C++ don’t forget to make power positive if it goes negative in following way

(a-b-c)\mod m == ( ((a\mod m) - (b\mod m) -(c\mod m))\mod m )+m)\mod m