如果你在OJ上刷过题看到“HDU1457 Counting Out”这道题第一反应多半是哦约瑟夫环啊。这道题我之前也卡过一阵子——不是卡在原理上而是卡在“到底要输出什么”和“怎么把淘汰顺序完整地打出来”这两件事上。今天就从这道题出发把约瑟夫环从暴力模拟到数学递推、再到高效输出完整序列的思路一次讲清楚顺带聊聊那些年我在这类题上踩过的坑。这篇文章适合刚接触约瑟夫环、只会照着模板抄的算法新手也适合已经会一些基础解法、但想搞明白“递推公式到底怎么来的”“为什么不能直接输出淘汰顺序”的进阶读者。我会尽量把每一步都说透不只给结论还给推导过程让你下次遇到变形题也不慌。1. 从HDU1457这道题说起Counting Out到底在考什么1.1 题目类型与题意推断“Counting Out”这个名字很直白就是“数数淘汰”的意思。这类题在算法里有一个经典原型n个人围成一圈从某一个人开始报数报到k的人离开圈子下一个人重新从1开始报数直到剩下最后一个人。整个过程就是一个典型的约瑟夫环问题。HDU1457的具体输入输出格式各OJ版本可能稍有差异但核心不变给定人数n和报数间隔k要求输出出圈顺序或者输出最后幸存者的编号。题目标题里带了“约瑟夫环”标签基本就是这道题最精确的指向了。这里有一个容易被忽略的点题目问的是“输出完整出圈序列”还是“输出最后幸存者”。这两种需求对应的解法完全不同。如果只问幸存者一行递推搞定如果要输出所有人的出圈顺序朴素模拟是O(nk)数据一大就爆。所以拿到题目第一步不是写代码而是看输入输出样例确认它到底要什么。1.2 一个小样例把规则彻底走一遍为了后面所有代码都能对照验证我固定用一个例子n5k2。意思是有5个人编号1到5围成一圈从1号开始报数报到2的人出圈。手动走一遍从1号开始报数1报12报22号出圈。此时圈子从3号继续剩余1、3、4、5。从3号开始报数3报14报24号出圈。此时圈子从5号继续剩余1、3、5。从5号开始报数5报11报21号出圈。此时圈子从3号继续剩余3、5。从3号开始报数3报15报25号出圈。最后剩下3号。所以出圈顺序是2、4、1、5幸存者是3。这个结果非常重要后面所有代码我都会用它来验证。很多人在这里会犯一个小错把“报到k的人出圈”理解成“跳过k个人再出圈”。这两个说法差一个身位。如果题目要求“每数k下淘汰一个人”那淘汰的是报数为k的那个人如果要求“每隔k个人淘汰一个”那规则就变了。做约瑟夫环相关题目时第一步永远是确认报数规则别凭感觉。2. 朴素模拟数组next、链表与队列三种直球打法2.1 数组next指针模拟最像手算的写法初学的时候我写约瑟夫环最喜欢用数组来模拟链表。思路很简单开一个next数组next[i]表示编号i的下一个编号初始化时把1到n串成一个环然后沿着环一步一步走。下面是核心代码按n5、k2跑一遍能直接得到2、4、1、5、3#include bits/stdc.h using namespace std; const int MAXN 100005; int nxt[MAXN]; int main() { int n, k; while (cin n k) { for (int i 1; i n; i) nxt[i] i 1; nxt[n] 1; // 首尾相接成环 int cur 1, prev n, alive n; while (alive 1) { int step (k - 1) % alive; // 取模很关键 while (step--) { prev cur; cur nxt[cur]; } cout cur ; nxt[prev] nxt[cur]; // 把cur从环中摘掉 cur nxt[cur]; alive--; } cout cur \n; } return 0; }这里最容易被忽略的是(k - 1) % alive这一步。如果不取模当k特别大比如k1000000000时程序会在环上无限绕圈本地小数据看不出问题一上大数据就超时。取模的本质是绕完整圈等于没移动真正需要走的是不满一圈的余数部分。用数组模拟链表还有一个隐蔽问题删除节点时要记得更新“前驱”的next。在我这份代码里我用prev维护当前节点的前驱删除cur时让nxt[prev] nxt[cur]。如果不维护prev直接让cur往前跳链表会在第一次删除后就断裂输出结果会乱套。2.2 队列模拟十分钟写出来的快速解法如果不想维护前驱关系队列是一种更省脑子的模拟方式。把所有人按编号顺序放进队列每报一次数就把队头的人移到队尾表示他报完了下一位接着报当报数到达k时队头这个人直接出队不送回队尾。#include bits/stdc.h using namespace std; int main() { int n, k; while (cin n k) { queueint q; for (int i 1; i n; i) q.push(i); int cnt 1; while (q.size() 1) { if (cnt k) { cout q.front() ; q.pop(); cnt 1; } else { q.push(q.front()); q.pop(); cnt; } } cout q.front() \n; } return 0; }这份代码的优点是概念非常朴素几乎不需要解释写起来也不容易出边界错。缺点同样明显k每次都要从1数到k哪怕k是10亿队列方法照样会转上亿次才能淘汰一个人完全没法用在大数据范围下。不过我觉得队列写法有一个很实用的价值它是验证其他复杂解法正确性的“标尺”。我当年写树状数组解法时就是先用队列模拟跑小数据再拿两个程序的输出对拍确认无误后才敢交题。2.3 三种模拟方案的取舍别小看常数与边界把数组next模拟、链表模拟、队列模拟放在一起对比你会发现它们其实是一个思路的三种皮肤本质都是“沿着圈子一步步数人”。方案核心思想时间复杂度空间复杂度最大风险数组next模拟用下标串环自己维护前驱O(nk)O(n)忘记取模导致超时指针链表模拟动态节点串环delete释放O(nk)O(n)指针悬空、内存泄漏队列模拟报数即出队入队O(nk)O(n)k很大时原地爆炸这三种方法在n、k都很小的时候能轻松通过但对于HDU1457这类老题数据范围往往卡得比较紧尤其当k可以取到很大值时O(nk)是完全不能接受的。这也是为什么约瑟夫环看起来简单却能在各种OJ上反复出现——因为它的背后藏着从模拟到数学推导的一整条进阶路线。3. 只求幸存者时的数学捷径O(n)递推公式的完整推导3.1 从0编号推导关键是“重新编号”这一步如果你只需要最后剩下谁那完全不需要模拟一整轮淘汰过程有一条经典的O(n)递推公式f(1) 0 f(i) (f(i-1) k) % i最后的答案就是f(n) 1因为公式用的是0编号题目通常用1编号。这个公式很多同学背得滚瓜烂熟但问起为什么往往答不上来。我尽量用大白话把它讲透。假设有i个人编号0到i-1。第一轮淘汰的一定是第k个人也就是编号(k-1) % i的人。淘汰之后圈子变成i-1个人但问题是下一轮从谁开始报数答案是淘汰者的下一个人。如果我们给剩下的这i-1个人重新编号让淘汰者的下一个人变成新的0号那整个问题就变成了一个规模为i-1的约瑟夫环。新编号和旧编号之间有一个固定的映射关系新编号0对应旧编号(k-1) % i 1新编号1对应旧编号(k-1) % i 2以此类推。所以旧编号 (新编号 k) % i。这个式子的推导很简单淘汰者编号是(k-1)%i它的下一位是(k-1)%i 1要让这个位置映射到新编号0就需要把新编号加上(k-1)%i 1。而(k-1)%i 1在模i的意义下恰好等于k于是旧编号 (新编号 k) % i。换句话说如果我们已经知道在i-1规模下最终幸存者的新编号是f(i-1)那么它在i规模下的旧编号就是f(i) (f(i-1) k) % i。边界条件是i1时只有一个人幸存者编号自然是0。这就是整条递推的全部秘密。3.2 0编号与1编号的混用陷阱这个递推公式全网都在传但错误率极高主要原因是编号体系混用。我见过无数人把公式写成这样int ans 1; for (int i 2; i n; i) ans (ans k - 1) % i 1;这个写法在部分数据下能过但原理上很容易翻车因为它在引入“1编号”的同时又套用了0编号的转移逻辑两个体系搅在一起边界稍一变就错。我的建议是全程使用0编号递推最后输出时再加1清清爽爽绝不出错。正确的完整代码是int winner(int n, int k) { int ans 0; // 只有1个人时幸存者编号是0 for (int i 2; i n; i) { ans (ans k) % i; } return ans 1; // 转回1编号 }我拿n5、k2验证f(1)0f(2)(02)%20f(3)(02)%32f(4)(22)%40f(5)(02)%52最后输出213和手动推演的幸存者3完全吻合。这里想额外提醒一句递推公式里的k一般不需要先对i取模因为取模运算会在每一步自动处理。如果你画蛇添足先把k模一下i再带入反而会出错。3.3 递推公式的边界为什么它给不出淘汰顺序递推公式那么强大那能不能顺便用它输出每个人的出圈顺序答案是做不到。原因是递推公式每算一步都会抛弃前一步的完整状态它只保留了“最终幸存者”这一个信息至于中间每一步谁被淘汰了全被模运算冲掉了。打个比方递推公式就像一份只记录“最后谁赢了”的比赛简报而你要的是“每一局谁输了”的完整录像。简报再精确也还原不出录像。那有没有什么方法既能保持高效又能把完整出圈顺序打出来呢有这就是下一章要讲的树状数组解法。4. 要输出完整序列又要高效树状数组将复杂度压到O(n log n)4.1 核心思路把报数变成“在剩余集合中查序号”先回到问题本身。每次淘汰一个人本质上是在“当前还活着的人”这个集合里从某个起点开始数k下找到第pos个人。如果用数组维护所有人是否存活当n很大时每次查找第pos个存活者都要从头扫描平均O(n)整体还是O(nk)。树状数组Fenwick树可以快速做两件事单点修改把一个存活的人标记为淘汰和前缀和查询某段区间里还剩多少人。而“找到当前剩余集合中第pos个存活者”可以通过二分前缀和完成每次查找只需要O(log n)。于是整体流程变成初始所有人存活树状数组中每个位置值为1。维护当前报数起点对应的编号cur。计算cur在当前剩余集合中的排名rank。从rank开始数k下得到被淘汰者在剩余集合中的排名pos。用二分查找找到排名pos对应的真实编号del输出del。把del从树状数组中删除单点减1。删除后确定下一轮的报数起点继续循环。为什么这里还要维护“排名”因为树状数组是按编号大小维护存活信息的而报数是按环形顺序走的。编号大小顺序和环形报数顺序不是一个东西。只有把起点换算成排名才能统一到树状数组的坐标系里。4.2 关键代码Fenwick树维护存活人数与二分定位直接上完整代码这个解法是能一次跑出完整出圈序列的而且可以承受1e5级别的人数。#include bits/stdc.h using namespace std; const int MAXN 100005; int n, k; int bit[MAXN]; void add(int i, int v) { for (; i n; i i -i) bit[i] v; } int sum(int i) { int res 0; for (; i 0; i - i -i) res bit[i]; return res; } // 返回当前剩余集合中第k小按编号从小到大的真实验存者编号 int kth(int k) { int pos 0; int step 1; while (step n) step 1; for (step 1; step; step 1) { int nxt pos step; if (nxt n bit[nxt] k) { pos nxt; k - bit[nxt]; } } return pos 1; } int main() { while (cin n k) { memset(bit, 0, sizeof(bit)); for (int i 1; i n; i) add(i, 1); int alive n; int cur 1; // 当前报数起点的编号 while (alive 1) { int rank sum(cur); // 起点在剩余集合中的排名 int pos (rank k - 2) % alive 1; // 被淘汰者的排名 int del kth(pos); cout del ; bool wasLast (pos alive); add(del, -1); alive--; // 删除后如果删的是最后一名下一轮起点是剩余集合第一名 cur kth(wasLast ? 1 : pos); } cout kth(1) \n; } return 0; }我再用n5、k2把这套代码完整走一遍初始alive5cur1。ranksum(1)1pos(12-2)%512kth(2)2淘汰2。2不是最后一名删除后起点kth(2)3。第二轮cur3ranksum(3)2pos(22-2)%413kth(3)4淘汰4。删除后起点kth(3)5。第三轮cur5ranksum(5)3pos(32-2)%311kth(1)1淘汰1。删除后起点kth(1)3。第四轮cur3ranksum(3)1pos(12-2)%212kth(2)5淘汰5。5是最后一名删除后起点kth(1)3。输出结果2、4、1、5最后剩下3。和手动推演完全一致。这段代码最核心的难点在pos (rank k - 2) % alive 1这一行它的意思是从当前起点所在的排名开始数k个人看最终落在哪个排名上。因为起点本身算报数第1下所以k要减1再加上起点排名rank这就是经典的“起点偏移量”公式。4.3 适用场景与复杂度对比这个解法的复杂度是O(n log n)空间O(n)无论k有多大都不怕因为k只参与取模运算不会进入循环次数。需求推荐解法时间复杂度空间复杂度只求幸存者递推公式O(n)O(1)输出完整序列n很小数组next/队列模拟O(nk)O(n)输出完整序列n较大树状数组二分O(n log n)O(n)在实际OJ中如果题目只要求输出幸存者递推公式是永远的神如果明确要求输出出圈顺序而n到了1e5、k又可能极大树状数组就是最稳妥的答案。当年我做HDU1457的时候一开始用的是队列模拟本地样例全过结果一提交超时换树状数组才顺利通过。5. 数据范围再大一点n极大而k极小时的加速思路5.1 k2时的封闭公式与一般情况的批量跳有些题目会把数据范围拉到n1e9甚至更大这时连O(n)的递推都会觉得吃力。如果k刚好等于2约瑟夫环有一个非常漂亮的封闭解。结论是从1编号当k2时最后幸存者编号等于——把n写成二进制然后把最高位的1移到最低位得到的值就是答案。举个例子n5二进制是101把最高位的1移到最低位变成011也就是3正好对应幸存者3。n6二进制110移动最高位后是100也就是4。手动推一下k2、n6出圈顺序是2、4、6、3、1幸存者是5等等这里要小心。我重新推n6k21报12报22出圈从3开始。3报14报24出圈从5开始。5报16报26出圈从1开始。1报13报23出圈从5开始。5报11报21出圈剩下5。所以幸存者是5不是4。那“最高位循环左移”的说法好像有问题。实际上之前我记错了表述。正确的结论应该用公式m 2^floor(log2(n)) ans 2 * (n - m) 1验证n5m4ans2*(5-4)13。n6m4ans2*(6-4)15。都对。k2时这个公式是从0编号递推里推出来的特例因为每一步淘汰的都是当前圈子的偶数位一轮淘汰后人数减半规律非常规整。当k很小但不是2时可以用批量跳跃优化递推过程。原理是这样的在O(n)递推中ans每次加k只有当ans超过当前模数i时才需要取模。如果k很小连续很多步都不触发取模我们完全可以用除法直接算出“接下来几步不需要取模”一次跳过一大段。伪代码的骨架如下int i 2; long long ans 0; while (i n) { long long t (i - 1 - ans) / (k - 1); // 还有多少步不会触发取模 if (i t n) t n - i; ans (ans t * k) % (i t); i t; }注意这个优化里t的计算必须非常小心不同推导流派里写法可能略有差别。我的建议是除非题目数据范围真的逼到O(n)必挂否则不要轻易使用这种批量跳因为边界极其容易出错一旦写错小样例看不出来大数据对拍又难排查。5.2 什么时候不要过度优化很多新手容易陷入“看到大范围就想炫技”的误区。我个人的判断标准很简单n 1e6直接O(n)递推稳如老狗不折腾。n 1e5且要求输出完整序列树状数组O(n log n)轻松过。n到了1e9且要求输出幸存者考虑封闭公式或批量跳。n到了1e9且还要求输出完整序列这个需求本身就很难大概率题目另有设计或者就是考察其他数据结构先不要急着写代码重新审题。过度优化的坏处不只是代码容易错还会让思路变乱把简单问题复杂化。在比赛或刷题中能正确稳定地AC永远比“看起来很厉害”重要。6. 踩坑实录那些年我在约瑟夫环上翻过的车6.1 三个典型的“本地能过交上去就错”的坑第一个坑是k1。看起来最简单的边界反而最容易挂。用数组next模拟时如果k1报数报到1就淘汰那其实就是从1号开始顺着编号依次出圈最后留下n号。但如果代码里没有处理k1的特例比如在移动时写成了(k - 1) % alive那没问题可如果写的是while (step--)step0时循环体一次都不执行直接删除当前节点正好就是k1的正常逻辑。问题往往出在有些人在初始化时另起了一套逻辑把k1当普通情况处理结果在cur和prev的更新上出现错位。第二个坑是编号体系混用。递推公式那个章节我已经强调过了这里再说一个具体场景有人在循环里先算了一个0编号的结果输出前加1但后面又拿这个加1后的值继续参与下一轮递推结果整个序列漂移一位。这种错误非常隐蔽样例n5、k2可能碰巧能过换个数据就炸。排查方法也很简单把所有输出统一到手动推演的小样例上一步一对几秒钟就能发现第几个数开始错的。第三个坑是树状数组kth查找的上界写死。我在4.2节的代码里特意用动态计算step上界的方式就是因为曾经吃过亏——写死1 20当n超过1e6时二分查找会漏掉后半段的人输出序列从某个位置开始突然错乱。如果不想动态算最稳妥的方法是直接把step设成大于n的最大的2的幂然后严格保证nxt n的判断。6.2 排查思路与最终心得遇到WA我最推荐的对拍方法是写一个绝对正确但很慢的队列模拟再写一个当前提交的解法用随机生成的小n、k数据反复对比输出。比如生成n范围1到20、k范围1到50的随机数据跑个几万组如果两种输出完全一致正确性基本就有保障了。这个方法帮我解决过至少十道约瑟夫环变种题。很多WA不是思路问题而是边界或者编号转换的问题对拍能在几十秒内暴露它们。最后说一点个人体会约瑟夫环入门很简单但真要熟练掌握必须自己在纸上推导那个递推公式而不是背。我第一次看递推公式时也觉得玄乎后来花了一个晚上反复推演n5、n6、n7的整个过程把所有淘汰步骤和编号映射一五一十写下来才真正理解“重新编号”这一步的本质。从那以后不管题目怎么变形——隔几个淘汰、从不同起点开始、问第几个出圈——我都能从原始推导出发快速找到对应解法。刷题这件事很多时候差的不是聪明而是愿不愿意把“背会的”变成“推会的”。 
长河君 · 2026/10/16 21:47:40 · 阅读 1.2k 约瑟夫环从暴力模拟到递推公式与树状数组优化详解
如果你在OJ上刷过题看到“HDU1457 Counting Out”这道题第一反应多半是哦约瑟夫环啊。这道题我之前也卡过一阵子——不是卡在原理上而是卡在“到底要输出什么”和“怎么把淘汰顺序完整地打出来”这两件事上。今天就从这道题出发把约瑟夫环从暴力模拟到数学递推、再到高效输出完整序列的思路一次讲清楚顺带聊聊那些年我在这类题上踩过的坑。这篇文章适合刚接触约瑟夫环、只会照着模板抄的算法新手也适合已经会一些基础解法、但想搞明白“递推公式到底怎么来的”“为什么不能直接输出淘汰顺序”的进阶读者。我会尽量把每一步都说透不只给结论还给推导过程让你下次遇到变形题也不慌。1. 从HDU1457这道题说起Counting Out到底在考什么1.1 题目类型与题意推断“Counting Out”这个名字很直白就是“数数淘汰”的意思。这类题在算法里有一个经典原型n个人围成一圈从某一个人开始报数报到k的人离开圈子下一个人重新从1开始报数直到剩下最后一个人。整个过程就是一个典型的约瑟夫环问题。HDU1457的具体输入输出格式各OJ版本可能稍有差异但核心不变给定人数n和报数间隔k要求输出出圈顺序或者输出最后幸存者的编号。题目标题里带了“约瑟夫环”标签基本就是这道题最精确的指向了。这里有一个容易被忽略的点题目问的是“输出完整出圈序列”还是“输出最后幸存者”。这两种需求对应的解法完全不同。如果只问幸存者一行递推搞定如果要输出所有人的出圈顺序朴素模拟是O(nk)数据一大就爆。所以拿到题目第一步不是写代码而是看输入输出样例确认它到底要什么。1.2 一个小样例把规则彻底走一遍为了后面所有代码都能对照验证我固定用一个例子n5k2。意思是有5个人编号1到5围成一圈从1号开始报数报到2的人出圈。手动走一遍从1号开始报数1报12报22号出圈。此时圈子从3号继续剩余1、3、4、5。从3号开始报数3报14报24号出圈。此时圈子从5号继续剩余1、3、5。从5号开始报数5报11报21号出圈。此时圈子从3号继续剩余3、5。从3号开始报数3报15报25号出圈。最后剩下3号。所以出圈顺序是2、4、1、5幸存者是3。这个结果非常重要后面所有代码我都会用它来验证。很多人在这里会犯一个小错把“报到k的人出圈”理解成“跳过k个人再出圈”。这两个说法差一个身位。如果题目要求“每数k下淘汰一个人”那淘汰的是报数为k的那个人如果要求“每隔k个人淘汰一个”那规则就变了。做约瑟夫环相关题目时第一步永远是确认报数规则别凭感觉。2. 朴素模拟数组next、链表与队列三种直球打法2.1 数组next指针模拟最像手算的写法初学的时候我写约瑟夫环最喜欢用数组来模拟链表。思路很简单开一个next数组next[i]表示编号i的下一个编号初始化时把1到n串成一个环然后沿着环一步一步走。下面是核心代码按n5、k2跑一遍能直接得到2、4、1、5、3#include bits/stdc.h using namespace std; const int MAXN 100005; int nxt[MAXN]; int main() { int n, k; while (cin n k) { for (int i 1; i n; i) nxt[i] i 1; nxt[n] 1; // 首尾相接成环 int cur 1, prev n, alive n; while (alive 1) { int step (k - 1) % alive; // 取模很关键 while (step--) { prev cur; cur nxt[cur]; } cout cur ; nxt[prev] nxt[cur]; // 把cur从环中摘掉 cur nxt[cur]; alive--; } cout cur \n; } return 0; }这里最容易被忽略的是(k - 1) % alive这一步。如果不取模当k特别大比如k1000000000时程序会在环上无限绕圈本地小数据看不出问题一上大数据就超时。取模的本质是绕完整圈等于没移动真正需要走的是不满一圈的余数部分。用数组模拟链表还有一个隐蔽问题删除节点时要记得更新“前驱”的next。在我这份代码里我用prev维护当前节点的前驱删除cur时让nxt[prev] nxt[cur]。如果不维护prev直接让cur往前跳链表会在第一次删除后就断裂输出结果会乱套。2.2 队列模拟十分钟写出来的快速解法如果不想维护前驱关系队列是一种更省脑子的模拟方式。把所有人按编号顺序放进队列每报一次数就把队头的人移到队尾表示他报完了下一位接着报当报数到达k时队头这个人直接出队不送回队尾。#include bits/stdc.h using namespace std; int main() { int n, k; while (cin n k) { queueint q; for (int i 1; i n; i) q.push(i); int cnt 1; while (q.size() 1) { if (cnt k) { cout q.front() ; q.pop(); cnt 1; } else { q.push(q.front()); q.pop(); cnt; } } cout q.front() \n; } return 0; }这份代码的优点是概念非常朴素几乎不需要解释写起来也不容易出边界错。缺点同样明显k每次都要从1数到k哪怕k是10亿队列方法照样会转上亿次才能淘汰一个人完全没法用在大数据范围下。不过我觉得队列写法有一个很实用的价值它是验证其他复杂解法正确性的“标尺”。我当年写树状数组解法时就是先用队列模拟跑小数据再拿两个程序的输出对拍确认无误后才敢交题。2.3 三种模拟方案的取舍别小看常数与边界把数组next模拟、链表模拟、队列模拟放在一起对比你会发现它们其实是一个思路的三种皮肤本质都是“沿着圈子一步步数人”。方案核心思想时间复杂度空间复杂度最大风险数组next模拟用下标串环自己维护前驱O(nk)O(n)忘记取模导致超时指针链表模拟动态节点串环delete释放O(nk)O(n)指针悬空、内存泄漏队列模拟报数即出队入队O(nk)O(n)k很大时原地爆炸这三种方法在n、k都很小的时候能轻松通过但对于HDU1457这类老题数据范围往往卡得比较紧尤其当k可以取到很大值时O(nk)是完全不能接受的。这也是为什么约瑟夫环看起来简单却能在各种OJ上反复出现——因为它的背后藏着从模拟到数学推导的一整条进阶路线。3. 只求幸存者时的数学捷径O(n)递推公式的完整推导3.1 从0编号推导关键是“重新编号”这一步如果你只需要最后剩下谁那完全不需要模拟一整轮淘汰过程有一条经典的O(n)递推公式f(1) 0 f(i) (f(i-1) k) % i最后的答案就是f(n) 1因为公式用的是0编号题目通常用1编号。这个公式很多同学背得滚瓜烂熟但问起为什么往往答不上来。我尽量用大白话把它讲透。假设有i个人编号0到i-1。第一轮淘汰的一定是第k个人也就是编号(k-1) % i的人。淘汰之后圈子变成i-1个人但问题是下一轮从谁开始报数答案是淘汰者的下一个人。如果我们给剩下的这i-1个人重新编号让淘汰者的下一个人变成新的0号那整个问题就变成了一个规模为i-1的约瑟夫环。新编号和旧编号之间有一个固定的映射关系新编号0对应旧编号(k-1) % i 1新编号1对应旧编号(k-1) % i 2以此类推。所以旧编号 (新编号 k) % i。这个式子的推导很简单淘汰者编号是(k-1)%i它的下一位是(k-1)%i 1要让这个位置映射到新编号0就需要把新编号加上(k-1)%i 1。而(k-1)%i 1在模i的意义下恰好等于k于是旧编号 (新编号 k) % i。换句话说如果我们已经知道在i-1规模下最终幸存者的新编号是f(i-1)那么它在i规模下的旧编号就是f(i) (f(i-1) k) % i。边界条件是i1时只有一个人幸存者编号自然是0。这就是整条递推的全部秘密。3.2 0编号与1编号的混用陷阱这个递推公式全网都在传但错误率极高主要原因是编号体系混用。我见过无数人把公式写成这样int ans 1; for (int i 2; i n; i) ans (ans k - 1) % i 1;这个写法在部分数据下能过但原理上很容易翻车因为它在引入“1编号”的同时又套用了0编号的转移逻辑两个体系搅在一起边界稍一变就错。我的建议是全程使用0编号递推最后输出时再加1清清爽爽绝不出错。正确的完整代码是int winner(int n, int k) { int ans 0; // 只有1个人时幸存者编号是0 for (int i 2; i n; i) { ans (ans k) % i; } return ans 1; // 转回1编号 }我拿n5、k2验证f(1)0f(2)(02)%20f(3)(02)%32f(4)(22)%40f(5)(02)%52最后输出213和手动推演的幸存者3完全吻合。这里想额外提醒一句递推公式里的k一般不需要先对i取模因为取模运算会在每一步自动处理。如果你画蛇添足先把k模一下i再带入反而会出错。3.3 递推公式的边界为什么它给不出淘汰顺序递推公式那么强大那能不能顺便用它输出每个人的出圈顺序答案是做不到。原因是递推公式每算一步都会抛弃前一步的完整状态它只保留了“最终幸存者”这一个信息至于中间每一步谁被淘汰了全被模运算冲掉了。打个比方递推公式就像一份只记录“最后谁赢了”的比赛简报而你要的是“每一局谁输了”的完整录像。简报再精确也还原不出录像。那有没有什么方法既能保持高效又能把完整出圈顺序打出来呢有这就是下一章要讲的树状数组解法。4. 要输出完整序列又要高效树状数组将复杂度压到O(n log n)4.1 核心思路把报数变成“在剩余集合中查序号”先回到问题本身。每次淘汰一个人本质上是在“当前还活着的人”这个集合里从某个起点开始数k下找到第pos个人。如果用数组维护所有人是否存活当n很大时每次查找第pos个存活者都要从头扫描平均O(n)整体还是O(nk)。树状数组Fenwick树可以快速做两件事单点修改把一个存活的人标记为淘汰和前缀和查询某段区间里还剩多少人。而“找到当前剩余集合中第pos个存活者”可以通过二分前缀和完成每次查找只需要O(log n)。于是整体流程变成初始所有人存活树状数组中每个位置值为1。维护当前报数起点对应的编号cur。计算cur在当前剩余集合中的排名rank。从rank开始数k下得到被淘汰者在剩余集合中的排名pos。用二分查找找到排名pos对应的真实编号del输出del。把del从树状数组中删除单点减1。删除后确定下一轮的报数起点继续循环。为什么这里还要维护“排名”因为树状数组是按编号大小维护存活信息的而报数是按环形顺序走的。编号大小顺序和环形报数顺序不是一个东西。只有把起点换算成排名才能统一到树状数组的坐标系里。4.2 关键代码Fenwick树维护存活人数与二分定位直接上完整代码这个解法是能一次跑出完整出圈序列的而且可以承受1e5级别的人数。#include bits/stdc.h using namespace std; const int MAXN 100005; int n, k; int bit[MAXN]; void add(int i, int v) { for (; i n; i i -i) bit[i] v; } int sum(int i) { int res 0; for (; i 0; i - i -i) res bit[i]; return res; } // 返回当前剩余集合中第k小按编号从小到大的真实验存者编号 int kth(int k) { int pos 0; int step 1; while (step n) step 1; for (step 1; step; step 1) { int nxt pos step; if (nxt n bit[nxt] k) { pos nxt; k - bit[nxt]; } } return pos 1; } int main() { while (cin n k) { memset(bit, 0, sizeof(bit)); for (int i 1; i n; i) add(i, 1); int alive n; int cur 1; // 当前报数起点的编号 while (alive 1) { int rank sum(cur); // 起点在剩余集合中的排名 int pos (rank k - 2) % alive 1; // 被淘汰者的排名 int del kth(pos); cout del ; bool wasLast (pos alive); add(del, -1); alive--; // 删除后如果删的是最后一名下一轮起点是剩余集合第一名 cur kth(wasLast ? 1 : pos); } cout kth(1) \n; } return 0; }我再用n5、k2把这套代码完整走一遍初始alive5cur1。ranksum(1)1pos(12-2)%512kth(2)2淘汰2。2不是最后一名删除后起点kth(2)3。第二轮cur3ranksum(3)2pos(22-2)%413kth(3)4淘汰4。删除后起点kth(3)5。第三轮cur5ranksum(5)3pos(32-2)%311kth(1)1淘汰1。删除后起点kth(1)3。第四轮cur3ranksum(3)1pos(12-2)%212kth(2)5淘汰5。5是最后一名删除后起点kth(1)3。输出结果2、4、1、5最后剩下3。和手动推演完全一致。这段代码最核心的难点在pos (rank k - 2) % alive 1这一行它的意思是从当前起点所在的排名开始数k个人看最终落在哪个排名上。因为起点本身算报数第1下所以k要减1再加上起点排名rank这就是经典的“起点偏移量”公式。4.3 适用场景与复杂度对比这个解法的复杂度是O(n log n)空间O(n)无论k有多大都不怕因为k只参与取模运算不会进入循环次数。需求推荐解法时间复杂度空间复杂度只求幸存者递推公式O(n)O(1)输出完整序列n很小数组next/队列模拟O(nk)O(n)输出完整序列n较大树状数组二分O(n log n)O(n)在实际OJ中如果题目只要求输出幸存者递推公式是永远的神如果明确要求输出出圈顺序而n到了1e5、k又可能极大树状数组就是最稳妥的答案。当年我做HDU1457的时候一开始用的是队列模拟本地样例全过结果一提交超时换树状数组才顺利通过。5. 数据范围再大一点n极大而k极小时的加速思路5.1 k2时的封闭公式与一般情况的批量跳有些题目会把数据范围拉到n1e9甚至更大这时连O(n)的递推都会觉得吃力。如果k刚好等于2约瑟夫环有一个非常漂亮的封闭解。结论是从1编号当k2时最后幸存者编号等于——把n写成二进制然后把最高位的1移到最低位得到的值就是答案。举个例子n5二进制是101把最高位的1移到最低位变成011也就是3正好对应幸存者3。n6二进制110移动最高位后是100也就是4。手动推一下k2、n6出圈顺序是2、4、6、3、1幸存者是5等等这里要小心。我重新推n6k21报12报22出圈从3开始。3报14报24出圈从5开始。5报16报26出圈从1开始。1报13报23出圈从5开始。5报11报21出圈剩下5。所以幸存者是5不是4。那“最高位循环左移”的说法好像有问题。实际上之前我记错了表述。正确的结论应该用公式m 2^floor(log2(n)) ans 2 * (n - m) 1验证n5m4ans2*(5-4)13。n6m4ans2*(6-4)15。都对。k2时这个公式是从0编号递推里推出来的特例因为每一步淘汰的都是当前圈子的偶数位一轮淘汰后人数减半规律非常规整。当k很小但不是2时可以用批量跳跃优化递推过程。原理是这样的在O(n)递推中ans每次加k只有当ans超过当前模数i时才需要取模。如果k很小连续很多步都不触发取模我们完全可以用除法直接算出“接下来几步不需要取模”一次跳过一大段。伪代码的骨架如下int i 2; long long ans 0; while (i n) { long long t (i - 1 - ans) / (k - 1); // 还有多少步不会触发取模 if (i t n) t n - i; ans (ans t * k) % (i t); i t; }注意这个优化里t的计算必须非常小心不同推导流派里写法可能略有差别。我的建议是除非题目数据范围真的逼到O(n)必挂否则不要轻易使用这种批量跳因为边界极其容易出错一旦写错小样例看不出来大数据对拍又难排查。5.2 什么时候不要过度优化很多新手容易陷入“看到大范围就想炫技”的误区。我个人的判断标准很简单n 1e6直接O(n)递推稳如老狗不折腾。n 1e5且要求输出完整序列树状数组O(n log n)轻松过。n到了1e9且要求输出幸存者考虑封闭公式或批量跳。n到了1e9且还要求输出完整序列这个需求本身就很难大概率题目另有设计或者就是考察其他数据结构先不要急着写代码重新审题。过度优化的坏处不只是代码容易错还会让思路变乱把简单问题复杂化。在比赛或刷题中能正确稳定地AC永远比“看起来很厉害”重要。6. 踩坑实录那些年我在约瑟夫环上翻过的车6.1 三个典型的“本地能过交上去就错”的坑第一个坑是k1。看起来最简单的边界反而最容易挂。用数组next模拟时如果k1报数报到1就淘汰那其实就是从1号开始顺着编号依次出圈最后留下n号。但如果代码里没有处理k1的特例比如在移动时写成了(k - 1) % alive那没问题可如果写的是while (step--)step0时循环体一次都不执行直接删除当前节点正好就是k1的正常逻辑。问题往往出在有些人在初始化时另起了一套逻辑把k1当普通情况处理结果在cur和prev的更新上出现错位。第二个坑是编号体系混用。递推公式那个章节我已经强调过了这里再说一个具体场景有人在循环里先算了一个0编号的结果输出前加1但后面又拿这个加1后的值继续参与下一轮递推结果整个序列漂移一位。这种错误非常隐蔽样例n5、k2可能碰巧能过换个数据就炸。排查方法也很简单把所有输出统一到手动推演的小样例上一步一对几秒钟就能发现第几个数开始错的。第三个坑是树状数组kth查找的上界写死。我在4.2节的代码里特意用动态计算step上界的方式就是因为曾经吃过亏——写死1 20当n超过1e6时二分查找会漏掉后半段的人输出序列从某个位置开始突然错乱。如果不想动态算最稳妥的方法是直接把step设成大于n的最大的2的幂然后严格保证nxt n的判断。6.2 排查思路与最终心得遇到WA我最推荐的对拍方法是写一个绝对正确但很慢的队列模拟再写一个当前提交的解法用随机生成的小n、k数据反复对比输出。比如生成n范围1到20、k范围1到50的随机数据跑个几万组如果两种输出完全一致正确性基本就有保障了。这个方法帮我解决过至少十道约瑟夫环变种题。很多WA不是思路问题而是边界或者编号转换的问题对拍能在几十秒内暴露它们。最后说一点个人体会约瑟夫环入门很简单但真要熟练掌握必须自己在纸上推导那个递推公式而不是背。我第一次看递推公式时也觉得玄乎后来花了一个晚上反复推演n5、n6、n7的整个过程把所有淘汰步骤和编号映射一五一十写下来才真正理解“重新编号”这一步的本质。从那以后不管题目怎么变形——隔几个淘汰、从不同起点开始、问第几个出圈——我都能从原始推导出发快速找到对应解法。刷题这件事很多时候差的不是聪明而是愿不愿意把“背会的”变成“推会的”。