VAIMIN - Editorial

general
, , , , ,
21

Earlier query answer -

In modular maths -

This relation is working because.

(inv[k]*fac[k])\%MOD=1;

\implies (inv[k+1]*fac[k+1])\%MOD=1;

multiply both sides by inv[k]\%MOD;

\implies (inv[k+1]*fac[k+1]*inv[k])\%MOD=inv[k]\%MOD;

\implies (inv[k+1]*(k+1)*fac[k]*inv[k])\%MOD=inv[k]\%MOD;

from (1)

\implies (inv[k+1]*(k+1)*1)\%MOD=inv[k]\%MOD

3 Likes
22

Thank You very much Sir! I got it.

1 Like
23

Abra-Kadabra- and we’re done. Have a check for your comment @aryanc403 and tell if any correction is needed.

1 Like
24

Your code has complexity of pqM. (p*q for the dp and M for find operation in each recursive call)
Constrains for third task were: p,q < 2000 and M < 3000
So it would even exceed 10^9, hence the TLE.

Also, your code was missing the following condition check:
if(good > p or bad > q) return 0;
Hence, your previous submission were getting RE(SIGSEGV). Since it may happen good ~ p + q = 4000 → that would exceed your array limits.

I incorporated the above mentioned changes in your code & got this code pass 1st subtask.

Hope that helps. :slight_smile:

2 Likes
25

Thanks mate :slight_smile:

26

I bet he will grin like a cat on seeing this :stuck_out_tongue: xD

27

Thanks alot @abhiy13 :).

XD @vijju123

1 Like
28

XD @vijju123

29

XD @both of you :stuck_out_tongue:

30

_ /|\ _ @vijju :stuck_out_tongue:

1 Like
31

Yes, the approach is based upon André’s reflection method.
I think almost everything is covered in this editorial - so you can safely skip reading it from there.

32

Yeah! thanks for pointing out the typo. I have updated the editorial :slight_smile: