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.

To avoid timing out this uses the factorial formula for the choose function, modding out at each step so that multiplication does not become too costly. Note that building tables can take quadratic time while the formula takes linear time. To tackle the division in the formula inside the modulus, a modular inversion function based on the Euclidean algorithm is written on the first line.

## Matrix Tracing

You are viewing a single comment's thread. Return to all comments →

Just for fun, a code golf solution in Python:

To avoid timing out this uses the factorial formula for the choose function, modding out at each step so that multiplication does not become too costly. Note that building tables can take quadratic time while the formula takes linear time. To tackle the division in the formula inside the modulus, a modular inversion function based on the Euclidean algorithm is written on the first line.