← 返回题目列表

AtCoder · agc071_b

B. 最大括号子序列

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

分数: 900 点

问题陈述

给你整数 N, K,以及正确的括号序列 S 长度 K 组成 ( 和 ).

求模数 998244353,长度-N 字符串 T 组成 ( 和 ) 满足以下所有条件:

  • 存在一个(不一定是连续的)子序列 T 这是长度正确的括号序列 K.
  • 在所有(不一定是连续的)子序列中 T 是长度正确的括号序列 K,字典顺序最大的一个是 S.

这里,关于由以下组成的字符串的字典顺序 ( 和 ),我们考虑 ( 小于 ).

有关正确括号顺序的注意事项 正确的括号序列是可以通过重复删除以下子串将其转换为空字符串的字符串: () 零次或多次。
字典顺序注释

一个字符串 S = S_1S_2\ldots S_{|S|} 据说是 按字典顺序较小 比字符串 T = T_1T_2\ldots T_{|T|} 如果以下任一条件成立。

  1. |S| < |T| 和 S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}.
  2. 存在一个整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace 这样:
    • S_1S_2\ldots S_{i-1} = T_1T_2\ldots T_{i-1},
    • S_i 是一个小于 T_i.

约束

  • K \leq N \leq 10^7
  • 2 \leq K \leq 5 \times 10^5
  • N 和 K 是整数。
  • S 是长度正确的括号序列 K.

输入

输入由标准输入按以下格式给出:

N K
S

输出

打印答案。


示例输入 1

7 4
(())

示例输出 1

20

例如,如果 T=((()))),唯一(不一定是连续的)子序列 T 这是长度正确的括号序列 4 is (()),等于 S,因此满足条件。

If T=((())(),有两个(不一定是连续的)子序列 T 是长度正确的括号序列 4: ()() 和 (())。字典序上最大的一个是 ()(),所以不满足条件。


示例输入 2

20 4
()()

示例输出 2

1047225

示例输入 3

71 10
()(()())()

示例输出 3

190654464

示例输入 4

10000000 28
(()()(()))(()((()))())()(())

示例输出 4

769035381