gym104090 The 2022 ICPC Asia Hangzhou Regional Programming Contest I. Guess Cycle Length

题目大意

交互题

给出一个长度为n的排列p，初始有一个人在某个位置（未知）

每次询问可以给出一个步数x，然后人会向前走x步并返回所在位置的数字

在1e4次询问内找到n，n<=1e9

保证排列在交互前固定

题解

显然，要想知道n就必须要重复走到某个点，否则不同的点之间的关系是未知的

一个简单的想法是，先走k步走出一个长度为k的段，然后k步k步地跳，这样一圈下来一定会走到一开始的段

k取sqrt(n)得2sqrt(n)次，寄？

---

然后发现很重要的一点是，返回的是数字p[i]

也就是说，如果随机把人丢到一个位置，那么p的期望是n/2

同理，如果随机丢k次，则p的期望是nk/(k+1)，和n的误差仅有n/(k+1)

这样就可以搞事了（注意次数≠步数
①先随机丢k次random步，那么可以得到t≈nk/(k+1)，可以等价于向后走n/(k+1)步
②然后走k次1步，走出一个长为k的段A
③之后走1次t步，那么会走到段A末尾再向前n/(k+1)步的位置
④最后k步k步跳，大概跳n/k^2次就可以走到段A里面，刚好走完一圈

算一下次数，①k+②k+③1+④n/k^2，当k取1000时就只用3000次，所以k取3000就差不多了
（③④一定可以保证正确性，1e4次数也是用不完的

原文地址：https://www.cnblogs.com/gmh77/p/16978223.html