P16958 [SCCPC 2026] Bracket Sequence

For strings $S$ and $T$, define that $S$ is lexicographically smaller than $T$ if and only if one of the following holds: - $S$ is the empty string (length $0$), and $T$ is non-empty; - $S$ and $T$ are non-empty, and $S[0]$ is lexicographically smaller than $T[0]$, where $S[0]$ and $T[0]$ denote the first character of $S$ and $T$; - $S$ and $T$ are non-empty, and $S[0]=T[0]$, and $S[1,\cdots]$ is lexicographically smaller than $T[1,\cdots]$, where $S[1,\cdots]$ and $T[1,\cdots]$ denote the strings obtained by deleting the first character from $S$ and $T$. For a bracket string $S$ consisting of $\texttt{\{`(',`)'\}}$, call it matchable if and only if one of the following holds: - $S$ is the empty string (length $0$); - $S = (A)$, where $A$ is a matchable bracket string; - $S = AB$, where both $A$ and $B$ are non-empty matchable bracket strings. Now a matchable bracket string $T$ is given. Find how many bracket strings $S$ satisfy all of the following four conditions: - $S$ is not the empty string (length $> 0$); - $S$ is matchable; - $S=T$, or $S$ is lexicographically smaller than $T$; - The length of $S$ is less than or equal to the length of $T$. Note that the character $\texttt{`('}$ is lexicographically smaller than $\texttt{`)'}$. This problem uses multiple test cases. The answer may be very large, so output the result modulo $998244353$.

The first line of each test file contains a positive integer $t$ ($1 \le t \le 5\times 10^5$), the number of test cases. Then follow $t$ test cases. For each test case, the first line contains an even integer $n$ ($2\le n\le 10^6$), the length of the string $T$. The second line contains a bracket string of length $n$ over $\texttt{\{`(',`)'\}}$. It is guaranteed that $T$ is matchable. It is guaranteed that the sum of lengths of all bracket strings in a single test file does not exceed $10^6$.

Output $t$ lines. The $i$-th line should contain the answer for the $i$-th test case modulo $998244353$.

For the fourth test case, there are the following six valid strings $S$: - $\texttt{()}$ - $\texttt{(())}$ - $\texttt{()(())}$ - $\texttt{(())()}$ - $\texttt{((()))}$ - $\texttt{(()())}$ Translated by ChatGPT 5