1 条题解
-
0
何老师 (root) LV 0 MOD @ 2021-12-08 17:43:48
刚开始的时候只想到了模拟递推。
就是f[n]表示n个人的时候最后剩下人的编号。那么显然f[1]=1。我们是在减去(m-1)个人的情况下得到的f[n-m+1]那么如果要推算f[n],首先在转换的时候编号都减少了m,再者如果人数过少那么肯定会出现循环,比如1,2,3,4,5,如果从3开始数,m=5的话,一次报号的人是3,4,5,1,2,这样最终剩下的是2。所以在累加m的过程中,一定会出现计算到的数超出当前总人数的情况,所以f[n]=f[n-m+1]%(n-m+1)+m。
但是这样只能过50分。然后就有一个打标发现的规律。
f[m^a+m-1]=m,其他的f[n]=f[n-m+1]+m,那么我们令n=m^a+(m-1)*k 其中(m^a<n<=m^a+1)保证k的系数不能为0。
f[n]=k*m=f[m^a+m-1]+(k-1)*m=k*m.
- 1