P16485 [GKS 2014 #B] Parentheses Order
题目描述
一个长度为 $n$ 的括号序列由 $n$ 个 `(` 和 $n$ 个 `)` 组成。
一个合法的括号序列定义如下：
你可以找到一种方式，通过反复删除相邻的括号对 `()` 使得序列最终变为空。
例如，`( ( ) )` 是一个合法的括号序列：你可以删除第 $2$ 和第 $3$ 个位置上的括号对，得到 `()`，然后再将其清空。
`) ( ) (` 不是一个合法的括号序列：删除第 $2$ 和第 $3$ 个位置上的括号对后，得到 `) (`，此后无法再删除任何括号对。
现在，我们有所有长度为 $n$ 的合法括号序列。请找出其中字典序第 $\mathbf{k}$ 小的序列。
例如，以下是长度为 $3$ 的所有合法括号序列，按字典序排列：
```
( ( ( ) ) )
( ( ) ( ) )
( ( ) ) ( )
( ) ( ( ) )
( ) ( ) ( )
```
输入格式
输入的第一行给出测试用例的数量 $T$。接下来 $T$ 行，每行对应一个测试用例，包含两个整数 $n$ 和 $k$。
输出格式
对于每个测试用例，输出一行形如 `Case #x: y` 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是所有长度为 $n$ 的合法括号序列中字典序第 $\mathbf{k}$ 小的序列。如果不同的长度为 $n$ 的合法括号序列不足 $\mathbf{k}$ 个，则输出 `Doesn't Exist!`。
说明/提示
### 限制
$1 \le T \le 100$。
**小数据集（测试集 1 - 可见）**
$1 \le n \le 10$。
$1 \le k \le 100000$。
**大数据集（测试集 2 - 隐藏）**
$1 \le n \le 100$。
$1 \le k \le 10^{18}$。
翻译由 DeepSeek V4 Pro 完成