Let us define the special index $$$s_p$$$ as the index ($$$0$$$-indexed) of the leftmost minimum value of the prefix sum. For example, $$$\texttt{)())(()}$$$ gives us $$$p=[-1,0,-1,-2,-1,0,-1]$$$, $$$s_p=3$$$. By definition the $$$s_p$$$ is the unique index such that $$$p_i > p_{s_p}$$$ if $$$i<s_p$$$ and $$$p_{s_p} \leq p_i$$$ if $$$s_p<i$$$.

Claim: when we perform a right rotation on the string, the special index will be updated like $$$s_p \gets (s_p+1) \% (2n+1)$$$. Loosely, the special index shifts along with the string.

Let us consider that currently our prefix sum is $$$p=[p_1,p_2,\ldots,p_k]$$$. After a single right rotation, it will become $$$p'=[0+(p_k-p_{k-1}),p_1+(p_k-p_{k-1}),p_2+(p_k-p_{k-1}),\ldots,p_{k-1}+(p_k-p_{k-1})]$$$. That is, we append $$$0$$$ to the beginning of $$$p$$$, delete the last element of $$$p$$$, then add $$$p_k-p_{k-1}$$$ to all elements.

We want to show that $$$s_{p'}= (s_p+1) \% (2n+1)$$$. We will split into two cases.

Note that $$$p_k$$$ is $$$-1$$$, since there are $$$n$$$ $$$\texttt{(}$$$s and $$$n+1$$$ $$$\texttt{)}$$$s. Furthermore, we can more easily consider $$$p'=[0,p_1,p_2,\ldots,p_{k-1}]$$$ since adding a constant all elements of $$$p'$$$ does not change $$$s_{p'}$$$.

Case 1

Suppose that $$$s_p < 2n$$$, then $$$s_{p'} = s_{p}+1$$$. From our assumption that $$$s_p$$$ is the special index of $$$p$$$, we already have that $$$p'_i > p'_{s_p+1}$$$ if $$$1 \leq i<s_{p}+1$$$ and $$$p_{s_p+1} \leq p_i$$$ if $$$s_p+1<i$$$. It only remains to prove that $$$p'_0 > p'_{s_p+1}$$$.

Since $$$p_k=-1$$$, it must be true that $$$p_{s_p} \leq -1$$$. We obtain $$$p'_0=0>-1\geq p_{s_p}$$$. Therefore, $$$p'_0 > p'_{s_p+1}$$$ and $$$s_{p'}=s_p+1$$$ is the special index of $$$p'$$$.

Case 2

Suppose that $$$s_p = 2n$$$. We only have to prove that all elements of $$$p'$$$ are non-negative to claim that $$$s_{p'}=0$$$. This is easy by contradiction. Suppose that $$$p'_j < 0$$$. Then it is impossible that $$$0 > p_{j-1} > p_{2n}=-1$$$. $$$\blacksquare$$$

In fact, our claim is a modified version of cycle lemma where we have $$$m=n+1$$$ and $$$k=1$$$ (see, for instance, $$$[3]$$$ for two nice proofs -- one by arranging the sequence on a circle and removing certain segments, and the other using an idea similar to the prefix sum idea presented above).

Now, let us rotate the string until $$$s_p=2n$$$. By our above claim, there is a unique position that satisfies this. since there are $$$n$$$ $$$\texttt{(}$$$s and $$$n+1$$$ $$$\texttt{)}$$$s, we have $$$p_{2n}=p_{s_p}=-1$$$. So, $$$p_i \geq 0$$$ for all $$$0 \leq i < 2n$$$. That is, the first $$$2n$$$ characters of the string is now a valid bracket sequence.

This translation is extremely abridged because I do not want to translate some stupid story line about the main characters from Chū-2 playing Yu-Gi-Oh.

There are $$$m$$$ cards. An array $$$a$$$ of length $$$n \leq m$$$ describes these cards where $$$m = \sum\limits_{i=1}^n a_i$$$. If $$$i \leq n$$$, then the $$$i$$$-th card has the string $$$\underbrace{\texttt{((}\ldots\texttt{(}}_{a_i-1 \ \text{times}}$$$. Otherwise, the $$$i$$$-th card has the string $$$\texttt{)}$$$. Out of all $$$m!$$$ ways to order the cards, find the number of valid orderings such that the cards, when read left to right, forms a valid bracket sequence.

Constraints:

• $$$1 \leq n \leq 40$$$
• $$$1 \leq a_i \leq 10^5$$$

Let's do the same set-up as earlier by adding an extra card that has the string $$$)$$$. Then we define the equivalence class in the same way, except now each equivalence class only has $$$m+1$$$ elements (well, we only have $$$m+1$$$ cards). I claim that each equivalence class still has exactly $$$1$$$ valid rotation.

Let's pretend that the cards don't exist for a while and we are just dealing with strings of length $$$2(n-m)+1$$$. We know that out of the $$$2(n-m)+1$$$ rotations, exactly one is valid, so our only concern is that this valid rotation is not present when we add on constraint about rotation with the "barriers" of the cards. But this will never happen because the string will be of this form $$$\texttt{(}X\texttt{))}$$$.

It is not too hard to show that each of the $$$3$$$ brackets belong to different cards due to the types of string that can be written on each cards. That is, we first have a valid rotation out of the possible $$$m+1$$$ rotations when accounting for the "barriers" of the cards, and the last character corresponds to a single card, so we can simply remove it.

Let's count first the number of ways with the addition of the extra card (remember that even if two cards have the same string, they are distinguishable). We have two types of cards — $$$\texttt{((}\ldots\texttt{(}$$$ and $$$\texttt{)}$$$. We have $$$n$$$ cards of the first type and $$$m-n+1$$$ cards of the second types. Overall, we have $$$\frac{1}{m+1} (m+1)! = m!$$$ valid ways to arrange them.

However, we have overcounted as we added our extra card. But no problems, it is easy to see that we counted each unique sequence $$$m-n+1$$$ times since each card of type $$$)$$$ has equal probability to be the last card that is removed. So, just divide our answer by $$$m-n+1$$$ and we get the answer of $$$\frac{m!}{m-n+1}$$$.

We are enumerating balanced bracket sequences that have length $$$2n$$$ and the first $$$k$$$ elements are $$$\texttt{(}$$$. This is equivalent to enumerating the bracket sequence which have $$$n-k$$$ $$$\texttt{(}$$$s and $$$n$$$ $$$\texttt{)}$$$s where $$$p_i \geq -k$$$.

Let us study the distinct binary strings with $$$n-k$$$ $$$\texttt{(}$$$s and $$$n+1$$$ $$$\texttt{)}$$$s. Instead of defining a special index, let us define a special set of indices $$$s_p$$$. Let $$$mn$$$ be the minimum value of the prefix sum. We will store the special leftmost index with values in the range $$$[mn,mn+k]$$$, so we are storing $$$k+1$$$ indices in our set. Note that $$$k+1$$$ is equal to the difference between the number of $$$\texttt{(}$$$ s and $$$\texttt{)}$$$ s.

Now, with a similar case work to our original solution, we can show that this set similarly rotates with our string (exercise to reader). The claim is now that if and only if $$$2n-k \in s_p$$$, then the concatenation of $$$\underbrace{\texttt{((}\ldots\texttt{(}}_{k \ \text{times}}$$$ with the first $$$2n-k$$$ characters of the string gives us a balanced bracket sequence.

Suppose that $$$2n-k \in s_p$$$. Since $$$p_{2n-k}=-k-1$$$, then we have $$$p_i \geq -k$$$ for $$$0 \leq i < 2n-k$$$. Suppose that this is not true, that is we have $$$p_j < -k$$$ for some $$$j$$$, Let us define $$$p_{-1}=0$$$ for convinience. By the definition of prefix sum, we have $$$|p_i-p_{i-1}| =1$$$ for $$$0 \leq i < 2n-k$$$. Since $$$p_{-1}=0$$$ and $$$p_j < -k$$$, by discrete intermediate value theorem, there exists $$$p_z = -k$$$ for some $$$0 \leq z < j$$$. This contradicts the fact that $$$2n-k$$$ was the leftmost index with value $$$-k-1$$$. So it is proven for this case.

Suppose that $$$2n-k \notin s_p$$$. Either $$$-k-1 \notin [mn,mn+k]$$$ or $$$2n-k$$$ is not the leftmost index with value $$$-k-1$$$. Both of these contradict our statement. So it is proven for this case too.

Now, let us study a single equivalence class defined by the same equivalence relation of $$$s \sim_R t$$$ when $$$s$$$ is a cyclic shift of $$$t$$$. But we need to note here that not all equivalence classes have the same size. Indeed, let $$$n=3$$$ and $$$k=1$$$. Then we are studying strings that are a permutation of $$$\texttt{(())))}$$$. In the equivalence class containing $$$\texttt{())())}$$$, there are only $$$3$$$ elements, while in the equivalence class containing $$$\texttt{(())))}$$$, there are $$$6$$$ elements. But this is actually fine.

