← 返回题目列表

AtCoder · pakencamp_2021_day2_k

K. 支架插入

中文机器翻译题面 查看原题

配点 : 500 点

問題文

乌龟喜欢玩绳子。今天是一个空字符串 准备 s 并执行以下操作。 我做了 N 次。

  • s 作为字符串 分成 l,r 。 替换为 s 输出为 l\ + () +\ r 。

N 操作后 s 的值为 T ,这样我们就可以计算出可能的操作方法的数量。 除以 998244353 求余数。

然而,一些正整数 k\ (1 \le k \le N) 存在 k 在第次操作中 (l,r) 对不同,只有这样 2 我们认为这两种操作方法是不同的。

还有,乌龟君不会说谎,所以一定要 s=T 操作方法是 1 似乎存在一个。 仅给出 T 。 长度由

制約

  • 1 \le N \le 10^5
  • T 满足 (, ) 组成 2N 字符串
  • 通过执行适当的操作, s=T 可以

入力

输入将以以下形式从标准输入给出。

N
T

出力

打印答案。


入力例 1

3
(())()

出力例 1

3

可以进行以下操作。 令

1 回目、 l,r 为空字符串。 s= () 变为。

2 回目、 l= () ,r 为空字符串。 s= ()() 变为。

3 回目、 l= ( ,r= )() 。 s= (())() 变为。


入力例 2

1
()

出力例 2

1

入力例 3

7
(()(()(())()))

出力例 3

72

原案: 海龟0123__ 长度由小于