P7263 Something Comforting
题目背景
> Cause getting made you want more
>
> And hoping made you hurt more
>
> Someone tell me
>
> Something comforting
题目描述
Porter Robinson 花了五年的时间制作了 Something Comforting 这首歌，Mivik 花了五天时间造出了一道和括号序列相关的题。但 Mivik 并不开心，因为他发现他不会造数据了！
Mivik 需要随机生成一个 **合法** 的括号序列，于是 Mivik 想了一会，写出了下面的算法：
```cpp
#include
#include
std::string generate(int n) { // 生成一个长度为 n * 2 的括号序列
const int len = n * 2;
bool arr[len]; // 0 代表左括号，1 代表右括号
for (int i = 0; i < n; ++i) arr[i] = 0;
for (int i = n; i < len; ++i) arr[i] = 1;
std::random_shuffle(arr, arr + len); // 随机打乱这个数组
for (int i = 0, j, sum = 0; i < len; ) {
sum += arr[i]? -1: 1;
if (sum < 0) { // 出现了不合法的位置
for (j = i + 1; j < len; ++j) {
sum += arr[j]? -1: 1;
if (sum == 0) break;
}
// 现在 i 是第一个不合法的位置，j 是 i 后面第一个合法的位置
// ( ( ) ) ) ) ( ( ( ) ( )
// i j
for (int k = i; k
输入格式
无
输出格式
无
说明/提示
### 样例解释
样例一：$n$ 为 1 时，无论怎样都只可能会生成 `()` 这一种合法的括号序列，因此概率为 1。
### 数据范围
对于全部数据，有 $1\le n\le 5\cdot 10^5$，且输入的括号序列合法。
Subtask 1（20 pts）：保证 $1\le n\le 5$。
Subtask 2（30 pts）：保证 $1\le n\le 1000$。
Subtask 3（50 pts）：无特殊限制。