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)
	//multiply by inverse of k!
	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 6 for eg.

1 Like

thanks, that fixed my tle

Your code fails on this case:
-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

See my reply above.

Oops!! Thank you!

Your code fails on

2 2 0 0 0 0 3 3

Your code prints 2 0s instead of just 1.

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

@tmwilliamlin please help me out to find out what is wrong in my solution.

I think you need to change endl to “\n”.

1 Like

I tried to run solution after replacing endl to “\n” but it still didn’t work.

I see in your solution that you did not do some necessary checks as described in my video. For example, you need to check that s is divisible by n+1.