Hints: Rigged Bracket Sequence

A subsequence keeps relative order but may skip characters. For example, in $S=\texttt{()()}$, choosing positions $1$ and $4$ gives the string $\texttt{()}$ (first and last bracket), not the substring $\texttt{)()}$.

Why must any RBS subsequence contain the same number of ( and )? For a nonempty RBS, what is the first character and what is the last character of that subsequence-string?

Answer to Easy 1: Any nonempty RBS has the same count of opens and closes, and the subsequence-string must start with ( and end with ) (otherwise the Dyck walk fails immediately or at the end).

While you scan the chosen characters in index order, maintain the balance (number of opening brackets minus number of closing brackets seen so far in the subsequence). For the result to be an RBS, this balance must never be negative and must be zero after the last chosen character.

Answer to Easy 2: Process $S$ from left to right. After each prefix of $S$, keep counts of how many different subsequences (of that prefix) yield each possible current balance $b\ge 0$, having never gone negative along the way.

Let dp[b] be that count (modulo your prime). Initially only the empty subsequence exists: dp[0]=1, all other entries $0$.

When you read the next character, you may skip it (carry all old counts) or take it (update balances). How does taking ( vs taking ) change $b$?

Answer to Easy 3: For each new character $c$:

• Skip: every old state stays available.
• Take (: every old state with balance $b$ contributes to balance $b+1$.
• Take ): only states with $b\ge 1$ may take it, contributing to balance $b-1$.

Implement by copying dp to newdp for skips, then adding take-contributions (or a single backward/forward pass per character). After processing all of $S$, the number of nonempty RBS subsequences is $dp[0] - 1$ (subtract the empty subsequence).

Check on $S=\texttt{()}$: you should get $1$ nonempty RBS subsequence, namely the whole string.

Answer to Easy 4: On $S=\texttt{()()}$, enumerate by hand a few subsequences: $\texttt{()}$ can be formed in several ways (different position sets). The DP should agree with a careful manual count.

This exercise fixes the difference between “positions in the original $S$” and “the short string they spell out”—the same short string may correspond to many index sets, and the problem counts index sets, not distinct strings.

When you are comfortable with this DP, you are ready for Section 2, where the subsequence is not taken as-is: its characters are rotated before checking regularity.

Read the “shift to the right” carefully: if the chosen indices are $i_1 < i_2 < \cdots < i_k$, then simultaneously $S_{i_1}\gets S_{i_k}$, $S_{i_2}\gets S_{i_1}$, $\ldots$, $S_{i_k}\gets S_{i_{k-1}}$. For $k=1$ this is a no-op; for $k=2$ it swaps the two characters; for larger $k$ it is a single cyclic rotation of the multiset of characters on those positions.

Try $k=2$ on small RBS examples first: when does swapping two positions keep the whole string regular?

Answer to Hint 1: The multiset of brackets is unchanged, so the total number of ( and ) stays balanced. Regularity is about the prefix balances of the new string. A swap or rotation only changes $O(k)$ positions, but those changes can break the “never drop below zero” property unless the chosen positions interact with the matching structure in a very constrained way.

So the counting problem is not “all nonempty subsequences”, but a tiny structured family once you characterize validity.

Answer to Hint 2: Work out the sample $S=\texttt{()()}$ by hand (the statement lists all $8$ valid subsequences). Also try $S=\texttt{()}$ ($2$ valid). What do the valid subsequences have in common in terms of which positions appear and how many ( / ) you select?

You should start to suspect that validity is impossible for many subsets unless a strong non-crossing / nesting condition holds relative to the usual parenthesis matching tree.

Answer to Hint 3: A powerful way forward is to prove a classification: every valid nonempty subsequence falls into one of two disjoint combinatorial types (one “easy” family counted by a closed form, one “residual” family counted while scanning the string with a tiny DP). The official solution’s program is exactly this split: an initial sum in closed form, then a linear pass with two scalars dp[0], dp[1].

Your job is to discover what those two families mean—not to guess the DP from nowhere.

Answer to Hint 4: Focus on the easy family first. Imagine you are going to rotate a chosen subsequence. Intuitively, some constructions only “move brackets around” inside a region that cannot break the global prefix constraints, and every strictly earlier position may participate independently as “optional noise”.

That independence often shows up as a factor of $2$ per position. Along a fixed scan order, when you pass a ( at index $i$ (0-based), the number of unconstrained binary choices among earlier positions is $2^{i}$.

Answer to Hint 5: One clean closed-form piece of the answer is $$\sum_{\substack{0\le i<n\ S_i=\texttt{(}}} 2^{i} \pmod{998,244,353}.$$ In code: start with res = 1, walk the string left to right, double res after every character, and whenever you see (, add the current res into the answer before the doubling for that step (equivalently: add $2^{i}$ at index $i$).

This counts the entire first family; the remaining valid subsequences are handled by the second phase.

Answer to Hint 6: Sanity-check the sum on $S=\texttt{()()}$: openings at indices $0$ and $2$ contribute $2^0+2^2=1+4=5$. The full answer is $8$, so the second phase must contribute exactly $3$. Keep that arithmetic in mind while you design the residual counter.

Also note: the first family’s count depends only on the positions of (—not on matching partners—because it is “local optional choices before each opening”.

Answer to Hint 7: For the residual part, use the standard prefix balance $$\mathrm{pre}[i] = \text{(opens in } S_0\ldots S_{i-1}\text{)} - \text{(closes in } S_0\ldots S_{i-1}\text{)}.$$ Before reading $S_i$, you are at depth $\mathrm{pre}[i]$ in the usual Dyck walk.

The DP in the model solution zeros out one component whenever $\mathrm{pre}[i]\le 1$. Interpretation sketch: configurations counted in that component would rotate brackets across a region that includes the outermost wrapping or the first return to depth $0$, which is exactly where global regularity is easiest to break; only the shallower state should survive past that barrier.

Answer to Hint 8: Maintain two nonnegative modular counts dp[0] and dp[1] while scanning $i=0..n-1$. Think of them as counting partial valid constructions of the second type that end “in mode $0$ / mode $1$” at the current position—modes correspond to how deep the construction is tied into the bracket tree (the exact bijection is lengthy, but the recurrence is short).

The crucial reset: if $\mathrm{pre}[i]\le 1$, set dp[0] = 0 before applying the transition at $i$.

Answer to Hint 9: The transitions are asymmetric because ( and ) play different roles in a rotation-safe insertion:

• If $S_i=\texttt{(}$, update only dp[0]: dp[0] += dp[0] + dp[1] + 1.
• If $S_i=\texttt{)}$, first add 1 + dp[0] + dp[1] to the global answer, then update only dp[1]: dp[1] += dp[0] + dp[1] + 1.

The trailing + 1 is the subsequence that uses only the current index (consistent with singletons being valid in many positions, as in the samples).

Answer to Hint 10: Process left to right. Initialize dp[0]=dp[1]=0, ans equal to the closed-form sum from Hint 6. For each $i$:

1. If $\mathrm{pre}[i]\le 1$, set dp[0]=0.
2. Apply the ( or ) branch exactly as above (for ), add to ans before growing dp[1]).

All arithmetic is modulo $998,244,353$. This is $O(n)$ per test case; summed $n$ is bounded, so it fits the limits.