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

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:

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**

a^{b-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

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

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

#### U can also see that using Fermat’s little theorem

7 is also prime hence

( 2^{(10 \mod 6)} \mod 7 ) = (2^4 \mod 7 ) = ( 16 \mod 7 ) = 2

2==2

Euler’s theorem generalises Fermat’s theorem

i m calculating

Occurrences=(((n−1k−1)modm)-((Lk−1)modm)-((Rk−1)modm))modm

(element)occurrencesmodm

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

#### 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