第 2 题

题意分析

给定一个长度为 $N$ 的数列 $A$，以及整数 $K$。盘子中初始有 $0$ 颗糖，进行 $K$ 次操作：

• 设当前盘子有 $X$ 颗糖，计算下标 $i = X \bmod N$
• 向盘子中加入 $A_i$ 颗糖（即 $X \leftarrow X + A_i$）

求 $K$ 次操作后盘子中糖的总颗数。

关键约束：

• $2 \le N \le 2 \times 10^5$（数组长度，决定状态空间）
• $1 \le K \le 10^{12}$（操作次数极大，不能直接模拟 $K$ 次）
• $1 \le A_i \le 10^6$

注意到每次操作只依赖于 $X \bmod N$，而 $X \bmod N$ 的取值范围是 $[0, N-1]$，最多只有 $N$ 种不同状态。根据鸽巢原理，最多模拟 $N+1$ 次操作就一定会出现重复的状态（即相同的余数）。一旦余数重复，由于后续操作完全由当前余数决定，整个数列的状态转移就进入了循环节。因此我们可以用 $O(N)$ 的时间找到循环，再用 $O(1)$ 的时间加速计算后续巨量的重复操作。

---

思路分析

核心：记录每个余数第一次出现的时机

我们维护以下信息：

• $X$：当前盘子中的糖数（即题目中的总颗数）
• step：已经执行完成的操作次数
• seen[r]：记录余数 $r$ 第一次出现时，(step, X) 的数值对

模拟过程：

1. 计算当前余数 $r = X \bmod N$
2. 如果 seen[r] 已经有记录，说明循环节找到了：
   • 设上次出现余数 $r$ 时，操作次数为 pre_step，糖数为 pre_val
   • 当前是第 step 次操作前，糖数为 $X$
   • 这意味着从 pre_step 到 step 之间的 cycle_len = step - pre_step 次操作构成一个完整循环
   • 这个循环内糖数增加了 cycle_sum = X - pre_val
   • 剩余操作次数 remain = K - pre_step，我们还可以执行 remain / cycle_len 个完整循环，以及 remain % cycle_len 次零散操作
   • 直接跳到循环结束（或散段结束），不再逐项模拟
3. 如果 seen[r] 没有记录，说明是新状态：
   • 记录 seen[r] = (step, X)
   • 执行一次操作：$X leftarrow X + A[r]$，step++

注意：题目中 $K$ 次操作的含义是"进行 $K$ 次加法"。我们在循环检测时，检测到余数重复意味着下一次要加的数和之前某次完全一样，且当时的总糖数状态也完全一样，所以后续行为必然重复。

循环计算公式

设循环前前缀有 pre_step 次操作，对应糖数 pre_val。

进入循环后，还剩余 remain = K - pre_step 次操作需要执行。

• 完整循环个数：loops = remain / cycle_len
• 完整循环增加的糖数：loops * cycle_sum
• 散段长度：rest = remain % cycle_len

散段需要模拟吗？我们可以预先记录散段中每一步的操作序列，但实际上：

如果我们已经走到了当前 $X$，且知道从 pre_step 到 pre_step + rest 这 rest 步怎么走的……

等等，这里有个技巧：我们在检测到循环时，已经执行完了 step 次操作，当前糖数是 $X$。 检测到循环意味着"如果现在继续操作，将会和历史上某一段完全重复"。

更好的写法：我们在执行操作前检查当前余数是否出现过。

• 若未出现，记录当前 (step, X)，然后执行操作
• 若已出现，说明从上次记录点到当前点之间是一个循环

这样更清晰：

设上次记录余数 $r$ 时：

• 已执行 pre_step 次操作
• 当时糖数为 pre_val

当前状态：

• 已执行 step 次操作
• 当前糖数为 $X$

则从 pre_step 次操作后到 step 次操作前，中间经历了 cycle_len = step - pre_step 次操作，糖数从 pre_val 增加到 $X$，增加了 cycle_sum = X - pre_val。

此时还剩 remain = K - step 次操作未执行（注意！是当前状态之后还剩这么多）。

我们可以：

1. 跳过 loops = remain / cycle_len 个完整循环：$X += loops times cycle_sum$，step += loops \times cycle_len
2. 然后还剩 rest = remain % cycle_len 次操作，因为最多 $N$ 次，直接模拟即可

复杂度

• 时间：$O(N)$，最多遍历 $N$ 个不同余数
• 空间：$O(N)$

---

代码实现（逐行解释）

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;   // K 最大 1e12，糖数总和可能极大，全部用 long long

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

    int N;          // 数组长度，最大 2e5
    ll K;           // 操作次数，最大 1e12，必须用 long long
    cin >> N >> K;

    vector<ll> A(N);    // 数组 A[0..N-1]
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    // ---------- 记录每个余数第一次出现的时机 ----------
    // seen[r] = pair(第一次出现的操作次数 step, 第一次出现时的糖数 X)
    // 用 vector，初始化一个标记表示"未出现过"
    // 因为 step 从 0 开始，可以用 step = -1 作为未出现的标记
    vector<ll> seen_step(N, -1);   // seen_step[r] 表示余数 r 第一次出现时的操作次数
    vector<ll> seen_val(N, 0);     // seen_val[r] 表示余数 r 第一次出现时的糖数

    ll X = 0;       // 当前盘子里的糖数，初始为 0
    ll step = 0;    // 已经执行完成的操作次数

    while (step < K) {
        int r = X % N;              // 计算当前余数，决定加 A 的哪个元素

        if (seen_step[r] != -1) {
            // 这个余数之前出现过！循环节找到了
            ll pre_step = seen_step[r];  // 上次出现时的操作次数
            ll pre_val = seen_val[r];    // 上次出现时的糖数

            // 循环节长度：从上一次到当前，中间有多少次操作
            ll cycle_len = step - pre_step;
            // 这 cycle_len 次操作让糖数增加了多少
            ll cycle_sum = X - pre_val;

            // 还剩多少次操作没执行
            ll remain = K - step;

            // 可以跳过的完整循环个数
            ll loops = remain / cycle_len;
            // 直接加上这些完整循环的贡献
            X += loops * cycle_sum;
            // 跳过这些操作次数
            step += loops * cycle_len;

            // 现在还剩 rest 次零散操作（最多 cycle_len-1 次，不超过 N，很小）
            ll rest = remain % cycle_len;
            // 零散操作直接模拟
            for (ll i = 0; i < rest; i++) {
                r = X % N;          // 重新计算余数
                X += A[r];          // 执行一次操作
                step++;             // 操作次数 +1
            }

            break;  // 所有 K 次操作已经完成，退出循环
        } else {
            // 这个余数第一次出现，记录下来
            seen_step[r] = step;
            seen_val[r] = X;

            // 执行一次正常操作
            X += A[r];
            step++;
        }
    }

    cout << X << '\n';
    return 0;
}