CCPC 2021 Online E - Monopoly 复盘：周期前缀与同余分组

前言

CCPC 2021 Online E - Monopoly 要回答一个无限循环过程中的最早到达时间。直接模拟无法确定要走多少圈，有限的部分只有一圈中的位置；每走完一圈，分数都会增加同一个周期和。

题目

地图上有首尾相接的 $n$ 个整数 $a_1,a_2,\ldots,a_n$。初始分数为 $0$，第一步走到 $a_1$，以后按顺序循环移动，每一步把当前位置的数加入分数。

每个询问给出目标分数 $x$。需要输出第一次恰好得到 $x$ 时的步数；如果无法到达则输出 $-1$。初始状态已经得到 $0$ 分，所以 $x=0$ 的答案为 $0$。

单个测试中 $n,m\le 10^5$，全部测试的 $n$ 与 $m$ 之和分别不超过 $5\times 10^5$。目标分数的绝对值可以达到 $10^{12}$，不能按步数或周期数枚举。

周期中的位置

定义第一圈的前缀和

$$P_0=0,\qquad P_i=\sum_{j=1}^{i}a_j\quad(1\le i\le n),$$

一整圈带来的分数变化为

$$S=P_n.$$

实现中，pre[i] 保存周期内前缀 $P_i$（$0\le i<n$），s 保存一个完整周期的总和 $S$。

任意时刻都可以唯一写成

$$t=q\cdot n+i,\qquad q\ge 0,\quad 0\le i<n.$$

其中 $q$ 是完整走过的圈数，$i$ 是当前一圈中已经走过的步数。此时分数为

$$q\cdot S+P_i.$$

只保留 $P_0$ 到 $P_{n-1}$。$P_n=S$ 与下一圈开头的 $P_0$ 表示同一个周期边界，若两者同时保留，同一时刻会有两种表示。

对询问 $x$，问题变成寻找满足

$$x=q\cdot S+P_i,\qquad q\ge 0$$

的周期内位置 $i$，并最小化 $q\cdot n+i$。

周期和为零

若 $S=0$，完整走一圈不会改变分数：

$$q\cdot S+P_i=P_i.$$

所有可达分数都已经出现在第一圈。对于每个前缀和，只记录它最早出现的步数；询问时在哈希表中查找即可。初始前缀 $P_0=0$ 对应步数 $0$。

同一个前缀和以后再次出现时步数更大，不会成为答案。

这张“前缀和到最早位置”的映射由 f1st 保存。建表时只在前缀和第一次出现时写入，solve1 查询到的自然就是最早步数：

if (!f1st.count(s)) {
    f1st[s] = i;
}

按同余分组

下面考虑 $S\ne 0$，令

$$d=\lvert S\rvert.$$

完整周期带来的变化是 $d$ 的整数倍。一个周期内前缀 $P_i$ 能产生目标 $x$，必要条件为

$$P_i\equiv x\pmod{d}.$$

把前缀按模 $d$ 的非负余数分组。固定一组余数 $r$，可以写成

$$0\le r<d,\qquad P_i=r+k_i\cdot d,\qquad x=r+h\cdot d,\qquad k_i,h\in\mathbb{Z}.$$

同余条件保证所需圈数是整数，剩下的限制是 $q\ge 0$。周期和的正负决定了合法前缀位于排序后数组的哪一侧。

实现时，mod 把负余数统一到 $[0,d)$，same_rem 按余数保存候选前缀。每个候选的第一项是 $P_i$，第二项 val 在下面两个分支中分别保存对应的步数补偿项。

周期和为正

此时 $S=d$。代入

$$x=P_i+q\cdot S$$

可得

$$q=h-k_i.$$

合法条件为

$$q\ge 0 \iff k_i\le h \iff P_i\le x.$$

对应步数为

$$\begin{aligned} q\cdot n+i &=(h-k_i)\cdot n+i\\ &=h\cdot n+(i-k_i\cdot n). \end{aligned}$$

对于固定询问，$h\cdot n$ 不变。将同余组内的前缀按 $P_i$ 升序排列，并对

$$i-k_i\cdot n$$

维护前缀最小值。查询时用二分找到最后一个不大于 $x$ 的前缀，取该位置以前的最小值即可。

对应到实现，val = i - k * n 保存 $i-k_i\cdot n$，best 保存按 $P_i$ 排序后的前缀最小值。upper_bound 定位最后一个满足 $P_i\le x$ 的位置，答案写成 h * n + best[rem][idx]。若组内最小的前缀都大于 $x$，则不存在合法的非负圈数。

周期和为负

此时 $S=-d$，等式变为

$$x=P_i-q\cdot d.$$

因此

$$q=k_i-h,$$

合法条件为

$$q\ge 0 \iff k_i\ge h \iff P_i\ge x.$$

步数可以写成

