Skip to content

11604: 【原1604】Interesting Stack

题目

题目描述

author: xzj 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1604

Description

将1-N按顺序入栈,且可以在任意“栈非空的时刻”弹出栈顶元素,以此种方法得到的出栈序列(弹出的栈顶元素依次组成的序列)即为合法的出栈序列。两个出栈序列是不同的,当且仅当两个序列中存在至少一位不相同的元素。

定义一个出栈序列的代价为cost,则cost为“每次有元素入栈时,将全部栈内元素的标号求和”的和。例如,当n=4时,某个操作序列为“1入 2入 2出 3入 3出 1出 4入 4出”,则有“1入时cost+=1,2入时cost+=(1+2),3入时cost+=(1+3),4入时cost+=4”。

求全部不同的合法出栈序列的cost的和,答案对1000000007(10^9+7)取模。

Input Format

一个整数 N。

Output Format

一个数 ANS % 1000000007。

Sample Input

2

Sample Output

7

Hint

共有两种方案:

1入1出2入2出(答案为1+2)

1入2入2出1出(答案为1+3)

Limits

  • 对于30%的数据,n不超过12;
  • 对于60%的数据,n不超过22;
  • 对于100%的数据,n不超过100.
  • (对于所有的数据,n各不相同。保证有小数据,你懂的)

Another Hint

如果AK了,可以考虑一下n=1000时的做法。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!