CF1299E So Mean题解

通过观察和自己动手模拟，可以得到：

1. 假如我们询问 $n$ 次，第 $i$ 次询问的数恰好不包含 $a_i$，则回答是 1 当且仅当 $a_i=1$ 或 $a_i=n$。

推广一下：

2. 假如我们已经得到了 $1,2,\dots,k,n-k+1,\dots,n$ 的位置，则询问 $n-2k$ 次，第 $i$ 次询问的数恰好不包含 $a_i$ 以及所有已知数，则回答是 1 当且仅当 $a_i=k+1$ 或 $a_i=n-k$。

但是怎么确定哪个是 $k+1$ 哪个是 $n-k$ 呢？事实上，

3. $1,n$ 的位置可以任意确定，假如不合法最后令 $n-a_i+1\to a_i$ 即可。

4. $1$ 确定后可以用 $n$ 次询问确定所有位置的奇偶性，进而确定哪个是 $k$，哪个是 $n-k+1$。

由此，我们可以在 $O(n^2)$ 次询问中得到整个排列，可以得到 $20\%$ 的分数。

让我们先用以上方法找出 $1\sim 4$，$n-3\sim n$。考虑用中国剩余定理解决本题：假如知道每个位置的数模上 $3,5,7,8$ 的值就能求出每个位置的精确值。

5. 将 $x$ 与两种模三不同余的数对放在一起询问，就能确定 $x\bmod 3$。
   由此，可以询问最多两次 $x,1,2$，$x,1,3$ 来求 $x\bmod 3$。

推广一下，容易发现：

6. 将 $x$ 与 $k$ 种模 $k$ 不同余的 $k-1$ 元数组放在一起询问，就能确定 $x\bmod k$。
   由此，可以询问最多 $4,6,7$ 次求出 $x\bmod 5,7,8$。

但是非常悲惨地，要找到模 $8$ 的余数，就意味着需要至少求得 $1\sim 5,n-4\sim n$，并且询问次数已经完全不允许了。

怎么办呢？稍微转换下思路：我们使用倍增。

7. 按照奇偶性，假如是奇数就询问 $x,1,2,4$，否则询问 $x,1,2,3$，可以用 $n$ 次询问求出 $x\bmod 4$。

推广一下：

8. 按照 $x\bmod 4$，分别按照 $0,1,2,3$ 询问不同的七元组，可以可以用 $n$ 次询问求出 $x\bmod 8$。

至此，我们花费了 $5n + (n + \frac{2n}{3}) + (n + \frac{4n}{5} + \frac{3n}{5} + \frac{2n}{5}) + (n + \frac{6n}{7} + \dots + \frac{2n}{7}) + n + n \sim 15.324 n$ 次询问，可以通过 $70\%$ 的数据（由于数据随机，你甚至可以拿到 $90\%$ 的分数）。我们只需要再稍微优化一下：

9. 通过 $1,2,n,n-1$ 确定模 $3$ 和 $4$ 的余数，之后我们只需要验证时可以确定模 $12$ 的余数。

你还可以找到其他优化，足以通过本题（使用9.你可以把询问次数缩减到 $13.67n$，加上其他优化你甚至可以将询问数减少到 $13n$ 以下） 。