$$\begin{aligned} q\cdot n+i &=(k_i-h)\cdot n+i\\ &=-h\cdot n+(i+k_i\cdot n). \end{aligned}$$

同余组仍按 $P_i$ 升序排列，但这次合法候选构成一个后缀。对

$$i+k_i\cdot n$$

维护后缀最小值，查询时用 lower_bound 找到第一个不小于 $x$ 的前缀，再读取对应的后缀最小值。

这里的补偿项对应 val = i + k * n，best 保存后缀最小值，最终答案为 -h * n + best[rem][idx]。正负两种情况共用同余分组，只改变合法区间方向和维护的最小值方向。

若组内最大的前缀仍小于 $x$，目标同样不可达。

实现边界

C++ 的负数取模可能得到负余数。分组时统一使用

$$((v\bmod d)+d)\bmod d$$

把余数放到 $[0,d)$，负前缀和负询问才能进入同一组。

同一个前缀值可以出现多次，不需要去重。前缀或后缀最小值会自动保留步数更早的候选。

查询 $x=0$ 时直接输出 $0$。后续即使再次回到零分，也不可能早于初始状态。

前缀和、询问、商和步数表达式都可能超过 int 范围，统一使用 long long。

复杂度

当 $S=0$ 时，建立最早前缀位置的哈希表平均需要 $O(n)$，每个询问平均为 $O(1)$。

当 $S\ne 0$ 时，所有分组的排序合计为 $O(n\log n)$，构造最小值数组还需要 $O(n)$。一次询问先通过哈希表选出同余组，再在组内二分合法区间，因此总时间复杂度平均为

$$O(n\log n+m\log n),$$

空间复杂度为 $O(n)$。

AC 代码

点击展开/折叠 最终 AC 代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int maxn = 1e5 + 5;

int t;

ll mod(ll a, ll b) {
    return (a % b + b) % b;
}

void solve1(int m, unordered_map<ll, int> &f1st) {
    f1st[0] = 0;
    for (int i = 1; i <= m; i++) {
        ll x;
        cin >> x;
        if (f1st.count(x)) {
            cout << f1st[x] << '\n';
        } else {
            cout << -1 << '\n';
        }
    }
}

void solve2(int n, int m, ll s, vector<ll> &pre, unordered_map<ll, vector<pair<ll, ll> > > &same_rem) {
    for (int i = 0; i < n; i++) {
        ll rem = mod(pre[i], abs(s));
        ll k = (pre[i] - rem) / abs(s);
        ll val;
        if (s > 0) {
            val = i - k * n;
        } else {
            val = i + k * n;
        }
        same_rem[rem].push_back({pre[i], val});
    }
    unordered_map<ll, vector<ll> > best;
    for (auto &um: same_rem) {
        ll rem = um.first;
        sort(um.second.begin(), um.second.end());
        int size = um.second.size();
        best[rem] = vector<ll>(size);
        if (s > 0) {
            best[rem][0] = um.second[0].second;
            for (int i = 1; i < size; i++) {
                best[rem][i] = min(best[rem][i - 1], um.second[i].second);
            }
        } else {
            best[rem][size - 1] = um.second[size - 1].second;
            for (int i = size - 2; i >= 0; i--) {
                best[rem][i] = min(best[rem][i + 1], um.second[i].second);
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        ll x;
        cin >> x;
        if (!x) {
            cout << 0 << '\n';
            continue;
        }
        ll d = abs(s);
        ll rem = mod(x, d);
        if (!same_rem.count(rem)) {
            cout << -1 << '\n';
            continue;
        }
        auto &v = same_rem[rem];
        if (s > 0) {
            int idx = upper_bound(v.begin(), v.end(), x, [](ll val, const auto &p) {
                return val < p.first;
            }) - v.begin() - 1;
            if (idx < 0) {
                cout << -1 << '\n';
                continue;
            }
            ll h = (x - rem) / s;
            cout << h * n + best[rem][idx] << '\n';
        } else {
            int idx = lower_bound(v.begin(), v.end(), x, [](const auto &p, ll val) {
                return p.first < val;
            }) - v.begin();
            if (idx == (int) v.size()) {
                cout << -1 << '\n';
                continue;
            }
            ll h = (x - rem) / d;
            cout << -h * n + best[rem][idx] << '\n';
        }
    }
}

void op() {
    int n, m;
    cin >> n >> m;
    ll s = 0;
    vector<int> a(n + 5);
    vector<ll> pre(n + 5, 0);
    unordered_map<ll, int> f1st;
    unordered_map<ll, vector<pair<ll, ll> > > same_rem;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s += a[i];
        if (!f1st.count(s)) {
            f1st[s] = i;
        }
        if (i != n) {
            pre[i] = s;
        }
    }
    if (!s) {
        solve1(m, f1st);
    } else {
        pre[0] = 0;
        solve2(n, m, s, pre, same_rem);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t;
    while (t--) {
        op();
    }
    return 0;
}