【算法】Catalan数
【题解】
学了卡特兰数就会啦>_<!
因为奇偶各自递增，所以确定了奇偶各自的数字后排列唯一。
那么就是给2n个数分奇偶了，是不是有点像入栈出栈序呢。
将做偶数标为-1，做奇数标为+1，显然当偶数多于奇数时不合法，因为它压不住后面的奇数。
然后其实这种题目，打表就可知啦……QAQ
然后问题就是求1/(n+1)*C(2n,n)%p了，p不一定是素数。
参考bzoj礼物的解法。
看到网上清一色的素数筛+分解质因数解法，不解了好久，感觉写了假的礼物……
后来觉得礼物的做法才比较快吧，当然也比较复杂。
原文：http://www.cnblogs.com/onioncyc/p/7215075.html