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 ;

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 algorithm - Modulo of Division of Two Numbers - Stack Overflow

By this we get (a/b)%m = (a*b^m-2)%m so that’s what author has done

Hope this helps!! :slight_smile:

@abhi_1595 @aswinashok44 Please help me out!!!

If anyone is having problem in understanding the code then head over to the above link…