约瑟夫问题及其一种变式

众所周知，约瑟夫环问题可以模拟解决，但本文不打算细讲模拟的方法，只会为了文章完整性起见提一下思路。本文的重点是介绍数学推导过程以及利用树状数组的解法，或者说主要是为了解决下面的变式问题，只是原版约瑟夫的推导过程确有帮助，故一并介绍

约瑟夫问题

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

原题参见LeetCode

原始思路

以上是约瑟夫环问题一种比较经典的描述，思考一下即可以想见两种解法：

• 最容易想到的自然是循环链表直接模拟，删除掉数字即删除链表节点，时间复杂度为$O(mn)$
• 稍稍优化一下思路，用求余的方法，可以直接确定下一个该删除的位置，防止m过大导致空转很多圈的情况，但是时间复杂度仍然为$O(n^2)$

不过既然已经求余，那么不妨思考一下，能否再进一步，直接用数学方法解决这个问题呢？

数学推导

约瑟夫问题每次删除一个人，也即问题的规模每次减小一，这提示我们使用递归的思路去解决这个问题。

然而问题在于，一个规模为$n$的约瑟夫问题中是对$0$~$n-1$进行操作，但是当我们删除一个数字之后，剩余的数字未必是$0$~$n-2$，也就是说，我们要解决的主要是问题规模变小之后的数字编号对应问题。我们需要在规模为$n-1$问题的数字，和规模为$n$的问题的剩余数字之间建立一个一一映射，从而将$n-1$问题的答案转化到$n$问题去。

以上是问题的核心思路，下面介绍详细的推导过程。

不妨假设我们在$0$~$n-1$中第一个删除的数字为$k$，那么为了进行对应，我们先对$0$~$n-1$​进行重排，如下图所示

这相当于把已经删除的数字$k$丢到最后去，不用考虑它，然后按照正常的操作顺序，我们下面应该对$k+1$~$k-1$进行操作。这即是一个规模为$n-1$的问题。我们建立一一映射关系如下图所示

该映射关系作为数学公式的表达如下：

假设$x_n$是上面的数字，$x_{n-1}$是下面的数字，那么有$x_n=(x_{n-1}+(k+1))\ mod\ n$。根据上图，容易验证公式是成立的。

这时候设想一下，如果有了$n-1$规模下的约瑟夫问题的答案$ans_{n-1}$，利用上面的映射关系，不就可以把$ans_{n-1}$映射过去，得到$ans_n$了吗！由于$k$是规模为$n$的问题中第一个删除的数，所以显然应该有$k=(m-1)\ mod\ n$。综合起来整理一下，得到最终的公式：

$$ans_n=(ans_{n-1}+m\ mod\ n)\ mod\ n=(ans_{n-1}+m)\ mod\ n$$

最后考虑一下边界条件，即$n=1$时，显然答案是数字$0$。

至此，我们已经完成了约瑟夫问题的数学公式推导。下面看一下代码实现（代码这么短有啥好看的）：

class Solution {
public:
    // 递归求解的函数
    int solve(int n, int m) {
        if (n == 1) return 0;  // 边界条件
        else return (solve(n - 1, m) + m) % n;  // 公式 
    }
    int lastRemaining(int n, int m) {
        return solve(n, m);
    }
};

也可以直接采用递推的写法：

class Solution {
public:
    int lastRemaining(int n, int m) {
        int ans = 0;
        for (int i = 2; i <= n; i++) {  // i即约瑟夫问题的规模
            ans = (ans + m) % i;
        }
        return ans;
    }
};

有一点值得注意，无论是递推还是递归求解约瑟夫问题，迭代的数字并不代表删除数字的顺序，而是代表着某个规模的约瑟夫问题的答案（比如i=n-2时，求出来的答案并不是倒数第二个被删除的数，而是代表规模为n-2的约瑟夫问题的答案）

如果是一些变种约瑟夫（比如让你求倒数三个被删除的数字），就要注意分清这种概念

