T715247 [CFCOI-R4-T3] 最短路查询

$\text{path.cpp},1 \text{ s},512 \text{ MiB}$ -------------- **这是一道交互题。** 你可以在下面示例程序中编辑： ```cpp #include using namespace std; extern "C" long long query(int x); extern "C" int solve(int n){ return -1; } ```

给定 $n$，考虑 $2^n$ 个节点的**无向无权图**，节点标号 $0 \sim 2^n-1$。 对于节点 $x,y$，如果存在 $k \in \mathbb N$ 使得 $x \operatorname{xor} y=2^k$，则在 $(x,y)$ 之间连接一条边。 现在有一个隐藏的节点 $p$，你每次可以向交互库询问 $x$，交互库会给出 $(x,p)$ 之间**本质不同的最短路径条数**。注意这个整数可能超过 `int` 类型的存储范围。 **两条路径本质不同，当且仅当它们经过的点集不同。** 你需要在 $\textcolor{red}{16}$ 次询问内求出 $p$ 的值。 #### 交互说明 你需要实现函数 `int solve(int n)`： 该函数需要在调用不超过 $16$ 次 `query` 函数的情况下，返回 $p$ 的值。 你可以调用函数 `long long query(int x)`： 该函数会返回 $(x,p)$ 之间**本质不同的最短路径条数**，特别地，若 $x

输入文件包含一个整数 $n$，每次测试的 $p$ 将在交互库内实现。 你不需要也不能读入输入文件。

没有输出。

#### 一个可能的交互过程 注意不一定有逻辑。 | 选手程序 | 交互库 | |:-:|:-:| | | `guess(2)` | | `query(0)` | ||$1$| | `query(2)` || ||$2$| | `query(9178)` || ||$-1$| | $1$ || || ok Accepted. | #### 测试方法 你编写的 `solve` 函数会被调用至多 $10^5$ 次。 保证 std 的评测时间不超过 $50 \text{ ms}$，空间不超过 $5 \text{ MiB}$。 #### 数据范围 对于 $100\%$ 的数据，$2 \le n \le 16,0 \le p < 2^n$。