1. 约瑟夫问题到底在问什么题面、样例与第一印象P1996这道题洛谷上标注的是“约瑟夫问题”题目描述极其简单n个人围成一圈从第1个人开始报数报数到m的人出圈然后下一个人重新从1开始报数问出圈顺序。n和m给定输出依次出圈的人的编号。我第一次看到这个题的时候第一反应是“就这”——毕竟n的范围只有100暴力模拟怎么也能过去。但真正把这题吃透之后我发现这题其实是算法竞赛里递推思想的一个非常经典的入口后面的约瑟夫环变体、数据范围扩大后的处理、以及从“模拟暴力”到“数学优化”的思维转变全都能从这道题延展出去。先看一眼经典样例n10m3时出圈顺序是3 6 9 2 7 1 8 5 10 4。如果你手动模拟一遍会发现在最后几轮圈子里只剩两个人时报数过程依然要按循环来处理这里稍不留神就容易算错。所以第一步我们先把这题的所有细节确认清楚再讨论算法。这题的定位在洛谷的题目列表里属于“入门/普及-”但很多初学者在第一次写这题的时候会非常自然地采用数组模拟然后发现n很小所以能过但稍微改一下数据范围就彻底不行了。所以这题真正的价值不在于“过题”而在于让你明白为什么看起来一样的两种写法复杂度会差一个量级递推是怎么把O(n*m)压成O(n)的这个问题搞清楚了往后你遇到约瑟夫环的各种变体都不会慌。1.1 题面细节与输出要求题目输入是n和m然后要求按出圈顺序输出编号每个编号后面跟一个空格部分版本要求换行洛谷P1996是每个数字后跟一个空格末尾可以有换行实测PE不算错。这里要注意的一点是“从第1个人开始报数报到m的人出圈”这个逻辑第一轮从编号1报数喊到“1”的是1号喊到“2”的是2号……所以如果m3第一个出圈的就是3号不是2号也不是1号这点新手经常搞混。另外值得注意的一个细节是报数的动作是从1开始的。这意味着如果你用下标i表示当前位置那么“从当前位置开始数第m个人”这个动作在代码里等价于i (i m - 1) % 当前人数假设i从0开始。这个“-1”的偏移量是整个模拟代码最容易出错的地方后面我会专门讲。1.2 样例推导手算一遍确认理解我们用n10, m3来手动过一遍确保后面代码的行为一致初始序列1 2 3 4 5 6 7 8 9 10第一轮从1开始报数1、2、33号出圈。序列变为1 2 4 5 6 7 8 9 10。下一轮从4号开始报数。第二轮从4号开始4、5、66号出圈。序列变为1 2 4 5 7 8 9 10。下一轮从7号开始。第三轮7、8、99号出圈。序列变为1 2 4 5 7 8 10。下一轮从10号开始。第四轮10、1、22号出圈。序列变为1 4 5 7 8 10。下一轮从4号开始。第五轮4、5、77号出圈。序列变为1 4 5 8 10。下一轮从8号开始。第六轮8、10、11号出圈。序列变为4 5 8 10。下一轮从4号开始。第七轮4、5、88号出圈。序列变为4 5 10。下一轮从10号开始。第八轮10、4、55号出圈。序列变为4 10。下一轮从4号开始。第九轮4、10、44号出圈。剩下10号。最后一轮只剩10号直接出圈。所以完整出圈顺序是3 6 9 2 7 1 8 5 10 4和样例输出一致。手动过一遍之后你对后续的代码行为和递推公式的边界条件就会有比较清晰的认知。2. 第一次尝试数组模拟直接翻译题意的暴力思路绝大多数人第一次写这题脑子里就是“按照题意模拟一个圈”。最简单的实现方式就是用数组或者vector找到出圈者就删掉然后继续。这种做法写起来非常符合直觉而且对于n100的数据范围完全够用洛谷P1996用这种方法可以直接AC。2.1 用vector实现的模拟代码先看我最初写的版本用C的vector直接模拟删除#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; vectorint people; for (int i 1; i n; i) people.push_back(i); int idx 0; // 从0号位置开始也就是编号1 while (!people.empty()) { idx (idx m - 1) % people.size(); cout people[idx] ; people.erase(people.begin() idx); // 删除后people[idx]已经是下一个人的位置不需要idx } return 0; }这段代码的核心逻辑非常直白idx表示当前“从谁开始报数”的位置初始是0也就是编号1。要找到出圈者需要从当前位置向后数m个人但因为当前位置的人也会被计数他报的是1所以偏移量是m-1。找到后输出并删除删除后vector会自动把后面的元素往前挪恰好此时people[idx]就是下一轮第一个报数的人所以不需要额外调整idx。这里最关键的是idx (idx m - 1) % people.size()这句。很多人第一次会写成(idx m) % size那样就相当于从当前位置的下一个人开始报数第一个出圈的人就变成了m1号而不是m号整体答案会全部错位。2.2 另一种模拟固定数组标记法除了vector删除法还有一种用固定数组记录的写法我后来也用过先初始化一个数组值为对应的编号用变量alive记录剩余人数每次找到出圈者之后把该位置标记为0下次跳过。这种数组标记法跟vector删除法本质一样只是不需要移动元素因此省去了erase的开销实际上比vector更稳定。但需要额外处理“跳过已经出圈的人”的逻辑代码会稍微长一点。#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; vectorint a(n 1); for (int i 1; i n; i) a[i] i; int alive n; int pos 0; while (alive) { int step m % alive; if (step 0) step alive; // 从pos向后走step步遇到已经出圈的跳过 while (step--) { pos; if (pos n) pos 1; while (a[pos] 0) { pos; if (pos n) pos 1; } } cout a[pos] ; a[pos] 0; alive--; } return 0; }这种写法在n100时同样轻松通过而且逻辑上更像是“在纸上手动模拟”的翻版。不过注意step m % alive的写法当m正好是alive的倍数时等价于要数循环一圈回到起点此时出圈者就是当前位置的人所以step要设置为alive而不是0。这段逻辑是数组标记法最容易出错的地方。2.3 模拟代码的边界情况与第一轮偏移上面两种模拟方案都要时刻注意“当前位置”和“出圈者位置”之间的关系。我用一个表格把容易出错的点列出来情况正确写法错误写法错误后果从0号位置开始数m个人idx (idx m - 1) % sizeidx (idx m) % size第一个出圈者是m1号m大于当前人数取模运算自动处理不取模数组越界或逻辑错乱删除后继续进行下一轮不需要调整idx手动idx跳过一个元素导致出圈顺序错乱我个人在实际写模拟的时候最惨痛的一次教训就是用vector的erase之后顺手写了idx结果出圈序列从中间开始就全部错了排查了很久才发现是删除后的指针偏移问题。后来我总结了一条经验用erase删除当前元素后迭代器或索引已经自动指向了删除位置的下一个元素这时候如果再手动加一就会跳过一个元素。3. 模拟的瓶颈在哪里复杂度分析为什么n1e5时暴力就卡死了P1996的n只有100所以直接用模拟没有任何问题。但如果你把数据范围改到n1e5或者更大vector删除法和数组标记法就都会面临严重的性能瓶颈。理解这个瓶颈在哪里是理解后续递推开挂式优化的前提。3.1 两种模拟的时间复杂度对比先看vector删除法。vector的erase操作在删除中间元素时会把后面的所有元素向前挪一位总代价是O(size)。每一轮都要查找一次O(1)定位加删除一次O(size)挪动而一共有n轮所以总时间复杂度是O(n²)。n100时这个量级完全无所谓但n1e5时1e10量级的操作在现代机器上需要几十秒才能跑完显然不能接受。数组标记法的erase是通过标记0来模拟删除省去了元素挪动的开销但每一轮查找出圈者的过程中都要跳过已出圈的0标记最坏情况下每轮需要遍历整个数组时间复杂度依然是O(n²)。n1e5时同样会超时。所以核心结论是当n比较小几百以内时暴力模拟是最简单、最不容易出错的方案但当n达到几千甚至更大时你必须放弃“跟着题意逐轮模拟”的思路改用数学方法。3.2 循环链表的改进以及它的适用边界有人会想到用循环链表来优化删除操作链表删除一个节点只需要O(1)的时间不需要挪动元素。这样总复杂度就是O(nm)——每一轮从当前位置数出m个节点然后删除一共n轮。这个方案比O(n²)的数组模拟好很多尤其是当m比较小时O(nm)可以逼近O(n)。但循环链表版本的缺点也很明显一是实现循环链表相对麻烦要自己维护节点结构、删除逻辑代码量比数组模拟大不少二是当m很大时比如m和n同量级每一轮走m步会带来很大的常数复杂度依然不理想。所以在实际写题时循环链表更多被用来“跑数据范围中等且m较小”的情况而不是通用方案。3.3 模拟是否真的没有价值理解暴力思路的意义不论如何我依然建议每个学这道题的人都先把模拟版本写一遍、跑通一遍。理由有三个。第一模拟是递推公式正确性的“对照实验”你推导的递推结果到底对不对拿模拟的输出一对便知这是调试期最重要的验证手段。第二模拟帮你建立对“报数机制”的直觉从第一个人开始数m个人后出圈这个动作在后续所有变体中都会反复出现你对这个动作的偏移量理解得越透彻写数学解法时就越不容易搞错下标。第三模拟在某些变体中依然是最方便的解法比如题目要求输出前k个出圈者的编号而k很小此时模拟的复杂度是O(k*n)完全可以接受。这些事情只看递推公式是体会不到的。4. 从最后一轮反向递推约瑟夫问题的数学核心这一节是整篇博文的重点。约瑟夫问题最漂亮的解法是不模拟整个出圈过程而是反过来想最后剩下的那个人在每轮结束时的“编号位置”是多少然后从n1的情况一路反推回n个人的情况得到一个非常简洁的递推公式。4.1 单人情况的答案递推的起点先考虑最简单的情况只有1个人的时候无论m是多少最后剩下的人当然是0号或者1号取决于你的编号起点。在经典的0-indexed递推中我们定义f(1) 0表示只有1个人时幸存者的索引是0。然后考虑2个人的情况。从1号开始报数报到m的人出圈如果m是奇数出圈的是1号剩下0号如果m是偶数出圈的是0号剩下1号。根据这个规律直接推是一个非常麻烦的case-by-case分析。我们需要一个更系统的方式。4.2 反推一轮把“出圈后”的状态对应到“出圈前”的状态关键在于理解当第一个人出圈后剩下n-1个人组成的新圈子和原来的n人圈子之间存在一个“平移”关系。假设当前有n个人编号为0到n-1暂时用0开头最后统一加1。报数的起始位置是0号。第一个出圈的人的下标是(m - 1) % n。这个人出圈之后下一轮报数的起始位置是m % n也就是出圈者后面的那一位。现在我们把剩下的n-1个人“重新编号”为0到n-2以便和“n-1个人的约瑟夫问题”建立对应关系。设i是某个人在原来n人圈子中的下标j是他在新圈子中的下标那么这两者满足j (i - m) % n为什么要减m因为新圈子的起点比原圈子的起点向后平移了m位。反过来就有i (j m) % n这个反向关系是整个递推公式的核心如果我知道了在n-1个人的问题中幸存者是谁它的新下标是f(n-1)那么把下标映射回n个人的圈子幸存者的原下标就是(f(n-1) m) % n。由此得到递推式f(n) (f(n-1) m) % n其中f(1) 0。4.3 递推公式的完整推导以及一个关键的理解误区很多文章直接这一步就把公式扔出来然后让你背。但这样很容易产生一个误区觉得这个f(n)是“n个人时的幸存者编号”。这其实不够准确。更准确的说法是f(n)表示的是在“n个人参与游戏且编号从0开始从0开始报数”的前提下最后幸存者的下标。这个下标并不是简单的“编号1到n”而是经过每轮“重新编号”后层层映射回来的结果。为了彻底理解这个公式我建议你手动跑一遍n5、m3的例子。f(1) 0 1个人时幸存者下标是0f(2) (f(1) 3) % 2 1f(3) (f(2) 3) % 3 (1 3) % 3 1f(4) (f(3) 3) % 4 (1 3) % 4 0f(5) (f(4) 3) % 5 (0 3) % 5 3所以5个人、报数到3时幸存者的下标是3也就是编号4。你可以用模拟验证一下这个结果是否正确。这个递推公式把原本O(n*m)的模拟过程压缩成了O(n)的简单循环这是质的飞跃。整个推导过程虽然只有三行但背后的“每次删人后重新编号再把答案映回原编号”的思想在很多组合数学问题中都会用到。4.4 为什么公式里要取模n而不是别的以及对0-indexed的解释取模的对象是“当前这一轮还活着的人数”。因为圈子是循环的下标在[0, 人数-1]之间循环所以必须对当前人数取模。这个n在递推过程中是变化的从2一直变到目标值n每一轮都要用对应的当前人数取模。另一个值得解释的点是为什么递推中的编号要从0开始而不是1因为取模运算%在C中对非负整数返回的结果在[0, mod-1]之间如果从1开始编号取模结果会是[1, mod]那么在递推过程中你还要额外处理边界比如(f(n-1) m) % n得到0时需要换成n非常容易出错。所以行业惯例是先在0-indexed的世界里推导和计算最后统一加1输出。这一点我强烈建议你直接沿用别自己在1-indexed上硬搞我见过太多人在这个偏移上绕晕的。5. 递推写法在P1996上的实现与边界处理有了递推公式接下来就是把它落到代码上。但P1996和“只求最后幸存者”的经典约瑟夫问题有一个重要区别这道题要输出的是完整的出圈顺序而不是最后一个幸存者。这导致递推公式不能直接用来逐个输出出圈者必须换一种策略。5.1 为什么递推公式无法直接输出出圈顺序如果你已经理解了递推公式的推导过程会发现它本质上是在“倒推幸存者”从1个人时的幸存者下标一路映射回n个人时的幸存者下标。这个映射只能得到最后一个幸存者中间过程的出圈者并不参与幸存者下标的计算。所以如果你用f(n) (f(n-1) m) % n直接循环一遍最后只会得到最后一个出圈者的编号前面所有出圈者的编号都拿不到。那洛谷P1996到底应该用什么算法如果你愿意完全可以用暴力模拟直接AC因为n只有100。但如果你想练手递推方法可以考虑另一种做法用递推推导每次“当前圈子中将要出圈的人的下标”然后根据当前圈子的大小计算并输出其真实编号。5.2 用递推思想输出完整出圈顺序的参考代码这里提供一个我实际写过的方案反过来从n个人推到1个人是幸存者但我们也可以正向用递推的“反向映射”来逐轮输出。思路是假设当前有i个人已知在这i个人中出圈者的下标是(m-1) % i因为从0号开始报数数m个人出圈者下标就是m-1模i。输出这个下标对应的真实编号后把这个人从圈子里删掉。删掉之后剩下i-1个人重新组成圈子且下一轮报数的起点变成了当前出圈者的后一位。我们只需要维护一个“本轮起始下标”变量让它正确随着每次删除更新。实际上更直观的方法是这样做维护一个变量start表示当前轮第一个报数的人在当前圈子中的位置0-indexed然后每次找到出圈位置out (start m - 1) % size。输出前需要把这个位置映射回原始编号这要求我们用一数据结构比如vector来保存当前圈子中每个位置对应的原编号。这样写下来你会发现本质上还是一个模拟只是下标计算使用了递推式的偏移逻辑。#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; vectorint circle(n); iota(circle.begin(), circle.end(), 1); // 生成1~n int start 0; while (!circle.empty()) { int out (start m - 1) % circle.size(); cout circle[out] ; circle.erase(circle.begin() out); start out; // 删除后circle[out]就是下一轮第一个报数的人 if (!circle.empty()) start % circle.size(); } return 0; }这个代码和前面暴力模拟的vector版本在本质上几乎一样区别在于显式维护了start变量逻辑更清晰。那道题的AC代码我用它提交耗时0ms内存几百KB。5.3 如果只要求输出最后一个幸存者直接套递推如果你碰到的题目只要求输出最后剩下来的人比如经典的“约瑟夫环”问题那就不需要vector了直接用递推公式就够了代码只有几行#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; int ans 0; // f(1) for (int i 2; i n; i) { ans (ans m) % i; } cout ans 1 endl; // 转回1-indexed return 0; }这里循环从i2到n每次用当前人数i取模。最终ans是0-indexed的幸存者下标加1才是真实编号。这段代码在n高达几百万、甚至几千万时依然可以飞快运行因为循环内部只做一次加法和一次取模几乎没有常数之外的额外开销。5.4 递推解法中容易踩的边界坑我自己在写递推解法时踩过的两个坑这里单独拎出来说一下。第一个坑是起始下标ans 0对应f(1)如果你从ans 1开始整个递推就全部错位最后输出会整体偏移1。第二个坑是取模对象有人在循环里写(ans m) % n把取模对象固定成了n这是错的。每一轮人数在变化取模对象必须是当前i而不是总人数n。举例来说n10、m100时m远大于当前人数不取模绝对越界但即使是mn这个固定n的错误也会在后期产生偏差。6. P1996之外的延伸思考数据范围变大、变体问题与学习建议P1996本身只是一道入门题但约瑟夫环这个模型在实际中有一堆变体数据范围扩大、m每次变化、要求输出前k个出圈者、双向约瑟夫、环形链表上的动态维护等等。真正把这题的两种思路模拟与递推都理解了你才能在面对这些变体时快速判断该用什么方案。6.1 数据范围扩大后的进阶方案如果n和m都达到1e5级别且必须输出完整出圈顺序这时候纯粹的模拟就不太可行了O(n²)级别但递推公式又只能输出幸存者。业界常用的方案是用树状数组或线段树来模拟“删除”过程通过区间求和找到当前存活的人中第k个人的位置每次删除复杂度O(log n)总复杂度O(n log n)。线段树的具体做法是建一棵维护区间“存活人数”的线段树叶子值为1表示该位置还有人0表示已经出圈。每次要删除时计算当前出圈位置在“存活序列”中的排名然后在线段树上二分找到第k个存活者的位置输出并把该位置设为0。这个做法本质上还是“模拟每一轮删除”只是把“找第k个人”和“删除”两步都变成了O(log n)。如果n到2e5这个方案是标准解。6.2 约瑟夫问题变体的几个方向我自己在刷题中遇到的变体主要有三种都是基于这道题延展开的第一种是“m很大”的情况。比如n100但m1e9这时候你不可能模拟m步但可以观察到报数过程会多轮循环每轮完整遍历一圈相当于抵消m % n的步数。利用这种取模压缩可以把每次找人的复杂度从O(m)降至O(1)整个模拟过程就是O(n)。这个优化在n很小、m极大时非常有用。第二种是“m动态变化”。有些题目中每个人出圈后会导致m按某种规则变化比如变成当前出圈者的编号的某种函数这时候递推公式没法用因为公式的前提是m恒定。只能回到模拟但可以用“二叉搜索树/平衡树”维护存活序列从而在O(log n)内完成每次删除。第三种是“要求第k个幸存者”。经典的递推只能求最后一个幸存者但如果你想知道第k轮出圈的人是谁一种办法是把递推过程倒过来先计算最后一轮幸存者然后逐步回溯出每轮的“位置编号”。具体做法是从n个人推到1个人的过程中记录每次ans的中间值然后从n个人的角度重新走一遍找到某个时刻的幸存者下标。这个思路比较绕但写出来也能做到O(n)。6.3 就这道题我的实操心得和学习建议最后分享一点自己的经验。P1996这道题最简单的是AC最难的是“真正理解递推”。如果你只是把模拟代码背下来过了题那你在这道题上几乎没有收获。我建议按这个顺序折腾一遍先用vector模拟写一版然后用数组标记法写一版对比两种实现的时间和代码复杂度接着手动推导一遍递推公式的映射关系再用递推代码写一版“只输出幸存者”的程序跟模拟结果对拍最后把n和m改成大数实测一下两种写法的性能差距。对拍是刷算法题最实用的习惯。把暴力和优化版本写到同一个文件中生成大量随机小数据通过system(fc /c)或直接写一个循环比对输出能帮你快速发现推导错误。我当年做这道题时就是靠对拍找到自己在递推中取模对象错误的n1时边界不对我一开始用的基础版本f(1)1是靠对拍抓出来的。关于“报数偏移”的理解我再多啰嗦一句这个-1的偏移贯穿整个约瑟夫问题的各种解法。你在写任何约瑟夫变体的代码之前先用n5、m3、手动模拟一遍出圈顺序再对照代码这个偏差就永远不会困扰你了。这道题的后续扩展空间很大。等你把基础版本吃透之后可以试试洛谷的其他变体题目比如数据范围更大或者带输出的约瑟夫问题你会发现自己对“递推 数据结构”的双重视角越来越熟练。算法学习就是这样一道看似简单的题只要你愿意往下钻能挖出来的东西远比题面看起来要多。
约瑟夫问题P1996全解析：从模拟递推到数据结构优化
1. 约瑟夫问题到底在问什么题面、样例与第一印象P1996这道题洛谷上标注的是“约瑟夫问题”题目描述极其简单n个人围成一圈从第1个人开始报数报数到m的人出圈然后下一个人重新从1开始报数问出圈顺序。n和m给定输出依次出圈的人的编号。我第一次看到这个题的时候第一反应是“就这”——毕竟n的范围只有100暴力模拟怎么也能过去。但真正把这题吃透之后我发现这题其实是算法竞赛里递推思想的一个非常经典的入口后面的约瑟夫环变体、数据范围扩大后的处理、以及从“模拟暴力”到“数学优化”的思维转变全都能从这道题延展出去。先看一眼经典样例n10m3时出圈顺序是3 6 9 2 7 1 8 5 10 4。如果你手动模拟一遍会发现在最后几轮圈子里只剩两个人时报数过程依然要按循环来处理这里稍不留神就容易算错。所以第一步我们先把这题的所有细节确认清楚再讨论算法。这题的定位在洛谷的题目列表里属于“入门/普及-”但很多初学者在第一次写这题的时候会非常自然地采用数组模拟然后发现n很小所以能过但稍微改一下数据范围就彻底不行了。所以这题真正的价值不在于“过题”而在于让你明白为什么看起来一样的两种写法复杂度会差一个量级递推是怎么把O(n*m)压成O(n)的这个问题搞清楚了往后你遇到约瑟夫环的各种变体都不会慌。1.1 题面细节与输出要求题目输入是n和m然后要求按出圈顺序输出编号每个编号后面跟一个空格部分版本要求换行洛谷P1996是每个数字后跟一个空格末尾可以有换行实测PE不算错。这里要注意的一点是“从第1个人开始报数报到m的人出圈”这个逻辑第一轮从编号1报数喊到“1”的是1号喊到“2”的是2号……所以如果m3第一个出圈的就是3号不是2号也不是1号这点新手经常搞混。另外值得注意的一个细节是报数的动作是从1开始的。这意味着如果你用下标i表示当前位置那么“从当前位置开始数第m个人”这个动作在代码里等价于i (i m - 1) % 当前人数假设i从0开始。这个“-1”的偏移量是整个模拟代码最容易出错的地方后面我会专门讲。1.2 样例推导手算一遍确认理解我们用n10, m3来手动过一遍确保后面代码的行为一致初始序列1 2 3 4 5 6 7 8 9 10第一轮从1开始报数1、2、33号出圈。序列变为1 2 4 5 6 7 8 9 10。下一轮从4号开始报数。第二轮从4号开始4、5、66号出圈。序列变为1 2 4 5 7 8 9 10。下一轮从7号开始。第三轮7、8、99号出圈。序列变为1 2 4 5 7 8 10。下一轮从10号开始。第四轮10、1、22号出圈。序列变为1 4 5 7 8 10。下一轮从4号开始。第五轮4、5、77号出圈。序列变为1 4 5 8 10。下一轮从8号开始。第六轮8、10、11号出圈。序列变为4 5 8 10。下一轮从4号开始。第七轮4、5、88号出圈。序列变为4 5 10。下一轮从10号开始。第八轮10、4、55号出圈。序列变为4 10。下一轮从4号开始。第九轮4、10、44号出圈。剩下10号。最后一轮只剩10号直接出圈。所以完整出圈顺序是3 6 9 2 7 1 8 5 10 4和样例输出一致。手动过一遍之后你对后续的代码行为和递推公式的边界条件就会有比较清晰的认知。2. 第一次尝试数组模拟直接翻译题意的暴力思路绝大多数人第一次写这题脑子里就是“按照题意模拟一个圈”。最简单的实现方式就是用数组或者vector找到出圈者就删掉然后继续。这种做法写起来非常符合直觉而且对于n100的数据范围完全够用洛谷P1996用这种方法可以直接AC。2.1 用vector实现的模拟代码先看我最初写的版本用C的vector直接模拟删除#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; vectorint people; for (int i 1; i n; i) people.push_back(i); int idx 0; // 从0号位置开始也就是编号1 while (!people.empty()) { idx (idx m - 1) % people.size(); cout people[idx] ; people.erase(people.begin() idx); // 删除后people[idx]已经是下一个人的位置不需要idx } return 0; }这段代码的核心逻辑非常直白idx表示当前“从谁开始报数”的位置初始是0也就是编号1。要找到出圈者需要从当前位置向后数m个人但因为当前位置的人也会被计数他报的是1所以偏移量是m-1。找到后输出并删除删除后vector会自动把后面的元素往前挪恰好此时people[idx]就是下一轮第一个报数的人所以不需要额外调整idx。这里最关键的是idx (idx m - 1) % people.size()这句。很多人第一次会写成(idx m) % size那样就相当于从当前位置的下一个人开始报数第一个出圈的人就变成了m1号而不是m号整体答案会全部错位。2.2 另一种模拟固定数组标记法除了vector删除法还有一种用固定数组记录的写法我后来也用过先初始化一个数组值为对应的编号用变量alive记录剩余人数每次找到出圈者之后把该位置标记为0下次跳过。这种数组标记法跟vector删除法本质一样只是不需要移动元素因此省去了erase的开销实际上比vector更稳定。但需要额外处理“跳过已经出圈的人”的逻辑代码会稍微长一点。#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; vectorint a(n 1); for (int i 1; i n; i) a[i] i; int alive n; int pos 0; while (alive) { int step m % alive; if (step 0) step alive; // 从pos向后走step步遇到已经出圈的跳过 while (step--) { pos; if (pos n) pos 1; while (a[pos] 0) { pos; if (pos n) pos 1; } } cout a[pos] ; a[pos] 0; alive--; } return 0; }这种写法在n100时同样轻松通过而且逻辑上更像是“在纸上手动模拟”的翻版。不过注意step m % alive的写法当m正好是alive的倍数时等价于要数循环一圈回到起点此时出圈者就是当前位置的人所以step要设置为alive而不是0。这段逻辑是数组标记法最容易出错的地方。2.3 模拟代码的边界情况与第一轮偏移上面两种模拟方案都要时刻注意“当前位置”和“出圈者位置”之间的关系。我用一个表格把容易出错的点列出来情况正确写法错误写法错误后果从0号位置开始数m个人idx (idx m - 1) % sizeidx (idx m) % size第一个出圈者是m1号m大于当前人数取模运算自动处理不取模数组越界或逻辑错乱删除后继续进行下一轮不需要调整idx手动idx跳过一个元素导致出圈顺序错乱我个人在实际写模拟的时候最惨痛的一次教训就是用vector的erase之后顺手写了idx结果出圈序列从中间开始就全部错了排查了很久才发现是删除后的指针偏移问题。后来我总结了一条经验用erase删除当前元素后迭代器或索引已经自动指向了删除位置的下一个元素这时候如果再手动加一就会跳过一个元素。3. 模拟的瓶颈在哪里复杂度分析为什么n1e5时暴力就卡死了P1996的n只有100所以直接用模拟没有任何问题。但如果你把数据范围改到n1e5或者更大vector删除法和数组标记法就都会面临严重的性能瓶颈。理解这个瓶颈在哪里是理解后续递推开挂式优化的前提。3.1 两种模拟的时间复杂度对比先看vector删除法。vector的erase操作在删除中间元素时会把后面的所有元素向前挪一位总代价是O(size)。每一轮都要查找一次O(1)定位加删除一次O(size)挪动而一共有n轮所以总时间复杂度是O(n²)。n100时这个量级完全无所谓但n1e5时1e10量级的操作在现代机器上需要几十秒才能跑完显然不能接受。数组标记法的erase是通过标记0来模拟删除省去了元素挪动的开销但每一轮查找出圈者的过程中都要跳过已出圈的0标记最坏情况下每轮需要遍历整个数组时间复杂度依然是O(n²)。n1e5时同样会超时。所以核心结论是当n比较小几百以内时暴力模拟是最简单、最不容易出错的方案但当n达到几千甚至更大时你必须放弃“跟着题意逐轮模拟”的思路改用数学方法。3.2 循环链表的改进以及它的适用边界有人会想到用循环链表来优化删除操作链表删除一个节点只需要O(1)的时间不需要挪动元素。这样总复杂度就是O(nm)——每一轮从当前位置数出m个节点然后删除一共n轮。这个方案比O(n²)的数组模拟好很多尤其是当m比较小时O(nm)可以逼近O(n)。但循环链表版本的缺点也很明显一是实现循环链表相对麻烦要自己维护节点结构、删除逻辑代码量比数组模拟大不少二是当m很大时比如m和n同量级每一轮走m步会带来很大的常数复杂度依然不理想。所以在实际写题时循环链表更多被用来“跑数据范围中等且m较小”的情况而不是通用方案。3.3 模拟是否真的没有价值理解暴力思路的意义不论如何我依然建议每个学这道题的人都先把模拟版本写一遍、跑通一遍。理由有三个。第一模拟是递推公式正确性的“对照实验”你推导的递推结果到底对不对拿模拟的输出一对便知这是调试期最重要的验证手段。第二模拟帮你建立对“报数机制”的直觉从第一个人开始数m个人后出圈这个动作在后续所有变体中都会反复出现你对这个动作的偏移量理解得越透彻写数学解法时就越不容易搞错下标。第三模拟在某些变体中依然是最方便的解法比如题目要求输出前k个出圈者的编号而k很小此时模拟的复杂度是O(k*n)完全可以接受。这些事情只看递推公式是体会不到的。4. 从最后一轮反向递推约瑟夫问题的数学核心这一节是整篇博文的重点。约瑟夫问题最漂亮的解法是不模拟整个出圈过程而是反过来想最后剩下的那个人在每轮结束时的“编号位置”是多少然后从n1的情况一路反推回n个人的情况得到一个非常简洁的递推公式。4.1 单人情况的答案递推的起点先考虑最简单的情况只有1个人的时候无论m是多少最后剩下的人当然是0号或者1号取决于你的编号起点。在经典的0-indexed递推中我们定义f(1) 0表示只有1个人时幸存者的索引是0。然后考虑2个人的情况。从1号开始报数报到m的人出圈如果m是奇数出圈的是1号剩下0号如果m是偶数出圈的是0号剩下1号。根据这个规律直接推是一个非常麻烦的case-by-case分析。我们需要一个更系统的方式。4.2 反推一轮把“出圈后”的状态对应到“出圈前”的状态关键在于理解当第一个人出圈后剩下n-1个人组成的新圈子和原来的n人圈子之间存在一个“平移”关系。假设当前有n个人编号为0到n-1暂时用0开头最后统一加1。报数的起始位置是0号。第一个出圈的人的下标是(m - 1) % n。这个人出圈之后下一轮报数的起始位置是m % n也就是出圈者后面的那一位。现在我们把剩下的n-1个人“重新编号”为0到n-2以便和“n-1个人的约瑟夫问题”建立对应关系。设i是某个人在原来n人圈子中的下标j是他在新圈子中的下标那么这两者满足j (i - m) % n为什么要减m因为新圈子的起点比原圈子的起点向后平移了m位。反过来就有i (j m) % n这个反向关系是整个递推公式的核心如果我知道了在n-1个人的问题中幸存者是谁它的新下标是f(n-1)那么把下标映射回n个人的圈子幸存者的原下标就是(f(n-1) m) % n。由此得到递推式f(n) (f(n-1) m) % n其中f(1) 0。4.3 递推公式的完整推导以及一个关键的理解误区很多文章直接这一步就把公式扔出来然后让你背。但这样很容易产生一个误区觉得这个f(n)是“n个人时的幸存者编号”。这其实不够准确。更准确的说法是f(n)表示的是在“n个人参与游戏且编号从0开始从0开始报数”的前提下最后幸存者的下标。这个下标并不是简单的“编号1到n”而是经过每轮“重新编号”后层层映射回来的结果。为了彻底理解这个公式我建议你手动跑一遍n5、m3的例子。f(1) 0 1个人时幸存者下标是0f(2) (f(1) 3) % 2 1f(3) (f(2) 3) % 3 (1 3) % 3 1f(4) (f(3) 3) % 4 (1 3) % 4 0f(5) (f(4) 3) % 5 (0 3) % 5 3所以5个人、报数到3时幸存者的下标是3也就是编号4。你可以用模拟验证一下这个结果是否正确。这个递推公式把原本O(n*m)的模拟过程压缩成了O(n)的简单循环这是质的飞跃。整个推导过程虽然只有三行但背后的“每次删人后重新编号再把答案映回原编号”的思想在很多组合数学问题中都会用到。4.4 为什么公式里要取模n而不是别的以及对0-indexed的解释取模的对象是“当前这一轮还活着的人数”。因为圈子是循环的下标在[0, 人数-1]之间循环所以必须对当前人数取模。这个n在递推过程中是变化的从2一直变到目标值n每一轮都要用对应的当前人数取模。另一个值得解释的点是为什么递推中的编号要从0开始而不是1因为取模运算%在C中对非负整数返回的结果在[0, mod-1]之间如果从1开始编号取模结果会是[1, mod]那么在递推过程中你还要额外处理边界比如(f(n-1) m) % n得到0时需要换成n非常容易出错。所以行业惯例是先在0-indexed的世界里推导和计算最后统一加1输出。这一点我强烈建议你直接沿用别自己在1-indexed上硬搞我见过太多人在这个偏移上绕晕的。5. 递推写法在P1996上的实现与边界处理有了递推公式接下来就是把它落到代码上。但P1996和“只求最后幸存者”的经典约瑟夫问题有一个重要区别这道题要输出的是完整的出圈顺序而不是最后一个幸存者。这导致递推公式不能直接用来逐个输出出圈者必须换一种策略。5.1 为什么递推公式无法直接输出出圈顺序如果你已经理解了递推公式的推导过程会发现它本质上是在“倒推幸存者”从1个人时的幸存者下标一路映射回n个人时的幸存者下标。这个映射只能得到最后一个幸存者中间过程的出圈者并不参与幸存者下标的计算。所以如果你用f(n) (f(n-1) m) % n直接循环一遍最后只会得到最后一个出圈者的编号前面所有出圈者的编号都拿不到。那洛谷P1996到底应该用什么算法如果你愿意完全可以用暴力模拟直接AC因为n只有100。但如果你想练手递推方法可以考虑另一种做法用递推推导每次“当前圈子中将要出圈的人的下标”然后根据当前圈子的大小计算并输出其真实编号。5.2 用递推思想输出完整出圈顺序的参考代码这里提供一个我实际写过的方案反过来从n个人推到1个人是幸存者但我们也可以正向用递推的“反向映射”来逐轮输出。思路是假设当前有i个人已知在这i个人中出圈者的下标是(m-1) % i因为从0号开始报数数m个人出圈者下标就是m-1模i。输出这个下标对应的真实编号后把这个人从圈子里删掉。删掉之后剩下i-1个人重新组成圈子且下一轮报数的起点变成了当前出圈者的后一位。我们只需要维护一个“本轮起始下标”变量让它正确随着每次删除更新。实际上更直观的方法是这样做维护一个变量start表示当前轮第一个报数的人在当前圈子中的位置0-indexed然后每次找到出圈位置out (start m - 1) % size。输出前需要把这个位置映射回原始编号这要求我们用一数据结构比如vector来保存当前圈子中每个位置对应的原编号。这样写下来你会发现本质上还是一个模拟只是下标计算使用了递推式的偏移逻辑。#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; vectorint circle(n); iota(circle.begin(), circle.end(), 1); // 生成1~n int start 0; while (!circle.empty()) { int out (start m - 1) % circle.size(); cout circle[out] ; circle.erase(circle.begin() out); start out; // 删除后circle[out]就是下一轮第一个报数的人 if (!circle.empty()) start % circle.size(); } return 0; }这个代码和前面暴力模拟的vector版本在本质上几乎一样区别在于显式维护了start变量逻辑更清晰。那道题的AC代码我用它提交耗时0ms内存几百KB。5.3 如果只要求输出最后一个幸存者直接套递推如果你碰到的题目只要求输出最后剩下来的人比如经典的“约瑟夫环”问题那就不需要vector了直接用递推公式就够了代码只有几行#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; int ans 0; // f(1) for (int i 2; i n; i) { ans (ans m) % i; } cout ans 1 endl; // 转回1-indexed return 0; }这里循环从i2到n每次用当前人数i取模。最终ans是0-indexed的幸存者下标加1才是真实编号。这段代码在n高达几百万、甚至几千万时依然可以飞快运行因为循环内部只做一次加法和一次取模几乎没有常数之外的额外开销。5.4 递推解法中容易踩的边界坑我自己在写递推解法时踩过的两个坑这里单独拎出来说一下。第一个坑是起始下标ans 0对应f(1)如果你从ans 1开始整个递推就全部错位最后输出会整体偏移1。第二个坑是取模对象有人在循环里写(ans m) % n把取模对象固定成了n这是错的。每一轮人数在变化取模对象必须是当前i而不是总人数n。举例来说n10、m100时m远大于当前人数不取模绝对越界但即使是mn这个固定n的错误也会在后期产生偏差。6. P1996之外的延伸思考数据范围变大、变体问题与学习建议P1996本身只是一道入门题但约瑟夫环这个模型在实际中有一堆变体数据范围扩大、m每次变化、要求输出前k个出圈者、双向约瑟夫、环形链表上的动态维护等等。真正把这题的两种思路模拟与递推都理解了你才能在面对这些变体时快速判断该用什么方案。6.1 数据范围扩大后的进阶方案如果n和m都达到1e5级别且必须输出完整出圈顺序这时候纯粹的模拟就不太可行了O(n²)级别但递推公式又只能输出幸存者。业界常用的方案是用树状数组或线段树来模拟“删除”过程通过区间求和找到当前存活的人中第k个人的位置每次删除复杂度O(log n)总复杂度O(n log n)。线段树的具体做法是建一棵维护区间“存活人数”的线段树叶子值为1表示该位置还有人0表示已经出圈。每次要删除时计算当前出圈位置在“存活序列”中的排名然后在线段树上二分找到第k个存活者的位置输出并把该位置设为0。这个做法本质上还是“模拟每一轮删除”只是把“找第k个人”和“删除”两步都变成了O(log n)。如果n到2e5这个方案是标准解。6.2 约瑟夫问题变体的几个方向我自己在刷题中遇到的变体主要有三种都是基于这道题延展开的第一种是“m很大”的情况。比如n100但m1e9这时候你不可能模拟m步但可以观察到报数过程会多轮循环每轮完整遍历一圈相当于抵消m % n的步数。利用这种取模压缩可以把每次找人的复杂度从O(m)降至O(1)整个模拟过程就是O(n)。这个优化在n很小、m极大时非常有用。第二种是“m动态变化”。有些题目中每个人出圈后会导致m按某种规则变化比如变成当前出圈者的编号的某种函数这时候递推公式没法用因为公式的前提是m恒定。只能回到模拟但可以用“二叉搜索树/平衡树”维护存活序列从而在O(log n)内完成每次删除。第三种是“要求第k个幸存者”。经典的递推只能求最后一个幸存者但如果你想知道第k轮出圈的人是谁一种办法是把递推过程倒过来先计算最后一轮幸存者然后逐步回溯出每轮的“位置编号”。具体做法是从n个人推到1个人的过程中记录每次ans的中间值然后从n个人的角度重新走一遍找到某个时刻的幸存者下标。这个思路比较绕但写出来也能做到O(n)。6.3 就这道题我的实操心得和学习建议最后分享一点自己的经验。P1996这道题最简单的是AC最难的是“真正理解递推”。如果你只是把模拟代码背下来过了题那你在这道题上几乎没有收获。我建议按这个顺序折腾一遍先用vector模拟写一版然后用数组标记法写一版对比两种实现的时间和代码复杂度接着手动推导一遍递推公式的映射关系再用递推代码写一版“只输出幸存者”的程序跟模拟结果对拍最后把n和m改成大数实测一下两种写法的性能差距。对拍是刷算法题最实用的习惯。把暴力和优化版本写到同一个文件中生成大量随机小数据通过system(fc /c)或直接写一个循环比对输出能帮你快速发现推导错误。我当年做这道题时就是靠对拍找到自己在递推中取模对象错误的n1时边界不对我一开始用的基础版本f(1)1是靠对拍抓出来的。关于“报数偏移”的理解我再多啰嗦一句这个-1的偏移贯穿整个约瑟夫问题的各种解法。你在写任何约瑟夫变体的代码之前先用n5、m3、手动模拟一遍出圈顺序再对照代码这个偏差就永远不会困扰你了。这道题的后续扩展空间很大。等你把基础版本吃透之后可以试试洛谷的其他变体题目比如数据范围更大或者带输出的约瑟夫问题你会发现自己对“递推 数据结构”的双重视角越来越熟练。算法学习就是这样一道看似简单的题只要你愿意往下钻能挖出来的东西远比题面看起来要多。