Given a string $$$s$$$, choose the shortest string $$$t$$$ such that $$$s$$$ is the concatenation of some copies of $$$t$$$. Then, the number of elements in the equivalence class containing $$$s$$$ is $$$|t|$$$.

We now want to show that of those $$$|t|$$$ elements, $$$\frac{k+1}{n+1} \cdot \frac{|t|}{|s|}$$$ of them satisfy $$$2n-k \in s_p$$$.

I claim that if $$$x \in s_p$$$, then $$$(x+|t|) \% (2n-k+1) \in s_p$$$. It is not too hard to prove this by noting that $$$p_{|t|}<0$$$, since the ratio of bracket types in $$$s$$$ and $$$t$$$ are the same.

Therefore, pick any element in the equivalence class. By the property of elements of $$$s_p$$$ being rotated while we rotate the string, the number of strings that correspond to valid bracket sequences is the number of elements in $$$(2n-k-|t|,2n-k] \cap s_p$$$. Since, we know that if $$$x \in s_p$$$, then $$$(x+|t|) \% (2n-k+1) \in s_p$$$, we have $$$\sum\limits_{i=0}^\frac{|s|}{|t|} |(-1+i \cdot |t|,-1+(i+1) \cdot |t|] \cap s_p| = |s_p| = \frac{|s|}{|t|} \cdot |(2n-k-|t|,2n-k] \cap s_p|$$$.

