KOLO（COI 2010 T2）题解

题目分析

有 $n$ 个人围成一个圆环，初始时 $1$ 号位置有正方形标记，其余位置为圆形标记。游戏进行 $k$ 轮，第 $i$ 轮中，正方形标记所在的人会与右手边的人交换位置 $p_i$ 次（$p_i$ 为第 $i$ 个质数）。给定 $n,k,a$，要求输出 $k$ 轮后 $a$ 的右侧和左侧邻居编号。

关键难点

直接模拟所有人的位置变换会因 $n$ 最大为 $5 \times 10^6$ 而超时，因此需要通过数学推导简化位置变换逻辑，仅跟踪目标位置及邻居的变化。

核心思路

1. 质数预处理

$k$ 最大为 $5 \times 10^5$，第 $5 \times 10^5$ 个质数约为 $7.37 \times 10^6$，因此使用埃氏筛（bitset 优化） 预处理前 $k$ 个质数，存入数组 pr，其中 pr[i] 对应第 $i+1$ 个质数（适配代码中 0-based 索引）。

2. 坐标变换优化

将原编号 $1 \sim n$ 转换为 $0 \sim n-1$（0-based），方便模运算处理环形结构，最终输出时再还原为 1-based 编号。

3. 位置变换的数学推导

每轮操作中，正方形标记的位置会向右移动 $p_i$ 位（模 $n$）。直接模拟所有人位置不可行，因此：

• 正向计算目标位置 $a$ 经过 $k$ 轮后的最终位置；
• 反向推导该位置的左右邻居在 $k$ 轮操作后的实际位置（因为邻居的位置变化与目标位置的变换互逆）。

4. 核心函数逻辑

• nmod(x)：处理负数模运算，确保结果在 $0 \sim n-1$ 范围内；
• nxt(x, p)：正向计算位置 $x$ 经过一轮（质数 $p$）操作后的新位置；
• pre(x, p)：逆向操作，还原位置 $x$ 在一轮操作前的原始位置（nxt 的逆函数）。

解题步骤

1. 质数预处理：调用 sieve() 生成前 $k$ 个质数；
2. 坐标转换：将目标 $a$ 转为 0-based 编号 q = a - 1；
3. 正向更新目标位置：遍历 $k$ 轮，用 nxt 函数更新 q 为最终位置；
4. 确定邻居初始位置：最终位置的左邻居 l = (q - 1) mod n，右邻居 r = (q + 1) mod n；
5. 反向还原邻居位置：从最后一轮到第一轮，用 pre 函数还原邻居的实际位置；
6. 结果输出：将 l 和 r 转回 1-based 编号，输出右邻居 r+1 和左邻居 l+1。

复杂度分析

• 质数预处理：时间复杂度 $O(MXS \log \log MXS)$（$MXS$ 为第 $k$ 个质数的近似值），空间复杂度 $O(MXS)$（bitset 优化后空间占用极低）；
• 位置变换：时间复杂度 $O(k)$，仅需遍历 $k$ 轮处理目标位置和邻居，无额外空间开销；
• 整体复杂度：可高效处理题目给定的最大数据范围。

总结

本题的核心是避免全量模拟，通过数学推导将位置变换转化为单个位置的正向/逆向计算，结合质数预处理和模运算优化，在时间和空间上均满足题目要求。关键思路是：

1. 用筛法快速预处理所需质数；
2. 利用 0-based 坐标简化环形位置计算；
3. 正向跟踪目标位置，逆向还原邻居位置，规避大规模模拟的低效问题。

这种“聚焦目标、数学简化”的思路是解决大规模模拟类问题的常用技巧，值得借鉴。