树状数组

关于树状数组的写法，放在下面的变种约瑟夫里一起介绍。

线型变向约瑟夫

在这万物复苏的春天，“春樱对决”比赛开始啦！晴明有N个式神，他想从这N个式神里选一个来当这次活动海报的主角。因为想当主角的式神非常多，于是晴明就定下了这样一个选拔的规矩：

将N个式神从左到右排成一排，编号为1~N。从第1个式神开始进行1~M的正向报数，报到的第M个式神出列，再从下一个式神开始继续1到M报数、出列。如果按照某个方向报数到尾部，那么再反方向继续报数。如此进行下去，直到剩下一个式神，而这个式神就是本次“春樱对决”海报的主角。

第一个来到这个寮的两面佛渴望能成为主角，毕竟这是他唯一可能成为主角的时刻了。于是佛佛求你编个程序帮助他实现这个愿望，告诉他要想当主角，他的编号应该是多少。

数据范围：N≤10⁵，M≤10⁹

(ACMOJ · 春樱对决 (sjtu.edu.cn))（没有SJTUOJ账号可能看不见呢）

原始思路

提前声明一下，这个“线型变向约瑟夫”的名字是我乱起的，毕竟本来这个题目背景（阴阳师？）就很奇怪。不过题目大意很清楚了，就是把约瑟夫问题的循环，变成了在一条链上两个方向来回跑。由此，我们仍然可以想到一些朴素解法：

• 用双链表直接模拟，时间复杂度$O(mn)$
• 用循环链表，把除了头尾元素的部分复制一份接到尾的后面，再首尾相接构造循环链表，这样便可以转化成我们熟悉的问题，采用取余的方法，将时间复杂度降低到$O(n^2)$

不过朴素方法仍然不是我们的重点，下面介绍数学方法。

数学推导

我们延续原版约瑟夫的思路，希望能够通过减小问题规模进行递归。

但是这次还有报数方向问题，应该是不能通过很直接的数学公式一行解决了。我们不妨把方向当做每一轮的已知量，加入递归函数传递的变量中，记为$dir$。另外，由于从循环链表变成线性链，每个位置的地位也不再等同，于是我们也传递每轮开始报数的位置，设为$st$。另外，为了求解的方便，我们仍然使用$0$~$n-1$而非原问题中的$1$~$n$。下面开始求解。

记剩余人数为$n$（即前文所述问题规模为$n$）时初始位置为$st_n$，初始方向为$dir_n$（为了叙述的方便，下面将剩余人数为$n$的问题简记为问题$n$）。

我们首先要确定剩余人数为$n-1$时的报数方向$dir_{n-1}$。方向的改变和什么有关呢？自然是和我们跑过了几个转折点（即头尾节点）有关（经过奇数次就转向，偶数次就不转向）。为了方便，我们可以先将$0$~$n-1$进行复制变成一个无限长链便于想象，如下图所示

我们已经将正常的折返等价成了上图的长链，也就是说在上图的链中按一个方向（不妨向右）跑就相当于原题的折返跑。只要落在图中蓝色的部分，原始方向都应该是向右；反之，落在红色部分原始方向就应该向左。

以初始方向向右为例，为了统计的方便，我们不妨将初始位置暂且看作从头（即数字0处）出发，那么跑过的路程就是$s=st_n+(m-1)$，然后我们判断$[\frac{s}{n-1}]=[\frac{st_n+m-1}{n-1}]$（这里[]是高斯函数）的奇偶性，即可知道跑完之后落在红色还是蓝色区域，从而知道方向。

初始方向向左也类似（这时初始$st$应该落在红区），只不过路程$s=(n-1-st_n)+(m-1)$（这里暂且看作出发位置是$n-1$）。

综合一下，有