Therefore, we conclucde that $$$|(2n-k-|t|,2n-k] \cap s_p| = (k+1) \cdot \frac{|t|}{|s|}$$$. That is to say, in each equivalence class, there is a $$$\frac{k+1}{|s|}= \frac{k+1}{2n-k+1}$$$ probability that some element corresponds to a bracket sequence.

Since there are $$$\binom{2n-k+1}{n-k}$$$ elements total, there are $$$\frac{k+1}{2n-k+1} \binom{2n-k+1}{n-k}$$$ elements that correspond to bracket sequences where the first $$$k$$$ elements are $$$\texttt{(}$$$ s.

In fact, this gives us a way to generate a uniform random balanced bracket sequence of length $$$2n$$$ where the first $$$k$$$ elements are $$$\texttt{(}$$$ s. Generate a random string with $$$n-k$$$ $$$\texttt{(}$$$ s and $$$n+1$$$ $$$\texttt{)}$$$ s. The equivalence class that this string will be in is obviously proportional to the number of elements in said equivalence class. Now, we could pick a random element of $$$(2n-k-|t|,2n-k] \cap s_p$$$, but you can simply pick a random element of $$$s_p$$$ and it will be equivalent.

Oh course, we could use the method of incrementally placing $$$\texttt{(}$$$ or $$$\texttt{)}$$$ by their correct ratio, but this is way cooler.

#include <bits/stdc++.h>

#include "testlib.h"

std::string balanced_bracket_sequence_v1(int n) {
    auto res = std::string(n, '(') + std::string(n + 1, ')');
    shuffle(res.begin(), res.end());
    std::vector<int> pref(2 * n + 2, 0);
    for (int x = 0; x < 2 * n + 1; x++)
        pref[x + 1] = pref[x] + (res[x] == '(' ? 1 : -1);
    int idx =
        int(std::min_element(pref.begin(), pref.end()) - pref.begin());
    std::rotate(res.begin(), res.begin() + idx, res.end());
    return res.substr(0, 2 * n);
}

std::string balanced_bracket_sequence_v2(int n) {
    auto a = std::string(n, '(') + std::string(n, ')');
    shuffle(a.begin(), a.end());
    auto output = a;
    for (int l_in = 0, l_out = 0, r_in = 2 * n; l_in < r_in;) {
        int pos = l_in;
        int balance = 0;
        for (; pos != r_in; ++pos)
            if ((balance += (a[pos] == '(' ? +1 : -1)) == 0) break;
        if (a[l_in] == '(') {
            for (; l_in <= pos; ++l_in, ++l_out) output[l_out] = a[l_in];
        } else {
            const int sz_u = r_in - pos - 1, r_out = l_out + sz_u + 1;
            output[l_out] = '(', output[r_out] = ')';
            for (int i = l_in + 1, j = r_out + 1; i != pos; ++i, ++j)
                output[j] = (a[i] == '(' ? ')' : '(');
            l_in = pos + 1;
            l_out++;
        }
    }
    return output;
}

std::string balanced_bracket_sequence_v3(int n) {
    long long a = 0, b = 0;
    std::string res;
    for (int x = 0; x < 2 * n; x++) {
        if (rnd.next((2 * n - a - b) * (a - b + 1)) <
            (n - a) * (a - b + 2)) {
            res += '(';
            a++;
        } else {
            res += ')';
            b++;
        }
    }
    return res;
}

struct tree {
    int node;
    tree *l, *r;
    tree(int node_, tree* l_, tree* r_) : node{node_}, l{l_}, r{r_} {}
};

int get_value(tree* t) {
    if (t) return t->node;
    return -1;
}

using representation_t = std::vector<std::tuple<int, int, char>>;

auto representation(tree* t) {
    representation_t repr;
    auto dfs = [&repr](auto self, tree* a) -> void {
        if (!a) return;
        repr.emplace_back(a->node, get_value(a->l), 'L');
        repr.emplace_back(a->node, get_value(a->r), 'R');
        self(self, a->l);
        self(self, a->r);
    };
    dfs(dfs, t);
    return repr;
}

auto shuffled_representation(int n, representation_t r) {
    std::vector<int> p(n);
    std::iota(p.begin(), p.end(), 0);
    shuffle(p.begin(), p.end());  // shuffle vertex labels
    for (auto& [n1, n2, dir] : r) {
        if (n1 != -1) n1 = p[n1];
        if (n2 != -1) n2 = p[n2];
    }
    shuffle(r.begin(), r.end());  // shuffle edge order
    return r;
}

tree* binary_tree_from_balanced_bracket_sequence(const std::string& s) {
    int n = int(s.size()) / 2;
    std::vector<int> nxt(2 * n, -1);
    std::vector<int> stk;
    for (int x = 0; x < 2 * n; x++) {
        if (s[x] == '(') {
            stk.push_back(x);
        } else {
            nxt[stk.back()] = x;
            stk.pop_back();
        }
    }
    int node = 0;
    std::vector<tree*> roots(2 * n, nullptr);
    for (int x = 2 * n - 1; x >= 0; x--) {
        if (s[x] == '(') {
            tree *left = nullptr, *right = nullptr;
            if (s[x + 1] == '(') left = roots[x + 1];        // left child
            if (nxt[x] + 1 < 2 * n && s[nxt[x] + 1] == '(')  // right child
                right = roots[nxt[x] + 1];
            roots[x] = new tree(node++, left, right);
        }
    }
    return roots[0];
}

int main(int argc, char* argv[]) {
    registerGen(argc, argv, 1);
    int n = opt<int>("n");
    int t = opt<int>("t");
    std::cout << t << '\n';
    for (int test = 1; test <= t; ++test) {
        std::cout << n << '\n';
        auto rep = shuffled_representation(
            n, representation(binary_tree_from_balanced_bracket_sequence(
                   balanced_bracket_sequence_v1(n))));
        for (auto [parent, child, direction] : rep)
            std::cout << parent + 1 << ' ' << child + 1 << ' ' << direction
                      << '\n';
    }
}

#include "testlib.h"
#include <bits/stdc++.h>
using namespace std;

string bSeq(int n,int k) {
    string res=string(n-k,'(')+string(n+1,')');
    shuffle(res.begin(),res.end());
    deque<int> dq(k+1);
    
    int mn=0;
    int curr=0;
    for (int x=0;x<=2*n-k;x++){
    	curr+=(res[x]=='('?1:-1);
    	if (curr<mn){
    		mn=curr;
    		dq.push_back(x);
    		dq.pop_front();
    	}
    }
    
	rotate(res.begin(),res.begin()+dq[rnd.next(k+1)]+1,res.end());
    return string(k,'(')+res.substr(0,2*n-k);
}

int main(int argc, char* argv[]) {
    registerGen(argc, argv, 1);
    int n=atoi(argv[1]),k=atoi(argv[2]);
    
    cout<<bSeq(n,k)<<endl;
}

#include <bits/stdc++.h>
using namespace std;

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))

mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
uniform_real_distribution<double> dist(0.0, 1.0);

double cat[10000005];
double t[10000005];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cat[0]=1;
	rep(x,0,10000000) cat[x+1]=(double)(x+0.5)/(x+2)*cat[x];
	
	rep(x,1,100000){
		double tot=0;
		rep(y,0,x){
			double prob=cat[y]*cat[x-y-1]/(4*cat[x]);
			t[x]+=prob*(t[y]+t[x-y-1]+min(y,x-y-1));
			tot+=prob*min(y,x-y-1);
		}
	}
	
	rep(x,1,100000) cout<<x<<" "<<t[x]<<endl;
}

#include <bits/stdc++.h>
using namespace std;

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))

mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
uniform_real_distribution<double> dist(0.0, 1.0);
 
long long time(){
	return chrono::system_clock::now().time_since_epoch().count();
}
 
double cat[10000005];

void solve(int pl,int pr,string &s){
	if (pl==pr) return;
	
	double temp=dist(rng);
	int n=(pr-pl)/2;
	
	double curr=0;
	int l=0,r=n-1;
	int ss;
	
	while (true){
		{ //add l
			curr+=cat[l]*cat[n-1-l]/(4*cat[n]);
			if (temp<curr){ ss=l; break; }
			l++;
		}
		{ //add r
			curr+=cat[r]*cat[n-1-r]/(4*cat[n]);
			if (temp<curr){ ss=r; break; }
			r--;
		}
	}
	
	s[pl+1+2*ss]=')';
	solve(pl+1,pl+1+2*ss,s);
	solve(pl+2+2*ss,pr,s);
}

