P13060 [GCJ 2020 #1C] Overrandomized

**注意**：每当题目描述中提到"随机选择"时，均表示"在所有有效可能性中均匀随机且独立地选择"。 Banana Rocks 公司开发了一款基于云计算的优质随机数生成服务，旨在成为随机性领域的新黄金标准。 最初的设计是：一组服务器接收一个最多包含 $\mathbf{U}$ 位十进制数字的正整数 $\mathbf{M}$ 作为请求，然后返回一个在 1 到 $\mathbf{M}$ 之间（含端点）随机选择的整数。然而，这些服务器被"过度随机化"了——它们没有使用常规的 0-9 数字输出结果，而是每个服务器都随机选取了 10 个不同的大写英文字母作为数字，并随机将这些字母映射到 0-9 的唯一值。 当前情况的正式描述如下： - 每个服务器有一个由恰好 10 个不同大写字母组成的**数字字符串 $\mathbf{D}$** - 该字符串定义了字母与十进制数字的映射关系：$\mathbf{D}$ 中从左数第 $j$ 个字符（从 0 开始计数）代表数值为 $j$ 的数字 - 例如，若 $\mathbf{D}$ 为 `CODEJAMFUN`，则 `C` 代表数字 0，`O` 代表数字 1，`N` 代表数字 9。数字 379009 将被编码为 `EFNCCN` 当服务器收到第 $i$ 个参数为 $M_i$ 的查询时，会： 1. 从 1 到 $M_i$ 的范围内随机选择一个整数 $N_i$ 2. 使用 $\mathbf{D}$ 中的字母数字表示法将其转换为无前导零的十进制字符串 3. 返回结果字符串 $R_i$ 作为响应 我们收集了一些数据，认为可以用来恢复每个服务器的秘密数字字符串 $\mathbf{D}$。我们向每个服务器发送了 $10^4$ 次查询： - 每次查询的 $M_i$ 是从 1 到 $10^{\mathbf{U}}-1$ 范围内随机选择的 - 收到的响应 $R_i$ 是一个最多包含 $\mathbf{U}$ 个大写字母的字符串 - 我们记录了这些 $(M_i, R_i)$ 对 但在将这些记录转移到新存储设备时，部分服务器记录中的所有 $M_i$ 整数值都损坏无法读取了。你能帮我们找出每个服务器的数字字符串 $\mathbf{D}$ 吗？

输入第一行包含测试用例数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例，每个用例包含一个服务器的记录： - 第一行是整数 $\mathbf{U}$，表示查询参数 $M_i$ 的选择范围上限为 $10^{\mathbf{U}}-1$ - 接下来是恰好 $10^4$ 行，每行包含一个十进制整数 $\mathbf{Q}_i$ 和字符串 $\mathbf{R}_i$ - 若 $\mathbf{Q}_i = -1$，表示该次查询的 $M_i$ 未知 - 否则 $\mathbf{Q}_i = M_i$

对于每个测试用例，输出一行 `Case #x: y`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是该服务器对应的数字字符串 $\mathbf{D}$。

**数据范围** - $1 \leqslant \mathbf{T} \leqslant 10$ - $\mathbf{D}$ 是恰好 10 个不同大写字母组成的字符串，从所有可能组合中独立均匀随机选取 - 对所有 $i$，$M_i$ 从 1 到 $10^{\mathbf{U}}-1$ 范围内独立均匀随机选取 - 对所有 $i$，$N_i$ 从 1 到 $M_i$ 范围内独立均匀随机选取 - 对所有 $i$，$R_i$ 是 $N_i$ 的十进制表示，使用 $\mathbf{D}$ 中第 $j$ 个字母代表数字 $j$ **测试集 1（9 分，可见判定）** - 对所有 $i$，$\mathbf{Q}_i = M_i$ - $\mathbf{U} = 2$ **测试集 2（10 分，可见判定）** - 对所有 $i$，$\mathbf{Q}_i = M_i$ - $\mathbf{U} = 16$ **测试集 3（17 分，可见判定）** - 对所有 $i$，$\mathbf{Q}_i = -1$ - $\mathbf{U} = 16$ 翻译由 DeepSeek V3 完成