NOIP 提高组初赛 · NOIP 2007 提高组初赛试题 第 22 题

$N$ 个人在操场里围成一圈，将这 $N$ 个人按顺时针方向从 $1$ 到 $N$ 编号，然后，从第一个人起，每隔一个人让下一个人离开操场，显然，第一轮过后，具有偶数编号的人都离开了操场。依次做下去，直到操场只剩下一个人，记这个人的编号为 $J(N)$ ，例如，$J(5)=3$ ，$J(10)=5$ ，等等。则 $J(400)=$______________。

（提示：对 $N=2^m+r$ 进行分析，其中 $0\leq r<2^m$ ）。

别死算，这题本质是找最高次幂。把400拆成2的幂加余数，余数翻倍加1就是答案，专治各种手算疲劳。

最容易栽跟头就是跟经典约瑟夫隔一个杀一个的公式J(N)=2L+1（L是二进制循环左移）搞混，那个是隔一个杀一个，本题是每轮全杀偶数，公式完全不同。还有人会试图模拟几轮，算到后面数字大了就乱套。另外，拆2的幂时，m取小了，比如把400拆成256+144，有人可能误以为m=7（128），那样r就变成272，算出来J=545，完全跑偏。记住，m必须取最大的那个2的幂，r才是剩下的部分，公式里2r+1才能对上。

这道题考的是约瑟夫问题的一个特殊变种，核心知识点就是二进制表示与幂次分解。命题人喜欢在这种看似简单的模拟题里挖陷阱，把经典约瑟夫公式混进来，或者让学生盲目模拟，其实只要抓住“每轮去掉所有偶数编号”这个特征，就能直接推导出通项公式。

先理清概念：题目要求从1到N围成一圈，第一轮去掉所有偶数编号的人，剩下的人重新编号（从1开始），然后重复这个过程，直到只剩一人。关键点在于，每轮操作后，剩下的人的编号都是奇数，且数量减半。经过m轮后，剩下的人的编号是2^m + r的形式，其中r是初始N减去2^m的余数。

推导过程：假设N = 2^m + r，其中0 <= r < 2^m。第一轮去掉所有偶数编号，剩下的人重新编号，相当于把原来的编号减去2^m（因为每轮去掉一半，剩下的一半重新编号，编号从1开始）。经过m轮后，剩下的人的编号是r + 1。再经过一轮，去掉偶数编号，剩下的人的编号是2(r + 1) - 1 = 2r + 1。因此，J(N) = 2r + 1。

验证公式：J(5) = 2*1 + 1 = 3，J(10) = 2*2 + 1 = 5，都符合题目给出的例子。

计算J(400)：400 = 256 + 144，其中256 = 2^8，144 < 256，所以m = 8，r = 144。代入公式，J(400) = 2*144 + 1 = 289。

避坑指南：最容易错的就是公式混淆，把经典约瑟夫公式J(N) = 2L + 1（L是二进制循环左移）用在这里，或者误以为每轮去掉一半人后编号不变。还有人会试图模拟几轮，算到后面数字大了就乱套。记住，m必须取最大的那个2的幂，r才是剩下的部分，公式里2r+1才能对上。

考频与趋势：计数原理在题库中总共考过36题，覆盖4个考试级别（2007-2025），逐年分布为2007年4题、2008年2题、2009年1题、2010年2题、2019年6题、2020年4题、2021年3题、2022年1题、2023年3题、2024年5题、2025年5题。分赛事来看，CSP提高级14题、CSP入门级13题、NOIP普及组初赛5题、NOIP提高组初赛4题。本题属于NOIP提高组初赛，考频适中，且近年来计数原理类题目在NOIP提高组初赛中占比稳定，说明这类题目是命题人的常客。

预测：基于给定数据与经验，未来可能继续考类似的计数原理题目，尤其是涉及二进制表示与幂次分解的变种。暂无足够依据预测具体年份或题型，但这类题目在NOIP提高组初赛中仍具有较高的出现概率。