string gen(int n){
	cat[0]=1;
	rep(x,0,n) cat[x+1]=(double)(x+0.5)/(x+2)*cat[x];
	
	string res(2*n,'(');
	solve(0,2*n,res);
	return res;
}

signed main(int argc, char *argv[]){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	rep(x,0,24){
		long long start=time();
		long long num=0;
		while (time()-start<10000000000){
			gen(1<<x);
			num++;
		}
		
		long long end=time();
		cout<<(1<<x)<<" "<<num<<" "<<end-start<<" "<<(double)(end-start)/(num*(1<<x))<<endl;
	}
}

1 266547240 10000000078 37.5168
2 187154707 10000000050 26.7159
4 102058691 10000000091 24.4957
8 47076531 10000000131 26.5525
16 22151581 10000000151 28.2147
32 10758623 10000000660 29.0465
64 5403745 10000009142 28.9152
128 2734025 10000000066 28.5751
256 1338297 10000004834 29.1882
512 660750 10000010888 29.5592
1024 328150 10000004632 29.7597
2048 158510 10000011967 30.8045
4096 77867 10000111333 31.3539
8192 38048 10000260495 32.0841
16384 18565 10000365194 32.8777
32768 9273 10000355466 32.9113
65536 4657 10000484304 32.7669
131072 2277 10004361811 33.521
262144 1104 10004416345 34.5687
524288 548 10006717357 34.829
1048576 270 10012533429 35.3655
2097152 130 10035361701 36.8095
4194304 65 10088588940 37.0047
8388608 33 10127937055 36.5862