如果你在OJ上刷过题，看到“HDU1457 Counting Out”这道题，第一反应多半是：哦，约瑟夫环啊。这道题我之前也卡过一阵子——不是卡在原理上，而是卡在“到底要输出什么”和“怎么把淘汰顺序完整地打出来”这两件事上。今天就从这道题出发，把约瑟夫环从暴力模拟到数学递推、再到高效输出完整序列的思路一次讲清楚，顺带聊聊那些年我在这类题上踩过的坑。

这篇文章适合刚接触约瑟夫环、只会照着模板抄的算法新手，也适合已经会一些基础解法、但想搞明白“递推公式到底怎么来的”“为什么不能直接输出淘汰顺序”的进阶读者。我会尽量把每一步都说透，不只给结论，还给推导过程，让你下次遇到变形题也不慌。

1. 从HDU1457这道题说起：Counting Out到底在考什么

1.1 题目类型与题意推断

“Counting Out”这个名字很直白，就是“数数淘汰”的意思。这类题在算法里有一个经典原型：n个人围成一圈，从某一个人开始报数，报到k的人离开圈子，下一个人重新从1开始报数，直到剩下最后一个人。整个过程就是一个典型的约瑟夫环问题。

HDU1457的具体输入输出格式各OJ版本可能稍有差异，但核心不变：给定人数n和报数间隔k，要求输出出圈顺序，或者输出最后幸存者的编号。题目标题里带了“约瑟夫环”标签，基本就是这道题最精确的指向了。

这里有一个容易被忽略的点：题目问的是“输出完整出圈序列”还是“输出最后幸存者”。这两种需求对应的解法完全不同。如果只问幸存者，一行递推搞定；如果要输出所有人的出圈顺序，朴素模拟是O(nk)，数据一大就爆。所以拿到题目第一步不是写代码，而是看输入输出样例，确认它到底要什么。

1.2 一个小样例把规则彻底走一遍

为了后面所有代码都能对照验证，我固定用一个例子：n=5，k=2。意思是有5个人，编号1到5，围成一圈，从1号开始报数，报到2的人出圈。

手动走一遍：

• 从1号开始，报数：1报1，2报2，2号出圈。此时圈子从3号继续，剩余：1、3、4、5。
• 从3号开始，报数：3报1，4报2，4号出圈。此时圈子从5号继续，剩余：1、3、5。
• 从5号开始，报数：5报1，1报2，1号出圈。此时圈子从3号继续，剩余：3、5。
• 从3号开始，报数：3报1，5报2，5号出圈。最后剩下3号。

所以出圈顺序是：2、4、1、5，幸存者是3。这个结果非常重要，后面所有代码我都会用它来验证。

很多人在这里会犯一个小错：把“报到k的人出圈”理解成“跳过k个人再出圈”。这两个说法差一个身位。如果题目要求“每数k下淘汰一个人”，那淘汰的是报数为k的那个人；如果要求“每隔k个人淘汰一个”，那规则就变了。做约瑟夫环相关题目时，第一步永远是确认报数规则，别凭感觉。

2. 朴素模拟：数组next、链表与队列，三种直球打法

2.1 数组next指针模拟：最像手算的写法

初学的时候，我写约瑟夫环最喜欢用数组来模拟链表。思路很简单：开一个next数组，next[i]表示编号i的下一个编号，初始化时把1到n串成一个环，然后沿着环一步一步走。

下面是核心代码，按n=5、k=2跑一遍，能直接得到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特别大（比如k=1000000000）时，程序会在环上无限绕圈，本地小数据看不出问题，一上大数据就超时。取模的本质是：绕完整圈等于没移动，真正需要走的是不满一圈的余数部分。

用数组模拟链表还有一个隐蔽问题：删除节点时，要记得更新“前驱”的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) { queue<int> 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模拟、链表模拟、队列模拟放在一起对比，你会发现它们其实是一个思路的三种皮肤，本质都是“沿着圈子一步步数人”。

这三种方法在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。边界条件是i=1时只有一个人，幸存者编号自然是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编号 }

我拿n=5、k=2验证：f(1)=0，f(2)=(0+2)%2=0，f(3)=(0+2)%3=2，f(4)=(2+2)%4=0，f(5)=(0+2)%5=2，最后输出2+1=3，和手动推演的幸存者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. 初始所有人存活，树状数组中每个位置值为1。
2. 维护当前报数起点对应的编号cur。
3. 计算cur在当前剩余集合中的排名rank。
4. 从rank开始数k下，得到被淘汰者在剩余集合中的排名pos。
5. 用二分查找找到排名pos对应的真实编号del，输出del。
6. 把del从树状数组中删除（单点减1）。
7. 删除后，确定下一轮的报数起点，继续循环。

