We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
This is same as number of ways to reach the bottom-right of matrix starting from the top-left corner. Since the constraints are high so we use a bit of maths here.
The number of ways for a m n matrix can be calculated using formula :
Matrix Tracing
You are viewing a single comment's thread. Return to all comments →
This is same as number of ways to reach the bottom-right of matrix starting from the top-left corner. Since the constraints are high so we use a bit of maths here.
The number of ways for a m n matrix can be calculated using formula :
number_of_ways = (m + n - 2) ! / ((m - 1) ! * (n - 1) !)
Since denominator will be really large we find the multiplicative modulo inverse.
Multiplicative inverse of a number x w.r.t modulo m is given by :
multiplicative_inverse = pow(x, m - 2)
NOTE : For pow do the fast exponentiation method.
The code is as below :