f(n, m) = (f(n - 1, m) + m) % m
清除链表做法的想法,开始考虑如何进行递推,这次我们不考虑空位动态变化,需要标记然后掠过一个下标之类的事情。
先说整体思想:
- 考虑任意 n 个人,走 m 步的约瑟夫环。
- 我们可以先走 m 步,淘汰那个人。
- 然后从下一个人开始,把剩下的路径看作是另一个约瑟夫环。
- 然后我们再考虑,新约瑟夫环下标到原来约瑟夫环的映射关系。
例子:
- n = 5, m = 3
- 0 1 2 3 4
淘汰 2
- 2 3 x 0 1
对应下标 + m) % n
映射会原下标
然后再重新抽象回来考虑一下这大概的思想和为什么会有这样的映射关系:
- 整体上是强调递推的一种 dp,题目的特点在于他是一个环,我们就算有在一个下标连续的环中去掉一个,剩下的下标如果考虑环的话还是连续的。
- 而dp使得我们可以只考虑维护这样一层关系,然后最终解决连续的这样一个问题
虽然确实没法解本题吧。。辅助看看这个 https://www.acwing.com/solution/content/18760/
应该补充的一件事情是 f(1, m) = 0
,可以确定的一个初始状态,表示无论m是怎么值,怎么走,只有一个人的环,赢家是确定的。
这题的变化在于 m 是变化的,我们把 m 替换成 a[i],然后考虑如何确定 i
考虑 x = n 的情况,这个时候借助上面的结论,显然还是有 $f_n = (f_{n - 1} + a[0]) % n$
在这个基础上继续递推,a[0]
就变成 a[1]
了,故可以推断 i = n - x
这里其实算是以 x = n 为一个 baseline 的,其中继续推的结果,比方说 $f{n-1}$ 并不能说明真的元素是那么多的时候结果是那个