P13479 [GCJ 2008 AMER SemiFinal] Code Sequence

你正在尝试计算由一个秘密代码生成的数列 $S_n$ 的下一个数字。你已知该代码是按照以下过程生成的。 首先，对于每个 $k$ 从 $0$ 到 $29$，选择一个介于 $0$ 到 $10006$（包含）之间的数字 $C_k$。 然后，对于每个 $n$ 从 $0$ 到 $1\ 000\ 000\ 000$（包含）： - 将 $n$ 写成二进制形式。 - 对于 $n$ 的二进制表示中每一个被置位的比特 $k$，取出对应的 $C_k$。例如，当 $n=5$ 时，二进制下第 $0$ 位和第 $2$ 位被置位，因此取 $C_0$ 和 $C_2$。 - 将这些 $C_k$ 相加，除以 $10007$，输出余数作为 $S_n$。 你将获得数列 $S$ 的一段连续值，但你不知道这些数字在数列中的起始位置（不过你知道数列中至少还有下一个数字），也不知道生成数列时选取的 $C_k$ 的具体值。 请你找出该数列的下一个数字，或者如果无法确定，则输出 UNKNOWN。

第一行包含一个整数 $T$，表示测试用例的数量。 对于每个测试用例，包含： - 一行一个整数 $N$，表示你已知的数列 $S$ 的元素个数。 - 一行包含 $N$ 个用单个空格分隔的整数，范围在 $0$ 到 $10006$ 之间，表示已知的数列元素。

对于每个测试用例，输出一行，格式为 “Case #$X$: $Y$”，其中 $X$ 是测试用例编号（从 $1$ 开始），$Y$ 是该数列的下一个数字，或者如果无法确定则输出字符串 UNKNOWN。

**样例解释** 在第一个样例中，$C_0$、$C_1$ 和 $C_2$ 可能分别为 $1$、$2$ 和 $4$，我们已知的 $S_n$ 是从 $n=1$ 开始的。如果是这样，我们并不知道 $C_3$ 的值，因此下一个数列值可能是任意值！所以答案是 UNKNOWN。 在第二个样例中，我们无法知道所有 $C_k$ 的值，甚至不知道 $n$ 是多少，但我们可以证明，在任何数列中，如果 $1$、$10$、$11$、$200$ 按顺序出现，那么下一个值一定是 $201$。 **数据范围** - $1 \leqslant T \leqslant 20$ **小数据范围（7 分，测试点 1 - 可见）** - $1 \leqslant N \leqslant 5$ **大数据范围（15 分，测试点 2 - 隐藏）** - $1 \leqslant N \leqslant 1000$ 由 ChatGPT 4.1 翻译