Link to the DSERIES Problem: DSERIES Problem
Link to the DSeries editoral: DSERIES EDITORIAL
Link to the Author’s Solution: Author’s solution
I didn’t understand that why did the author used:
temp =(temp- fact[ t+1 ] + M )%M ;
and where or how did he divide the temp by t+1.
AND
what is this line used for?
temp = ( temp * powd( t + 1 , M -2 , M ) )%M ;
If anyone is having problem in understanding the code then head over to the above link…
As you must have seen in editorial, the ans is (product of (n+i) where i ranges from 1 to t+1/(t+1))-t! but
this is equal to [(product of (n+i) where i ranges from 1 to t+1)-(t+1)!]/(t+1) (multiplying t! by t+1 up and down like 2/3 +1 =(2+3)/3) this gives the explanation of first line
second line is about dividing the whole by t+1, as we have to do mod m we have to use modular division. But author has used Fermat’s little theorem details about which is given here
http://mathworld.wolfram.com/FermatsLittleTheorem.html
and proof here in this ans https://stackoverflow.com/questions/12235110/modulo-of-division-oftwo-numbers/12235283#12235283
By this we get (a/b)%m = (a*b^m-2)%m so that’s what author has done
Hope this helps!! 