Responsive image

问题 1245 --出入栈

1245: 出入栈

时间限制: 1 Sec  内存限制: 128 MB
提交: 2  解决: 2
[提交][状态][讨论版][命题人:]

题目描述

 给定一个初始为空的栈，和n个操作组成的操作序列，每个操作只可能是出栈或者入栈。
要求在操作序列的执行过程中不会出现非法的操作，即不会在空栈时执行出栈操作，同时保证当操作序列完成后，栈恰好为一个空栈。
求符合条件的操作序列种类。
例如，4个操作组成的操作序列符合条件的如下：
入栈，出栈，入栈，出栈
入栈，入栈，出栈，出栈
共2种。

输入描述

 输入包含多组测试用例，每组测试用例仅包含一个整数n(1<=n<=1000)。

输出描述

 输出仅一个整数，表示符合条件的序列总数，为了防止总数过多超出int的范围，结果对1000000007取模(mod 1000000007)。

样例输入

2
3
4
5
10

样例输出

1
0
2
0
42

提示

友情提示：如(x,y)表示共进行x次入栈和y次出栈。那么y必不大于x，要求(x,y)情况下操作序列的种类数。我们只需知道(x,y-1)和(x-1,y)时的种类数。前者在各可能序列最后加上一次出栈操作。后者在各可能序列最后加上一次入栈操作。即得出dp(x,y)=dp(x,y-1)+dp(x-1,y)时的种类数。

来源

黄庆浩 

[提交][状态]
ACM算法攻关部