题解：P5944 [POI2002] 出圈游戏

__vector__ · 2024-12-18 16:03:51 · 题解

做这题时没理解他是怎么报号的，猜了一种题意通过了，记录一下。

题意

有 n 个人，从左到右编号为 1,2,3,\cdots,n，且 n 右边是 1。

现在举行 n 轮游戏。

对于第 i 轮，从第 i-1 轮被踢出的人的右边的第一个存活的人开始报数，对于第一轮，则从 1 号开始。

从左到右报数，第一个人报 1，之后每个人报上一个人的数字加 1。

当有人报出 k 时，本轮结束，这个人被踢出。

现在已知第 i 个人是第 a_i 轮出圈的，求最小的 k，或者报告 NIE。

做法

考虑依次模拟每一轮，并在每一轮开始前，将开始报数的人编号设置为 1 并对所有存活的人按照报号顺序重新编号。

假设第 i 轮重新编号后，编号为 x 的人被踢出了，那么说明 k \equiv x \pmod {(n-i+1)} 。

显然，EXCRT 合并就可以解决本题。