CF1840G2 题解

Lucky_Xiang · 2023-06-09 09:59:02 · 题解

题目

CF1840G2

思路

对于 Easy Version，可以参考 BSGS 算法的思路，先转 \sqrt{n} 次一格，就可以记录相邻 \sqrt{n} 格的数字；再不停地转 \sqrt{n} 格，直到出现前面记录的数字，就知道转了一圈了，总操作次数 2\sqrt{n}。

Code

但是我们并没有充分利用询问的信息。假如一次操作后得到的数字为 x，它不仅可以让我们区分不同的格子，而且还告诉我们了一个隐藏信息：最终答案 n\geq x。那么，我们就可以先随机转 k 次并记录得到的最大值 n_0，不妨设 n_0\le n\le n_0+d，则所有的格子就被分为了数量分别为 n-n_0 和 n_0 的两部分。因为 n-n_0\le d，所以我们可以参考 Easy Version 的思路，在数量为 n-n_0 的部分的一端标记 \sqrt{d} 个格子，并从另一端开始不断转 \sqrt{d} 格，就可以确定 n-n_0 的值了，总操作次数 k+2\sqrt{d}。

但是，这个做法不完全正确，因为 n 可能大于 n_0+d。其出错概率 P(A)=({{n-d-1}\over{n}})^k。当 k=400,d=90000 时，P(A) \approx 4.1 \times 10^{-17}，足以通过此题。

Code