Didn't understand the 2 lines of the code in DSERIES author's solution

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.


what is this line used for?
temp = ( temp * powd( t + 1 , M -2 , M ) )%M ;

@abhi_1595 @aswinashok44 Please help me out!!!

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

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!! :slight_smile: