期望环大小为 $n^{1/4}$ 的时候就能找到解
by liqingyang @ 2022-11-28 19:12:16
@[liqingyang](/user/272088) 那环巨大怎么办?
by hbhz_zcy @ 2022-11-28 19:14:41
@[hbhz_zcy](/user/142549) 期望和环大小无关吧,就是说环大还是小都期望走那么多次
by liqingyang @ 2022-11-28 19:15:40
@[liqingyang](/user/272088) 但是我觉得可能一旦参数选错了它就要把整个环走完因此耗费很长的时间。
我原来写的是跑完整个环,跑一组数据可能跑1分钟也可能10ms。
by hbhz_zcy @ 2022-11-28 19:19:39
@[hbhz_zcy](/user/142549) ?跑一个环的复杂度是环长级别的啊?而且这个东西的期望应该是比较稳定的,您真的能造出来跑 1min 的情况?
by liqingyang @ 2022-11-28 19:22:21
@[liqingyang](/user/272088) 我跑的样例,过 int 的就很难跑过去。
我仔细看了一下,第一篇题解似乎是不断倍增环长上限的。
可能是我写的有毛病吧。
by hbhz_zcy @ 2022-11-28 19:26:52
这是带上我那个优化的。
<https://www.luogu.com.cn/record/95980120>
by hbhz_zcy @ 2022-11-28 19:27:53
估计是复杂度假了,正常期望跑 $n^{1/4}$ 次就能找到解应该是能过的
by liqingyang @ 2022-11-28 19:29:39
我是**,写成了 $x'=ax+c$
by hbhz_zcy @ 2022-11-29 11:37:57
最新结果:
<https://www.luogu.com.cn/record/96121428>
by hbhz_zcy @ 2022-11-30 15:19:22