为什么这里还要维护“排名”？因为树状数组是按编号大小维护存活信息的，而报数是按环形顺序走的。编号大小顺序和环形报数顺序不是一个东西。只有把起点换算成排名，才能统一到树状数组的坐标系里。

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

我再用n=5、k=2把这套代码完整走一遍：

• 初始alive=5，cur=1。rank=sum(1)=1，pos=(1+2-2)%5+1=2，kth(2)=2，淘汰2。2不是最后一名，删除后起点kth(2)=3。
• 第二轮cur=3，rank=sum(3)=2，pos=(2+2-2)%4+1=3，kth(3)=4，淘汰4。删除后起点kth(3)=5。
• 第三轮cur=5，rank=sum(5)=3，pos=(3+2-2)%3+1=1，kth(1)=1，淘汰1。删除后起点kth(1)=3。
• 第四轮cur=3，rank=sum(3)=1，pos=(1+2-2)%2+1=2，kth(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只参与取模运算，不会进入循环次数。

在实际OJ中，如果题目只要求输出幸存者，递推公式是永远的神；如果明确要求输出出圈顺序，而n到了1e5、k又可能极大，树状数组就是最稳妥的答案。当年我做HDU1457的时候，一开始用的是队列模拟，本地样例全过，结果一提交超时，换树状数组才顺利通过。

5. 数据范围再大一点：n极大而k极小时的加速思路

5.1 k=2时的封闭公式与一般情况的批量跳

有些题目会把数据范围拉到n=1e9甚至更大，这时连O(n)的递推都会觉得吃力。如果k刚好等于2，约瑟夫环有一个非常漂亮的封闭解。

结论是：从1编号，当k=2时，最后幸存者编号等于——把n写成二进制，然后把最高位的1移到最低位，得到的值就是答案。

举个例子，n=5，二进制是101，把最高位的1移到最低位，变成011，也就是3，正好对应幸存者3。n=6，二进制110，移动最高位后是100，也就是4。手动推一下k=2、n=6：出圈顺序是2、4、6、3、1，幸存者是5？等等，这里要小心。

我重新推n=6，k=2：

• 1报1，2报2，2出圈，从3开始。
• 3报1，4报2，4出圈，从5开始。
• 5报1，6报2，6出圈，从1开始。
• 1报1，3报2，3出圈，从5开始。
• 5报1，1报2，1出圈，剩下5。

所以幸存者是5，不是4。那“最高位循环左移”的说法好像有问题。实际上，之前我记错了表述。正确的结论应该用公式：

m = 2^floor(log2(n)) ans = 2 * (n - m) + 1

验证：n=5，m=4，ans=2*(5-4)+1=3。n=6，m=4，ans=2*(6-4)+1=5。都对。k=2时这个公式是从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 三个典型的“本地能过，交上去就错”的坑

第一个坑是k=1。看起来最简单的边界，反而最容易挂。用数组next模拟时，如果k=1，报数报到1就淘汰，那其实就是从1号开始顺着编号依次出圈，最后留下n号。但如果代码里没有处理k=1的特例，比如在移动时写成了(k - 1) % alive，那没问题；可如果写的是while (step--)，step=0时循环体一次都不执行，直接删除当前节点，正好就是k=1的正常逻辑。问题往往出在有些人在初始化时另起了一套逻辑，把k=1当普通情况处理，结果在cur和prev的更新上出现错位。

第二个坑是编号体系混用。递推公式那个章节我已经强调过了，这里再说一个具体场景：有人在循环里先算了一个0编号的结果，输出前加1，但后面又拿这个加1后的值继续参与下一轮递推，结果整个序列漂移一位。这种错误非常隐蔽，样例n=5、k=2可能碰巧能过，换个数据就炸。排查方法也很简单：把所有输出统一到手动推演的小样例上，一步一对，几秒钟就能发现第几个数开始错的。

第三个坑是树状数组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不是思路问题，而是边界或者编号转换的问题，对拍能在几十秒内暴露它们。

最后说一点个人体会：约瑟夫环入门很简单，但真要熟练掌握，必须自己在纸上推导那个递推公式，而不是背。我第一次看递推公式时也觉得玄乎，后来花了一个晚上，反复推演n=5、n=6、n=7的整个过程，把所有淘汰步骤和编号映射一五一十写下来，才真正理解“重新编号”这一步的本质。从那以后，不管题目怎么变形——隔几个淘汰、从不同起点开始、问第几个出圈——我都能从原始推导出发快速找到对应解法。刷题这件事，很多时候差的不是聪明，而是愿不愿意把“背会的”变成“推会的”。