CHEFPSA Video Solution

editorial
,
21

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

22

thank you got the mistake

23 
  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)

24

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

1 Like
25

tmw orz

26

@ 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
27

thanks, that fixed my tle

29

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.

31

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
32

See my reply above.

33

Oops!! Thank you!

34

Your code fails on

1
4
2 2 0 0 0 0 3 3

Your code prints 2 0s instead of just 1.

35

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.

36

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

37

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

38

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

39

@tmwilliamlin please help me out to find out what is wrong in my solution.
https://www.codechef.com/viewsolution/28887936

40

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

1 Like
41

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

42

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.