#P2981. [Poi2002]括号

    ID: 2102 传统题 1000ms 512MiB 尝试: 19 已通过: 11 难度: 8 上传者: 标签>CF2500省选/NOI-线性 DP计数 DP前缀和优化 DP滚动数组双射计数奇偶性分析

[Poi2002]括号

题目描述

减法不满足结合率,例如 (5−2)−1=2(5-2)-1=2,但 5−(2−1)=45-(2-1)=4,因此 (5−2)−1≠5−(2−1)(5-2)-1 \neq 5-(2-1)。这意味着表达式 5−2−15-2-1 依赖减法操作的顺序。如果没有括号,假定表达式计算从左到右,即5−2−15-2-1 等于 (5−2)−1(5-2)-1。我们给出表达式的形式如下:

x1+/−x2+/−⋯+/−xnx_{1} +/- x_{2} +/- \cdots +/- x_{n}

+/−+/- 表示 ++ (加) −- (减),x1,x2,...,xnx_{1},x_{2},...,x_{n} 表示计算变量。对下面的表达式 x1−x2−⋯−xnx_{1}-x_{2}- \cdots -x_{n} 我们想插入 n−1n-1 对括号得到和表达式相同的结果。例如,我们想得到和下面表达式相等值的表达式 x1−x2−x3+x4+x5−x6+x7x_{1}-x_{2}-x_{3}+x_{4}+x_{5}-x_{6}+x_{7} 可以对下面的表达式插入括号 x1−x2−x3−x4−x5−x6−x7x_{1}-x_{2}-x_{3}-x_{4}-x_{5}-x_{6}-x_{7} 得到 $(((x_{1}-x_{2})-((x_{3}-x_{4})-x_{5}))-(x_{6}-x_{7}))$。

注意: 我们只对完整而正确的表达式有兴趣,一个完整正确的表达式必须符合

  1. 它可能是单个变量,
  2. 可能形如 (w1−w2)(w_{1}-w_{2}),而且 w1w_{1} 和 w2w_{2} 都是完整而正确的表达式。

通常来说,我们对如下空括号形式不感兴趣:(),(xi),((...))(), (x_{i}), ((...))。而表达式 x1−(x2−x3)x_{1}-(x_{2}-x_{3}) 不是完整的,因为它缺少最外层的括号。

输入格式

第一行有一个整数 nn,表示表达式变量的个数。在下面的 n−1n-1 行有一个字符 ++ 或 −-。第 ii 行出现的字符给出了xi−1x_{i-1} 和 xix_{i} 之间的操作。

输出格式

对表达式 x1−x2−...−xnx_{1}-x_{2}-...-x_{n} 添加 n−1n-1 对括号,使得它与给出的表达式等价,表示插入空格的不同方案数,答案不超过 1×1091\times 10^9。

样例输入

7
-
-
+
+
-
+

样例输出

3

数据规模与约定

对于 100%100\%的数据,2≤n≤1×1062\leq n\leq 1\times 10^6。