题解

把展台编号整体减一后，当前位置可以用 $0$ 到 $n-1$ 之间的整数表示．沿顺时针移动一步相当于位置加一，沿逆时针移动一步相当于位置减一；经过环线首尾时，位置按模 $n$ 的意义循环．

算法 0：逐步移动

按照 $d_i$ 的符号，逐条指令模拟每一步移动：

• 顺时针越过展台 $n$ 时回到展台 $1$；
• 逆时针越过展台 $1$ 时回到展台 $n$．

每条指令除读写外需要执行 $|d_i|$ 次单步移动，因此总时间复杂度为

空间复杂度为 $O(1)$．在 subtask 1 中总移动次数至多 $10^4$，在 subtask 4 中总移动次数至多 $10^7$，均可通过．

预期通过 subtask 1、4，预期得分为 $35$ 分．

算法 1：利用特殊方向或移动范围

对于 subtask 2，所有 $d_i$ 均非负．令当前位置的零基编号为 $p$，直接计算

即可．因为被取模的数非负，C++ 的余数结果也一定非负．

对于 subtask 3，有 $|d_i|<n$．移动前 $0\le p<n$，所以移动后一定有

若结果小于 $0$，将其加上一次 $n$；若结果不小于 $n$，将其减去一次 $n$，即可恢复到 $[0,n-1]$．

这两种做法每条指令都只进行常数次运算，总时间复杂度为 $O(m)$，空间复杂度为 $O(1)$．

非负取模做法预期通过 subtask 2；单次边界修正做法预期通过 subtask 3．两种做法分别可获得 $20$ 分．

算法 2：有符号模运算

完整数据中，$d_i$ 可能为负，并且绝对值可能远大于 $n$．在环上移动 $n$ 步后会回到原位置，因此把一条指令替换成它模 $n$ 的余数不会改变终点．

设执行指令前的零基位置为 $p$．先计算

此时 $|d_i\bmod n|<n$，而 $0\le p<n$，所以加法中间结果的绝对值小于 $2n$，不会因 $d_i$ 接近 $10^{18}$ 而溢出．

C++ 规定负数除法的余数可以为负，例如 $-1\bmod 7=-1$．因此上述表达式计算后，如果 $p<0$，还需要令

处理后必有 $0\le p<n$，实际展台编号就是 $p+1$．

正确性证明

引理： 从同一展台出发，移动距离之差为 $n$ 的整数倍的两条指令会到达同一展台．

证明： 沿任意固定方向移动恰好 $n$ 步会经过整条环线并回到出发点．增加或减少任意个完整的 $n$ 步循环都不会改变终点．证毕．

定理： 算法输出的每个展台编号均正确．

证明： 对指令编号归纳．执行第一条指令前，算法中的零基位置 $s-1$ 与实际初始展台对应．假设第 $i$ 条指令前算法位置正确．根据引理，使用 $d_i\bmod n$ 代替 $d_i$ 不改变终点；两次取模和必要的一次加 $n$，恰好选出该终点在区间 $[0,n-1]$ 内唯一的零基编号．所以第 $i$ 条指令后的输出正确，并为下一条指令保持了归纳条件．因此所有输出都正确．证毕．

复杂度分析

每条指令只进行常数次整数运算，总时间复杂度为 $O(m)$，除输入输出外只保存当前位置，额外空间复杂度为 $O(1)$．

预期通过所有 subtask，预期得分为 $100$ 分．

参考代码

#include <cstdint>
#include <iostream>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::int64_t n = 0;
    std::int64_t s = 0;
    int m = 0;
    std::cin >> n >> m >> s;

    std::int64_t position = s - 1;
    for (int i = 0; i < m; ++i) {
        std::int64_t movement = 0;
        std::cin >> movement;
        position = (position + movement % n) % n;
        if (position < 0) {
            position += n;
        }
        if (i != 0) {
            std::cout << ' ';
        }
        std::cout << position + 1;
    }
    std::cout << '\n';
    return 0;
}