约瑟夫环问题求解

约瑟夫环问题(Josephus)是考察队列的一个经典问题，通常可用循环队列解决，时间复杂度 $O(m*n)$，通过数学递推的解法具有 $O(n)$ 的时间复杂度，是一个很高效的算法。

算法原理

约瑟夫环的递推公式：

\[{\begin{cases} \textrm{formula 1: } f[1]=0; f[i]=(f[i-1]+m)\%i; (i>1) \\ \textrm{formula 2: } f[1]=1; f[i]=(f[i-1]+m)\%i; (i>1); \textrm{if}(f[i]==0) \ f[i]=i; \end{cases}}\]

那么这两个公式有什么不同？首先可以肯定的是这两个公式都正确。公式1，得到的是以 $0 \sim n-1$ 标注的最终序号；公式2得到的就是正常的 $1 \sim n$ 的序号。下面我们就分别推导两个公式。公式1的推导：给出一个序列，从 $0 \sim n-1$ 编号。其中，$k$ 代表出列的序号的下一个，即 $k-1$ 出列。 $a: 0, 1, \dots, k-1, k, k+1, \dots, n-1$ 那么，出列的序号是 $(m-1)\%n$, $k=m\%n$（这个可真的是显而易见）。出列 $k-1$ 后，序列变为 $b: 0, 1, \dots, k-2, k, k+1, \dots, n-1$ 然后，我们继续从 $n-1$ 后延长这个序列，可以得到 $c': 0, 1, \dots, k-2, k, k+1, \dots, n-1, n, n+1, \dots, n+k-2$ 我们取从 $k$ 开始直到 $n+k-2$ 这段序列。其实这段序列可以看作将序列 $b$ 的 $0 \sim k-2$ 段移到了 $b$ 序列的后面。这样，得到一个新的序列 $c: k, k+1, \dots, n-1, n, n+1, \dots, n+k-2$ 好了，整个序列 $c$ 都减除一个 $k$，得到 $d: 0, 1, \dots, n-2$ $c$ 序列中的 $n-1$, $n$, $n+1$ 都减除个 $k$ 是什么？这个不需要关心，反正 $c$ 序列是连续的，知道了头和尾，就能知道 $d$ 序列是什么样的。

因此，从序列 $a$ 到序列 $d$，就是一个 $n$ 序列到 $n-1$ 序列的变化，约瑟夫环可以通过递推来获得最终结果。剩下的就是根据 $n-1$ 序列递推到 $n$ 序列。假设在 $n-1$ 序列中，也就是序列 $d$ 中，知道了最终剩下的一个序号是 $x$，那么如果知道了 $x$ 转换到序列 $a$ 中的编号 $x’$，不就是知道了最终的结果了么？

下面我们就开始推导出序列 $a$ 中 $x$ 的序号是什么。

$d \to c$，这个变换很容易，就是 $x+k$；
$c \to b$，从 $b \to c$，其实就是 $0 \sim k-2$ 这段序列转换为 $n \sim n+k-2$ 这段序列，那么再翻转回去，简单的就是 $\%n$，即 $(x+k)\%n$。 $\%n$ 以后，$k \sim n-1$ 这段序列值不会发生变化，而 $n \sim n+k-2$ 这段序列则变成了 $0 \sim k-2$；这两段序列合起来，就是序列 $b$。

于是，我们就知道了 $x'=(x+k)\%n$ 并且，$k=m\%n$ 所以 $x'=(x+m\%n)\%n=(x+m)\%n$ 公式1就出来了： $f[i]=(f[i-1]+m)\%i$ 当然，$i=1$ 就是特殊情况了，$f[1]=0$。这里还有一个小问题。也许会迷惑为什么 $x’=(x+m\%n)\%n=(x+m)\%n$ 中的 $\%n$ 变成公式中 $f[i]=(f[i-1]+m)\%i$ 中的 $\%i$ ？其实这个稍微想想就能明了。我们 $\%n$ 就是为了从序列 $c$ 转换到序列 $b$。这是在 $n-1$ 序列转换成 $n$ 序列时 $\%n$；那么从 $n-2$ 转换到 $n-1$ 呢？不是要 $\%(n-1)$ 了吗？所以这个值是变量，不是常量。

好了，这个最后需要注意的就是从一开始，我们将 $n$ 序列从 $0 \sim n-1$ 编号，所以依据公式1得出的序号是基于 $0$ 开始的。

求解出圈序列(线段树)

如果需要输出出圈的序列，常规求解算法为队列的解法，可以用循环队列优化空间，但时间复杂度仍为 $O(m*n)$, 可以采用线段树（排名树）的方法提高效率。通过线段树记录每个区间内还没有出圈的元素的个数，每次通过取模运算求出需要出列的元素从 $1$ 开始的相对位置，再从线段树中找出该元素，并更新线段树。时间复杂度为 $O(n * \log{n})$。参考 wikioi 1282 题，具体实现如下：

#include <cstdio>
using namespace std;

// segment tree.

int sum[120010];

void build(int l, int r, int rt)
{
    if (l == r) {
        sum[rt] = 1;
        return;
    }
    int m = (l+r) >> 1;
    build(l, m, rt << 1);
    build(m+1, r, rt << 1 | 1);
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

void update(int p, int l, int r, int rt)
{
    sum[rt]--;
    if (l == r) {
        printf("%d ", l);
        return;
    }
    int m = (l+r) >> 1;
    if (p <= sum[rt << 1]) {
        update(p, l, m, rt << 1);
    } else {
        update(p-sum[rt<<1], m+1, r, rt << 1 | 1);
    }
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

int main(int argc, char **argv)
{
    int n, m;
    scanf("%d %d", &n, &m);
    build(1, n, 1);
    int seq = 1;
    for (int i = 1; i <= n; ++i) {
        seq = (seq+m-1) % sum[1]; // get the relative postion.
        if (seq == 0) {
            seq = sum[1];
        }
        update(seq, 1, n, 1);
    }

    return 0;
}

参考：

1、http://hi.baidu.com/anywei/item/294351b5f432f144ba0e12f2.

2、http://www.cnblogs.com/EricYang/archive/2009/09/04/1560478.html.

算法原理

求解出圈序列(线段树)

参考：

Comments: