 # CHEFPSA Video Solution

Hi, thanks for amazing video.
I didn’t understand the inverse modulo part. Can someone please elaborate more around that.

thank you got the mistake

``````  for(int i=1; i<=k; ++i)
``````
``````		b=b*i%M;
//multiply by inverse of k!
//(k!)^(M-2)
ans=ans*powM(b, M-2)%M;
``````

Can someone explain the last step… I mean, how did we get (k!)^(M-2)

I had the exact same problem, TLE on one test case, logic was the same as editorial

1 Like

tmw orz

@ tmwilliamlin suppose occurence of suma is more than 2 let say X.then there will extra factor to multiply ->“Ways to chose two suma out of X i.e C(X,2)”
In video count of 10 is 2.what if it is more than 2.like 6 for eg.

1 Like

thanks, that fixed my tle

Your code fails on this case:
1
2
-1 -1 -1 0

You shouldn’t use unsigned long longs since the sums can be negative.

From Fermat’s little theorem, x^(P-1) = 1 mod P, so x^(P-2) = 1/x mod P. That’s why I multiply by (k!)^(P-2).

1 Like

Oops!! Thank you!

1
4
2 2 0 0 0 0 3 3

If there were 6 occurrences of 10, we don’t multiply by C(6, 2) because the 2 occurrences of 10 which we remove does not affect the original array a.

Yeaaaahh… Bro that helped but… Can u explain why it happened.

Yeah I closed one brace early. I got it now. Thanks!!!

endl forces cout to flush while “\n” does not