P7044 “MCOI-03” Brackets

Daily life in the MCOI q group …… > A little bookworm: If I can’t mine diamonds, I’m going to cry (lol). > WAPER420: But we clearly mine diamonds every time (confused). > A little bookworm: (a friendly smile). > 7KByte: Why do you all like adding brackets so much (staring blankly). > A little bookworm: (laugh). > WAPER420: (laugh). > Kagamine Rin: (laugh). > 7KByte: (laugh). --- In this problem, a **valid bracket sequence** is defined as follows: 1. The empty string is a valid bracket sequence. 2. If ```A``` is a valid bracket sequence, then ```(A)``` is a valid bracket sequence. 3. If ```A```, ```B``` are valid bracket sequences, then ```AB``` is a valid bracket sequence. In this problem, a **substring** is defined as follows: A substring of a string $S$ is a string formed by any consecutive characters in $S$. A substring of $S$ can be represented by a starting position $l$ and an ending position $r$, denoted as $S(l,r)$ ($1 \leq l \leq r \leq |S|$, where $|S|$ denotes the length of ```S```).

Define the level $0$ deviation value of a bracket string as the minimum number of operations needed to modify this bracket string into a **valid bracket sequence**. In one operation, you can **insert** a bracket at some position or **delete** a bracket at some position. For $i\ (i>0)$, define the level $i$ deviation value of the string as the sum of the level $i-1$ deviation values over **all substrings** of this string. Now you need to compute the level $K$ deviation value of a bracket string $S$ of length $N$. The answer may be very large; output the result modulo $998244353$.

The first line contains two integers $N, K$. The second line contains a string representing the bracket sequence $S$.

Output one integer, the answer modulo $998244353$.

#### Sample Explanation For sample $1$, the level $0$ costs of all substrings of $S$ are: - $\texttt{(}$, cost is $1$. - $\texttt{(}$, cost is $1$. - $\texttt{)}$, cost is $1$. - $\texttt{((}$, cost is $2$. - $\texttt{()}$, cost is $0$. - $\texttt{(()}$, cost is $1$. The total is $1+1+1+2+0+1=6$. #### Constraints **This problem uses bundled testdata.** | Subtask ID | $N\le$ | $K\le$ | Score | | :----------: | :----------: | :----------: | :----------: | | $1$ | $5$ | $5$ | $3$ | | $2$ | $5\times 10^3$ | $1$ | $10$ | | $3$ | $10^6$ | $1$ | $12$ | | $4$ | $10^2$ | $10^2$ | $10$ | | $5$ | $5\times10^3$ | $5\times 10^3$ | $20$ | | $6$ | $10^6$ | $10^6$ | $45$ | For $100\%$ of the testdata, $1 \le N, K \le 10^6$. --- Original idea: WAPER420 Translated by ChatGPT 5