1 条题解

  • 0
    @ 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

信息

ID
2331
难度
9
分类
动态规划 | 递推 点击显示
标签
(无)
递交数
1
已通过
1
通过率
100%
上传者