bzoj#P3300. [USACO2011 Feb] Best Parenthesis

[USACO2011 Feb] Best Parenthesis

题目描述

计算平衡字符串的分数,平衡字符串是指由相同数量的 (\texttt{(})\texttt{)} 组成,且以 (\texttt{(} 开头,以 )\texttt{)} 结尾的字符串。

计算规则:

  • 字符串 ()\texttt{()} 的得分是 11;
  • 如果平衡字符串 AA 的得分是 s(A)s(A),那么字符串 (A)\texttt{(}A\texttt{)} 的得分是 2×s(A)2\times s(A)
  • 如果 A,BA,B 的得分分别是 s(A)s(A)s(B)s(B),那么平衡字符串 ABAB 得分为 s(A)+s(B)s(A)+s(B)

例如:$s(\texttt{(())()})=s(\texttt{(())})+s(\texttt{()})=2\times s(\texttt{()})+1=2\times 1+1=3$。

输入格式

11 行一个整数 NN,表示平衡字符串长度。

2N+12\sim N+1 行:第 i+1i+1 行一个整数 001100 代表字符 (\texttt{(}11 代表 )\texttt{)}

输出格式

字符串的得分,结果对 1234567891012345678910 取模。

6
0
0
1
1
0
1
3

样例解释

样例对应字符串 (())()\texttt{(())()}

数据范围

对于 100%100\% 的数据,2N1052\leq N\leq 10^5