loj#P2839. 「JOISC 2018 Day 3」安全门
「JOISC 2018 Day 3」安全门
题目描述
译自 JOISC 2018 Day3 T3「防犯ゲート / Security Gate」
你知道「净是一些鬼畜发明公司」(Just Odd Inventions Co., Ltd.)吗?这家公司就是发明一些鬼畜玩意的。现在我们就叫它 JOI 公司。
为了防止机密信息泄露,公司门口装有一个安全门。进出这家公司必须通过这个门,并且每次只能容纳一人通过,无法两人或多人同时通过。
一旦有人通过这个安全门,安全门就会记录一条信息,表示行人是进入公司还是离开公司。公司的一名雇员 IOI 君得到了某天安全门的一份记录。我们用一个括号序列 代表这份记录,用 表示 的第 个字符。若 (
,则第 个通过安全门的人进入了公司;若 )
,则第 个通过安全门的人离开了公司。已知在当天开始和结束时,公司内都没有人。注意:存在字符串 只包含 (
和 )
但不表示一个合法记录。如:这样的两份记录:())(
和 (()
就不是合法记录。第一条记录会导致 JOI 公司内有负数个人,第二条记录表示这天下班之后 JOI 公司还有一个人。
IOI 君检查完 后, 就被病毒修改了!经过一些调查,他猜测病毒修改 的方法如下:
- 先将「 里面连续的一段字符串」中每一个
(
修改为)
,每一个)
则修改为(
。用 表示这次修改后的字符串。注意,该操作可能并没有执行,因此有可能出现 的情况。 - 然后将 中的某些字符改为
x
。用 表示这次修改后的字符串。该操作也可能并没有执行,因此有可能出现 的情况。
IOI 君不记得 了,所以他想将 恢复到 。为了达到这个目的,他首先想知道有多少可能的 (注意,不是 )。
任务
给出字符串 ,写一个程序计算有多少可能的 字符串,模 输出。
输入格式
从标准输入中读取以下内容:
- 第一行包含一个正整数 。表示 的长度,即两次修改后的字符串长度为 。
- 第二行包含一个字符串 ,每个字母都是
(
,)
,x
中的一个。表示修改两次之后的字符串 。
输出格式
输出一行到标准输出,输出包含 的可能数量,对 取模后输出。如果没有这样的字符串,输出 。
4
x))x
3
10
xx(xx()x(x
45
5
x))x(
0
10
xxxxxxxxxx
684
数据范围与提示
对于所有数据,满足 。
本题共有 个子任务。每个子任务的分数和附加限制如下:
Subtask | 附加限制 | 分数 |
---|---|---|
, 中字符 x 的数量最多为 |
||
, 中字符 x 的数量最多为 |
||
, 中字符 x 的数量最多为 |
||
无附加限制 |