【题解】ACMOJ 11038 约瑟夫环

题目描述

有 $n$ 个人编号 $1,2,\dots ,n$ 轮流报数（首轮从 $1$ 号开始报数），给定一组 $k_1,k_2,\dots ,k_{n-1}$，第 $i$ 轮报数 $k_i$ 的人出圈，并从下家开始重新报数，问最后留下的人的编号，保证 $n\leq 10^4,k_i\leq 10^8$

问题分析

注意到 $k_i$ 的规模并不重要，对剩余人数取模即有 $k_i\leq n$，利用循环链表可以实现 $O(n^2)$ 的模拟

下面介绍一种递推做法：

逆向考虑过程，尝试通过第 $i$ 轮的起始位置反推第 $i-1$ 轮的起始位置，在保证相对顺序不变的前提下，我们认为第 $i$ 轮开始时圈内 $n-i+1$ 人的相对位置即为 $0,1,2,\dots ,n-i$

记第 $i$ 轮的起始位置为 $a_i$，其中 $a_n=0$，反推即有关系 $a_i=(a_{i+1}+k_i)\mod (n-i+1)$，所求 $a_1$ 即为最后留下的人与 $1$ 号的相对位置，此时 $a_1+1$ 即为答案

该算法的时间复杂度为 $O(n)$，即使 $n\leq 10^8$ 仍可以高效解决问题

代码

#include <cstdio>
const int NMAX = 10005;

int k[NMAX], n, answer = 0;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
        scanf("%d", &k[i]);
    for (int i = 2; i <= n; i++)
        (answer += k[n - i + 1]) %= i;
    printf("%d\n", ++answer);
    return 0;
}