CF2157G.Isaac's Queries

wavetearz - contemporary chemical bonds

⠀

你已经到达了热门 roguelike 游戏“Isaac's Keybindings”的最终关卡。这一次，你遇到的不是 Boss，而是一个手里握有一个隐藏整数数组 $a_1, a_2, \ldots, a_n$ 的商人，其中对于每个 $i \in [1, n]$ ，都有 $0 \leq a_i < 2^{30}$ 。

保证该数组是随机生成的，也就是说，每个 $a_i$ （$1 \leq i \leq n$）是独立均匀随机地从 $[0, 2^{30})$ 区间中选择的整数，除了样例之外，所有测试点均如此。

定义 $f(u, v) = a_u \oplus a_{u+1} \oplus \ldots \oplus a_v$，其中 $\oplus$ 表示按位异或（XOR）操作。

你可以进行如下形式的查询：$\texttt{? u v}$，其中 $1 \leq u \leq v \leq n$。

对于每个查询，回答如下：

• 如果 $f(u, v) = 0$，答案为 $-1$；
• 否则，答案为 $\lfloor \log_2(f(u, v)) \rfloor$。

每次查询的费用为 $\frac{1}{v-u+1}$ robocoins。对于每份测试，你总共拥有 $300$ robocoins 要通过最多 $30$ 个测试用例（即平均每组最多消耗 $10$ robocoins）。如果你的余额任意时刻变成负数，你会判负。注意余额可以非整数。

你需要在不超出 robocoins 限制的前提下，找出所有 $\frac{n(n+1)}{2}$ 个可能的查询的答案。

每组测试包含若干测试用例。第一行为测试用例组数 $t$（$1 \le t \le 30$）。每组测试用例描述如下。

每个测试用例的第一行包含一个整数 $n$（$n = 3$ 或 $n = 100$），表示数组 $a_1, a_2, \ldots, a_n$ 的长度。保证除了样例外，所有测试的数组均为随机生成。

本题一共包含 $50$ 个测试点（包含样例）。样例测试中 $t = 1$ 且 $n = 3$，其余测试中 $t = 30$ 且 $n = 100$。

本题不允许 Hack。

（题目未给出输出格式，需根据实际交互式评测或具体输出要求实现。）

在样例中，隐藏数组为 $[a_1, a_2, a_3] = [2, 4, 6]$。

• 首先，你查询 $\texttt{? 1 2}$。因为 $f(1,2) = a_1 \oplus a_2 = 6$，答案为 $\lfloor \log_2(6) \rfloor = 2$。
• 然后，你查询 $\texttt{? 1 3}$。因为 $f(1,3) = a_1 \oplus a_2 \oplus a_3 = 0$，答案为 $-1$。
• 然后，你查询 $\texttt{? 2 3}$。因为 $f(2, 3) = a_2 \oplus a_3 = 2$，答案为 $\lfloor \log_2(2) \rfloor = 1$。

现在，即使不知道隐藏数组，你也Claim所有 $6$ 个查询的答案。例如，你声称 $\texttt{? 1 1}$ 的答案为 $1$。

你总共花费了 $1/2 + 1/3 + 1/2 = 4/3$ robocoins，低于允许的 $300$ robocoins。

由 ChatGPT 5 翻译