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!!
@abhi_1595 @aswinashok44 Please help me out!!!
If anyone is having problem in understanding the code then head over to the above link…