问题引入
约瑟夫问题有很多经典例题，例如猴子选王、丢手绢。在算法学习过程中，这是大部分人都会遇到的一类问题。一般地，可以简单的做到$O(n\times m)$模拟解法。
然而在一些情况下，这样的复杂度并不优秀，还可以再搞一搞~
解法介绍
具体数学上有讲
此类问题中，影响到一个人在出圈顺序中的位置 $id$ 的有三个关键参量：他的编号 $i$ 、人数 $n$ 以及出圈间歇 $m$。
在某些情况下，部分参量并不起作用。如 $m|i$ 时， $i$ 对 $id$ 无影响；$m=1$ 时， $n$ 对 $id$ 无影响。在部分题目中这可能成为解题的关键。
该类问题有两种问法，分别是：
时间复杂度$O(nlog \ n)$
这样考虑问题：假定当前出圈的人编号为当前第 $k$ 小，此人出圈后圈内还有 $n$ 人，那么下一个出圈的人为圈内编号第 $(k-1+m-1)\bmod n + 1$ 小。
那么只需要一个数据结构，满足能够单点修改，并查询区间第 $k$ 小的：权值树状数组。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
using namespace std;
struct ValueBIT {
int c[N], maxn;
int lowbit(int x) { return x & (-x); }
void reset(int n) {
maxn = n;
for (int i = 1; i <= maxn; i++) c[i] = lowbit(i);
}
void add(int m, int x) {
for (int i = m; i <= maxn; i += lowbit(i)) c[i] += x;
}
int find_kth(int k) {
int s = 0, sum = 0;
for (int i = 20; i >= 0; i--) {
s += (1 << i);
if (s > maxn || c[s] + sum >= k)
s -= (1 << i);
else
sum += c[s];
}
return s + 1;
}
} vbit;
int n, m;
int main() {
scanf("%d %d", &n, &m);
vbit.reset(n);
int now = 1;
while (n) {
now = (now - 1 + m - 1) % n + 1;
int k = vbit.find_kth(now);
vbit.add(k, -1);
printf("%d ", k);
n--;
}
return 0;
}
询问第$k$出圈
时间复杂度$O(k)$
令 $f(n,m,k)$ 表示第$k$ 出圈人。
那么有公式：
代码实现：1
2
3int f(int n, int m, int k) {
return ((k == 1 ? 0 : f(n - 1, m, k - 1)) - 1 + m) % n + 1;
}
非递归写法：
1 | int f(int n, int m, int k) { |
时间复杂度$O(log{\frac{m}{m-1}} n)$
当 $n>>m$ 时，每次从 1 到 n 的一个循环中，有 $\lfloor \frac{n}{m} \rfloor \times m$人报数，其中 $\lfloor \frac{n}{m} \rfloor$ 人出圈。
参考前面时间复杂度 $O(k)$ 的式子，可以发现在此过程中有许多取模操作是无作用的。
于是我们可以合并一些操作，使得部分加法合并为乘法。
有公式
式中 c 表示从当前的 n 一直变化到到 c 的期间内取模都无作用的最大的 c 。
代码实现：1
2
3
4
5
6
7
8
9int f(int n, int m, int k) {
if (m == 1) return k;
int i = n - k + 1, s = (m - 1) % i;
while (i < n) {
int c = min(n - i, (i - s + m - 2) / (m - 1));
s = (s + m * c) % (i += c);
}
return s + 1;
}
时间复杂度$O(\frac{mk}{n})$
易知第 $k$ 出圈人为第 $k\times m$ 报数人，以此为基础进行推导。
首先明确几个概念：
位置编号：从 $1$ 开始编号到 $n$，表示在圈内的初始编号为$k$ 。
报数编号：从 $1$ 开始编号到 $n\times m$，表示第 $k$ 次报数。
报数：从 $1$ 开始编号到 $m$，表示某人所报的某个数。
首先取一个报数编号$p$ ，对应位置编号 $id$。可以用该式来表示： $p = a \times m + b(0\le a <n,1\le b\le m)$。实际含义是：在第 $a$ 轮报数结束后，报数为 $b$。
那么容易推出以下信息：
此时圈内所剩人员数量为 $n-a$
若此人报数 $b=m$，则此人出局。否则圈内剩余的人将会恰好各报一次数，然后此人会再一次报数。
假设此人未出局，那么 $b<m$。
设此人下一次报数编号为 $q$ ，易知 $q = p + n - a = a \times (m - 1) + b + n$。
那么可以推导: $a = \dfrac{q - n - b}{m-1} = \lfloor \dfrac{q - n - 1}{m - 1} \rfloor$。
所以有：$p = q - n + a = q - n - \lfloor \dfrac{q - n - 1}{m - 1} \rfloor = \lfloor \dfrac{(q - n - 1) \times m}{m - 1} \rfloor + 1$
这样就完成了后继公式到前驱公式的变化，如此不断迭代，直到得到他是第 $k$ 报数人为止。
有公式如下：
代码实现如下：1
2
3
4int g(int n, int m, int x) {
return x <= n ? x : g(n, m, (x - 1 - n) * m / (m - 1) + 1);
}
int f(int n, int m, int k) { return g(n, m, k * m); }
注意到该函数可以非递归实现，给出优化后的代码:1
2
3
4
5int f(int n, int m, int k) {
int s = k * m - 1;
while (s >= n) s = (s - n) * m / (m - 1);
return s + 1;
}
例题：
2018-2019 ACM-ICPC, Asia Shenyang Regional Contest K - Let the Flames Begin
感谢牛逼网友！
更详细的介绍可以看具体数学。