Prutekoi's blog

填一个一年前的坑

有$n$只猴子选大王,编号顺时针从$0$到$n-1$,从$1$号猴子开始顺时针从$1$报数,报到$m$的猴子退到圈外,接着从$1$报数,最后剩下的猴子成为大王。

考虑递推,假设已经知道了$n-1$只猴子时编号为$x$的猴子会成为大王。
而且我们知道$n$只猴子时第一个出圈的是$(m-1)\%n$号猴子,那么可以把剩下的猴子重编号成为子问题。可以推出$(x+m)\%n$会成为大王。
于是有一个$O(n)$递推的做法。

特别地,当$m=2$,猴子编号从$1$到$n$时我们有更优秀的做法。首先,若$n=2^k$则易得$1$号猴子就是大王。设$n=2^k+t,t<2^k$,则考虑先$t$个猴子出圈之后下一只猴子就是大王。于是易得$2*t+1$号猴子成为大王。
值得一提的是,设$J(n)$为$n$只猴子时的答案,则$J(n)$即为$n$在二进制下循环左移一位,这个通过刚才推得的结论易得。