Description
栈是常用的一种数据结构,有n个元素在栈顶端一侧等待进栈,栈顶端另一侧是出栈序列。你已经知道栈的操作有两种: push 和 pop ,前者是将一个元素进栈,后者是将栈顶元素弹出。现在要使用这两种操作,由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n,计算并输出由操作数序列1 ,2 ,... ,n,经过一系列操作可能得到的输出序列总数 mod 7 的值。
Input
一个整数n。
Output
一个数,即可能输出序列的总数目。
Sample Input
3
Sample Onput
5
Data Range
n<=1000
Solution
这是一个经典的组合数学的模型，可以从两个角度来思考。
第一：这是卡特兰数，直接通过卡特兰数的递推公式推导而来。
第二：从格路数的角度思考，这就是从坐标原点不穿越y=x这条直线到(n,n)点的最短路径方案数
即C(2n,n)-C(2n,n-1)。
推导过程：不穿越y=x等价为不碰触y=x-1，即为所有不合法的方案为(0,0)以y=x-1的对称点(1,-1)到(n,n)的方案（一一对应原理）
再用合法方案减去不合法方案即为答案（没看懂的可以参考 《组合数学》卢开澄 清华大学出版社 第一章的解释）
最后递推组合数相减要注意避免出现负数，可以(C(2n,n)-C(2n,n-1)+14) mod 7