本文探究了约瑟夫问题的相关知识。

写在前面

由于可恶的2019-nCOV， 0xfaner 寒假被困在家里无事可做~~被水淹没~~。

于是他决定探究一下著名的约瑟夫问题Josephus problem。

问题介绍

约瑟夫问题有很多经典例题，例如猴子选王、丢手绢。在算法学习过程中，这是大部分人都会遇到的一类问题。然而大家往往只知道 $ \mathcal{O}(n m) $ 的模拟解法……

首先给出该问题的情景： $ n $ 个人围成一圈，编号为 $ 1 $ 到 $ n $ 。从 $ 1 $ 号最先从 $ 1 $ 开始报数，每次报到 $ m $ 的人出圈，下一个人重新从 $ 1 $ 开始报数，直到剩下最后一人为止。

解法介绍

其中影响到一个人在出圈顺序中的位置 $ id $ 的有三个关键参量：他的编号 $ i $ 、人数 $ n $ 以及出圈间歇 $ m $ 。

在某些情况下，部分参量并不起作用。如 $ m|i $ 时， $ i $ 对 $ id $ 无影响； $ m = 1$ 时， $ n $ 对 $ id $ 无影响……在部分题目中这可能成为解题的关键。

该类问题有两种问法，分别是：

询问约瑟夫排列（即出圈顺序
询问第 $ k $ 出圈（第 $ n $ 出圈为获胜者

询问约瑟夫排列

一般情况

时间复杂度 $ \mathcal{O}(n \log n) $ 。

这样考虑问题：假定当前出圈的人编号为当前第 $ k $ 小，此人出圈后圈内还有 $ n $ 人，那么下一个出圈的人为圈内编号第 $ (k-1+m-1)\bmod n +1$ 小。

那么只需要一个数据结构，满足能够单点修改，并查询区间第 $ k $ 小的：权值树状数组。

#include <bits/stdc++.h>
using namespace std;
#define N 1000001
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 $ 出圈

时间复杂度 $ \mathcal{O}(k) $

令 $ f(n,m,k) $ 表示第 $ k $ 出圈人。

有公式

$f(n,m,k)= \left \{\begin{array}{} (m - 1) \bmod n + 1 & , k = 1 \\ (f(n - 1, m, k - 1) -1 + m) \bmod n + 1 & , k > 0 \end{array} \right.$

代码实现如下

1
2
3

int f(int n, int m, int k) {
    return ((k == 1 ? 0 : f(n - 1, m, k - 1)) - 1 + m) % n + 1;
}

当然也有非递归的写法

int f(int n, int m, int k) {
    int s = (m - 1) % (n - k + 1);
    for (int i = n - k + 2; i <= n; i++) s = (s + m) % i;
    return s + 1;
}

时间复杂度 $ \mathcal{O}(\log_{\frac{m}{m - 1}}n) $

当 $ n>>m $ 时，每次从 $ 1 $ 到 $ n $ 的一个循环中，有 $ \lfloor \frac{n}{m} \rfloor \times m $ 人报数，其中 $ \lfloor \frac{n}{m} \rfloor $ 人出圈。

参考前面时间复杂度 $ \mathcal{O}(k) $ 的式子，可以发现在此过程中有许多取模操作是无作用的。

于是我们可以合并一些操作，使得部分加法合并为乘法。

有公式

$f(n, m, k) = (f(n - c, m, k - c) - 1 + m \times c) \bmod n + 1$

式中 $ c $ 表示从当前的 $ n $ 一直变化到到 $ c $ 的期间内取模都无作用的最大的 $ c $ 。

代码如下

int 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;
}

时间复杂度 $ \mathcal{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 \leq a < n $ , $ 1 \leq b \leq 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 $ 报数人为止。

有公式：

$f(n, m, k) = g(n, m, k \times m)$ $g(n, m, x) = \left \{\begin{array}{} x & , x \leq n \\ g(n, m, \lfloor \dfrac{(x - 1 - n) \times m}{m - 1} \rfloor + 1) &, x > n \end{array} \right.$