Rigged Bracket Sequence

Research note: I checked the official Codeforces editorial page, which currently has the 2201C section but no loaded tutorial body, plus CF Step's model-code recurrence and hints, and an independent kmjp DP writeup: official page, CF Step hints, CF Step code, kmjp writeup. The proof below is from the statement; sources were only used to sanity-check the intended linear DP.

Let the original prefix balance be

$B(x)=\sum_{i=0}^{x} [S_i=\texttt{(}]-[S_i=\texttt{)}].$

The original string is regular, so every $B(x)\ge 0$ and the final balance is $0$.

Choose positions

$p_1<p_2<\cdots<p_k,$

and let $v_j=1$ if $S_{p_j}=\texttt{(}$, otherwise $v_j=-1$. After the cyclic right shift, position $p_j$ receives the old value from $p_{j-1}$, with $p_1$ receiving from $p_k$.

Now look at the balance difference after a prefix that contains exactly the first $m$ chosen positions. It is

$\Delta_m=\sum_{j=1}^{m}(v_{j-1}-v_j),\quad v_0=v_k.$

This telescopes:

$\Delta_m=v_k-v_m.$

That is the whole problem. No need to simulate the subset circus.

There are only three possible differences: $-2,0,+2$. A negative difference happens only when:

• the rightmost chosen bracket is ), so $v_k=-1$;
• the latest chosen bracket inside the current prefix is (, so $v_m=1$.

So split by the rightmost chosen position.

Case 1: the rightmost chosen bracket is (

Then $v_k=1$, so $v_k-v_m$ is either $0$ or $2$. Prefix balances never decrease. Therefore every such non-empty subsequence is valid.

If this rightmost opening bracket is at $0$-based index $i$, every earlier position can be chosen or skipped independently, and position $i$ must be chosen. That gives $2^i$ subsequences.

So this part contributes

$\sum_{S_i=\texttt{(}} 2^i.$

This also counts singleton ( subsequences, correctly, because shifting one selected character is a no-op.

Case 2: the rightmost chosen bracket is )

Now dangerous intervals exist. Suppose some chosen ( is followed by the next chosen position later. From that ( until just before the next chosen position, the latest chosen bracket is ( while the final selected bracket is ), so the shifted balance is

$B(x)-2.$

For validity we need

$B(x)\ge 2$

throughout that whole gap.

This gives a clean left-to-right DP.

Let $\text{pre}[i]$ be the balance before reading $S_i$. Maintain:

• $dp_0$: number of non-empty partial chosen subsequences among already processed positions whose latest chosen bracket is (, and whose open dangerous gap has stayed at balance at least $2$ so far;
• $dp_1$: same, but latest chosen bracket is ). There is no dangerous open gap in this state.

Before processing position $i$, if $\text{pre}[i]\le 1$, every partial subsequence ending in ( is dead: if we kept skipping until here, the interval after that chosen ( reached balance $0$ or $1$, and later subtracting $2$ would break regularity. So:

$\text{if }\text{pre}[i]\le 1,\quad dp_0=0.$

Now process $S_i$.

If $S_i=\texttt{(}$, taking it can extend any alive partial subsequence, or start a new one. The latest chosen bracket becomes (:

$dp_0 \mathrel{+}= 1+dp_0+dp_1.$

Skipping it is already represented by keeping the old $dp_0,dp_1$.

If $S_i=\texttt{)}$, taking it can also extend any alive partial subsequence, or start a singleton ). Since this ) may be the rightmost selected bracket, all these choices are complete valid answers right now:

$ans \mathrel{+}=1+dp_0+dp_1.$

They can also be partial subsequences for a later rightmost ), now ending in ):

$dp_1 \mathrel{+}=1+dp_0+dp_1.$

The singleton ) is valid because a length-$1$ shift changes nothing.

Correctness proof

For any chosen subsequence, the prefix-balance change after the first $m$ chosen positions is exactly $v_k-v_m$ by telescoping. Therefore if the rightmost chosen bracket is (, no prefix balance decreases, so all such subsequences are valid and the closed form counts them exactly by their rightmost position.

If the rightmost chosen bracket is ), the only possible negative change is $-2$, and it happens exactly while the most recent chosen bracket is (. Thus the necessary and sufficient condition is: every gap after a chosen ( and before the next chosen position must have original balance at least $2$.

The DP stores exactly the partial subsequences satisfying all already-closed gaps, plus possibly one currently open gap when the latest chosen bracket is (. The reset $dp_0=0$ when $\text{pre}[i]\le 1$ removes exactly the partial subsequences whose open gap has just become impossible. The transitions append the current position or skip it, preserving the latest chosen bracket state. When a ) is taken, every alive partial subsequence plus the singleton case forms a valid full subsequence with rightmost bracket ), so adding $1+dp_0+dp_1$ counts each such subsequence exactly once, at its rightmost position.

The two cases are disjoint because the rightmost chosen bracket is either ( or ). Together they cover every non-empty subsequence.

Edge cases

• $k=1$ is handled: singleton ( is counted in the closed form, singleton ) in the DP.
• The reset uses the balance before the current character. Using the balance after the current character is an easy off-by-one way to get wrecked.
• The input is already a regular bracket sequence, so final balance after any rotation is still $0$; only prefix negativity matters.

Complexity

Each character is processed once, with $O(1)$ state.

$O(n)$ per test case, $O(\sum n)$ total time, and $O(1)$ extra memory.