bzoj#P3300. [USACO2011 Feb] Best Parenthesis
[USACO2011 Feb] Best Parenthesis
题目描述
计算平衡字符串的分数,平衡字符串是指由相同数量的 和 组成,且以 开头,以 结尾的字符串。
计算规则:
- 字符串 的得分是 ;
- 如果平衡字符串 的得分是 ,那么字符串 的得分是 ;
- 如果 的得分分别是 和 ,那么平衡字符串 得分为 。
例如:$s(\texttt{(())()})=s(\texttt{(())})+s(\texttt{()})=2\times s(\texttt{()})+1=2\times 1+1=3$。
输入格式
第 行一个整数 ,表示平衡字符串长度。
第 行:第 行一个整数 或 , 代表字符 , 代表 。
输出格式
字符串的得分,结果对 取模。
6
0
0
1
1
0
1
3
样例解释
样例对应字符串 。
数据范围
对于 的数据,。