$$s=\left\{\begin{matrix}st_n+m-1，dir_n=Right\\n-st_n+m-2，dir_n=Left \end{matrix}\right.$$ $$dir_{n-1}=\left\{\begin{matrix}dir_n的反向，[\frac{s}{n-1}]为奇数\\dir_n，[\frac{s}{n-1}]为偶数\end{matrix}\right.$$

有了上面的铺垫，我们接下来求解$st_{n-1}$就比较简单了。

我们先求出从$st_n$出发，移动$m$个之后到达的位置，并记为$k$。仍然看上面的图，如果落在蓝区，那么显然有$k=s\ mod\ (n-1)$；如果落在红区，就是$k=n-1-(s\ mod\ (n-1))$。综合一下，就有

$$k=\left\{\begin{matrix}s\ mod\ (n-1)，dir_{n-1}=Right\\n-1-(s\ mod\ (n-1))，dir_{n-1}=Left \end{matrix}\right.$$

仅仅知道$k$还不够，因为$k$只是问题$n$下的数字编号，而非问题$n-1$下的，所以我们还缺一步。记得吗？原版的约瑟夫中还有一个建立一一映射的过程。当然，由于是单链而非环状，我们不可能再进行重排，但是需要删除的数，即$k$，仍然要舍弃掉，并将剩下的数建立映射关系，如下图所示

假设$x_n$是上面的数字，$x_{n-1}$是下面的数字，那么用数学关系表达就是$x_n=\left\{\begin{matrix} x_{n-1}，x_{n-1}\leq k-1\\ x_{n-1}+1，x_{n-1}\geq k \end{matrix}\right.$

由此，我们便可以通过$k$得到$st_{n-1}$了。如果$dir_{n-1}=Right$，删除数字$k$之后，下一个开始位置是问题$n$中的$k+1$，代入公式得到对应的问题$n-1$中的数字编号为$k$。同理，如果$dir_{n-1}=Left$，删除数字$k$之后，下一个开始位置是问题$n$中的$k-1$，代入公式得到对应的问题$n-1$中的数字编号为$k-1$。

这里不用担心k+1或k-1后会超出0~n的范围，因为头尾位置的方向都是向内的

将这些过程综合一下，就有

$$st_{n-1}=\left\{\begin{matrix}k，dir_{n-1}=Right\\k-1，dir_{n-1}=Left \end{matrix}\right.$$

到这里，我们已经根据$st_n$和$dir_n$求出了$st_{n-1}$和$dir_{n-1}$，即成功地缩小了问题的规模。只要将问题$n-1$的答案映射到问题$n$的数字编号即可，映射公式已经推导过

$$ans_n=\left\{\begin{matrix} ans_{n-1}，ans_{n-1}\leq k-1\\ ans_{n-1}+1，ans_{n-1}\geq k \end{matrix}\right.$$

最后加上同样的边界条件，即$n=1$时，显然答案是数字$0$。

至此，我们完成了这个问题的数学推导。

下面贴出代码（这代码真没啥好看的，写完我自己都看不懂）：

代码仅供参考，请不要盲目抄袭代码来完成作业！！！

#include <iostream>

using namespace std;

// dir=0代表右，dir=1代表左，st是开始报数的人
int solve(int n, int m, int st, int dir) {
    if (n == 1) return 0;
    int k = dir ? (n - 1 - st + m - 1) : (st + m - 1);  // 这里的k是推导过程表述的路程s 
    int ndir = ((k / (n - 1)) & 1) ? (dir ^ 1) : dir;  // s / (n-1) 是奇数就反向
    k = (ndir ? (n - 1 - k % (n - 1)) : k % (n - 1));  // 这里的k即推导过程的k
    int nst = ndir ? k - 1 : k;  // 求出st_n-1
    int ret = solve(n - 1, m, nst, ndir);  // n-1问题的答案
    return (ret >= k) ? ret + 1 : ret;  // 进行映射
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    printf("%d", solve(n, m, 0, 0) + 1);
    return 0;
}

树状数组

有时间补上`(*>﹏<*)′

受笔者知识水平和表达能力所限，有的问题难免解释得或啰嗦或不清楚，欢迎在评论区指正