SPOJ - Brackets Parade

Recently solved problem #4202 - BRPAR.

If you want to solve the problem yourself - stop reading now.

Solution: Catalan numbers & number of permutations.

The number of ways to order n pairs of matching brackets is

i.e. The Catalan numbers.

The number of ways to order n things of m different types, where there are a1, a2,..., am things of each type is

i.e. The number of permutations.

When multiplying, we can divide out n! and have:
Numerator = (2n)!
Divisor = (n+1)!a1!a2!...am!

We can calculate both quantities using modular multiplication, calculate the modular inverse of the divisor and then the modular product is the required answer.

This modular inversion uses the fact that and applies repeated squaring to calculate the exponentiation. We could have used extended Euclid instead.

Maybe one could have solved it by following the logical steps the problem outlined. Though I doubt it'll pass the time limit required. I, however, find this solution more fun.

My SPOJ account