B - Maximum Bracket Subsequence Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 900 点

問題文

整数 N,K および (, ) からなる長さ K の正しい括弧列 S が与えられます。

(, ) からなる長さ N の文字列 T のうち、以下の条件をすべて満たすものの数を 998244353 で割った余りを求めてください。

  • T の部分列であって、長さ K の正しい括弧列であるものが存在する
  • T の部分列であって、長さ K の正しい括弧列であるもののうち、辞書順で最大のものは S である

なお、 (, ) からなる文字列の辞書順について、 ( は ) より小さい文字であるものとします。

正しい括弧列とは 正しい括弧列とは、 () である部分文字列を削除することを 0 回以上繰り返して空文字列にできる文字列を指します。
部分列とは 文字列 S の部分列とは、 S の文字を 0 文字以上選んで削除し、残った文字を元の順序を保って結合することで得られる文字列のことを指します。
辞書順とは？

文字列 S = S_1S_2\ldots S_{|S|} が文字列 T = T_1T_2\ldots T_{|T|} より辞書順で小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。 ここで、|S|, |T| はそれぞれ S, T の長さを表します。

  1. |S| \lt |T| かつ S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}。
  2. ある整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace が存在して、下記の 2 つがともに成り立つ。
    • 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 の正しい括弧列であるものは (()) のみであり、これは S に等しいため条件を満たします。

T=((())() の場合、 T の部分列であって、長さ 4 の正しい括弧列であるものは ()() と (()) の 2 種類存在し、辞書順で最大のものは ()() であるため、条件を満たしません。

入力例 2

20 4
()()

出力例 2

1047225

入力例 3

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

出力例 3

190654464

入力例 4

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

出力例 4

769035381

Score : 900 points

Problem Statement

You are given integers N, K, and a correct bracket sequence S of length K consisting of ( and ).

Find the number, modulo 998244353, of length-N strings T consisting of ( and ) that satisfy all of the following conditions:

  • There exists a (not necessarily contiguous) subsequence of T that is a correct bracket sequence of length K.
  • Among all (not necessarily contiguous) subsequences of T that are correct bracket sequences of length K, the lexicographically largest one is S.

Here, concerning the lexicographical order of strings consisting of ( and ), we consider ( smaller than ).

Notes on correct bracket sequences A correct bracket sequence is a string that can be transformed into the empty string by repeatedly deleting a substring that is () zero or more times.
Notes on lexicographical order

A string S = S_1S_2\ldots S_{|S|} is said to be lexicographically smaller than a string T = T_1T_2\ldots T_{|T|} if either of the following holds.

  1. |S| < |T| and S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}.
  2. There exists an integer 1 \leq i \leq \min\lbrace |S|, |T| \rbrace such that:
    • S_1S_2\ldots S_{i-1} = T_1T_2\ldots T_{i-1},
    • S_i is a character smaller than T_i.

Constraints

  • K \leq N \leq 10^7
  • 2 \leq K \leq 5 \times 10^5
  • N and K are integers.
  • S is a correct bracket sequence of length K.

Input

The input is given from Standard Input in the following format:

N K
S

Output

Print the answer.

Sample Input 1

7 4
(())

Sample Output 1

20

For example, if T=((()))), the only (not necessarily contiguous) subsequence of T that is a correct bracket sequence of length 4 is (()), which equals S, so it satisfies the conditions.

If T=((())(), there are two (not necessarily contiguous) subsequences of T that are correct bracket sequences of length 4: ()() and (()). The lexicographically largest one is ()(), so it does not satisfy the conditions.

Sample Input 2

20 4
()()

Sample Output 2

1047225

Sample Input 3

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

Sample Output 3

190654464

Sample Input 4

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

Sample Output 4

769035381