约瑟夫环

约瑟夫问题是个著名的问题：N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。

当N,M较大时，直接模拟显然很蠢，因此需要一种更高效的方法！

公式法

我们给每一个人从$0$到$N-1$编号。问题转变成求最后一个胜利者的编号。

定义$f(N, M)$为：$N$个人报数，报到$M$的人被杀掉时，最终获胜者的编号。

接下来，我们思考一下$f(N,M)$与$f(N-1,M)$之间是否存在递推关系

假设$f(N-1,M)$得到的获胜者为$N-1$个人中的第$x$个（编号不一定为$x$），那么他在原来的$N$个人中应当是第$(M + x) \% N$个人（从0开始算）

因而有

$$f(N,M)=(f(N-1,M) + M) \mod N$$

def survivor(N: int, M: int):
    survivor_idx = 0
    for n in range(2, N + 1):
        survivor_idx = (survivor_idx + M) % n
    return survivor_idx

复杂度$O(n)$

约瑟夫环优化

例题: HDU 3089

约瑟夫环，求最后活下来的人的序号。

数据范围: $N\le10^{12},M\le 1000$

显然对于本题，上述算法不再适用。

可以观察到，本题的$M$比较小，可以做一下优化：

记$f(n,M)$的转移方程有两种情况

$$X=f(n-1, M)+M\\F(n, M)=\left\{\begin{aligned}X, X<n \\X\%n , X\ge n\end{aligned}\right.$$

对于第一种情况，显然可以将多次递推合并；第二种情况不优化，直接递推。

现在考虑$N=8,M=3$的情况

在第一圈时，会筛掉$\lfloor\frac{8}{3}\rfloor=2$个人，令$s=M*\lfloor{\frac{8}{3}}\rfloor$，从第$s+1$个人开始重编号，如下表所示：

	A	B	C	D	E	F	G	H
原编号	0	1	2	3	4	5	6	7
重编号	2	3	/	4	5	/	0	1

易得尾部共有$k=n - s + 1=n\%M=2$个人

问题转化为$n'=6$的子问题，假设子问题的答案为$ans'$，分两种情况讨论：

1. $ans' < k$：即最终获胜者在尾部，其对应的编号$ans=ans'+$s
2. 若$ans'\ge k$：即最终获胜者不在尾部，其对应的编号$ans=ans'-k+\lfloor\frac{ans'-k}{M-1}\rfloor$

当$n\le k$时，直接老方法递归即可。

切记最后再特判一下$M=1$的情况。

时间复杂度$O(MlogN)$

AC代码

#include <iostream>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

ll calc(ll n, ll m){
	ll ans = 0;
	for(int i=2; i<=n; i++){
		ans = (ans + m) % i;
	}
	return ans;
}

ll solve(ll n, ll m){
	if(m == 1) return n - 1;
	if(n <= m) return calc(n, m);
	ll k = n % m, s = n / m * m;
	ll ans = solve(n - n / m, m);
	if(ans < k) return ans + s;
	return ans - k + ((ans - k) / (m - 1));
}

signed main(){
    Android;
	ll n, m;
	while(cin >> n >> m){
		cout << solve(n, m) + 1 << '\n';
	}
}

参考链接

https://blog.csdn.net/u011500062/article/details/72855826

https://www.zhihu.com/question/273665007