题意简述

给定序列 $a_1,\dots,a_n$，每个位置 $i$ 可以花费 $c_i$ 将 $a_i$ 修改为任意非负整数。求最小总代价，使得修改后所有前缀和 $s_i = \sum_{j=1}^i a_j$ 都不是 $r$ 的倍数。

关键观察

观察 1：修改 = 重置前缀和。 修改位置 $j$ 后，前缀和 $s_j$ 可以变成任意一个非零余数（因为 $a_j$ 可以改成任意值，$s_j = s_{j-1}+a_j$ 的余数可自由选择）。而 $j$ 之后的位置若不再修改，其前缀和等于 $s_j$ 加上确定的偏移量。

观察 2：段分割。 我们把被修改的位置称为"修改点"。相邻两个修改点（以及起点 $0$ 与第一个修改点、最后一个修改点与终点 $n$）之间是一段"不修改"的连续区间。段内所有位置的前缀和，等于段起点的前缀和加上段内的连续和。

观察 3：段可行的充要条件。 考虑从修改点 $j$ 出发、到下一个修改点 $i-1$ 结束（不修改 $j+1,\dots,i-1$）的一段。段起点前缀和 $s_j$ 可自由取任意非零值，需避开使得段内某前缀和变为 $0$ 的那些取值。

设初始前缀和 $S_0=0,\ S_t=(S_{t-1}+a_t)\bmod r$。段内位置 $t\in[j,i-1]$ 的前缀和（修改 $j$ 后整体加 $\Delta$）为 $S_t+\Delta$，要求不为 $0$，即 $\Delta \ne -S_t$。

$\Delta$ 有 $r-1$ 个非零选择，被禁止的选择对应 $S_t$ 的不同取值。因此：

段可行 ⟺ 区间 $[j,i-1]$ 内不同前缀和 $S_t$ 的数量 $< r$。

证明：区间内不同 $S_t$ 有 $D$ 个，则禁止的 $\Delta$ 至多 $D$ 个（其中 $S_t=0$ 对应 $\Delta=0$，本就非零选择之外）。需要存在非零 $\Delta$ 未被禁止，即 $D \le r-1$，等价于 $D<r$。

观察 4：起点段特殊。 起点 $0$ 处 $S_0=0$ 是固定的（不能自由选择），因此第一段（从 $0$ 到第一个修改点）要求 $S_1,S_2,\dots$ 都非零，这是确定的判断。

算法

设 $dp[i]$ 表示"位置 $i$ 是修改点"的最小代价（$dp[0]=0$ 表示起点）。

转移：

$$dp[i] = c_i + \min\left(\underbrace{[S_1\dots S_{i-1}\text{ 都非零}]\cdot dp[0]}_{\text{起点段}},\ \min_{\substack{1\le j<i \\ [j,i-1]\text{ 不同 }S<r}} dp[j]\right)$$

最终答案为：

$$\min\left([S_1\dots S_n\text{ 都非零}]\cdot 0,\ \min_{\substack{1\le j\le n \\ [j,n]\text{ 不同 }S<r}} dp[j]\right)$$

优化

• $r>n$ 时：任意区间的不同前缀和数量 $\le$ 区间长度 $\le n<r$，故所有段都可行。此时只需在第一个"坏点"（$S_i=0$）之前选择一个最小 $c_j$ 修改一次，答案为 $\min_{j=1}^{i_0}c_j$，其中 $i_0$ 是第一个 $S_i=0$ 的位置（若不存在则为 $0$）。

• $r\le n$ 时：用双指针 + 单调队列做到 $O(n)$。固定 $i$，随 $j$ 减小，区间 $[j,i-1]$ 变长，不同前缀和数量单调不减，故可行 $j$ 是连续区间 $[L,i-1]$。用双指针维护 $L$（窗口 $[L,i-1]$ 内不同 $S$ 数量 $<r$），用单调队列维护窗口内 $dp$ 的最小值。

复杂度

• 时间复杂度： $O(n)$（$r\le n$ 时双指针+单调队列；$r>n$ 时直接扫描），总复杂度 $O(\sum n)$。
• 空间复杂度： $O(n+r)$。

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 4e18;

void solve() {
    int n; ll r;
    scanf("%d%lld", &n, &r);
    vector<ll> a(n + 1), c(n + 1);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for (int i = 1; i <= n; i++) scanf("%lld", &c[i]);

    vector<ll> s(n + 1);
    s[0] = 0;
    for (int i = 1; i <= n; i++) s[i] = (s[i - 1] + a[i]) % r;

    vector<char> ok(n + 1);
    ok[0] = 1;
    int i0 = -1;
    for (int i = 1; i <= n; i++) {
        ok[i] = ok[i - 1] && (s[i] != 0);
        if (s[i] == 0 && i0 == -1) i0 = i;
    }

    if (ok[n]) { printf("0\n"); return; }

    if (r > (ll)n) {
        ll ans = INF;
        for (int i = 1; i <= i0; i++) ans = min(ans, c[i]);
        printf("%lld\n", ans);
        return;
    }

    int R = (int)r;
    vector<int> freq(R, 0);
    int cnt = 0, L = 1;

    vector<ll> dp(n + 1, INF);
    dp[0] = 0;

    deque<int> q;

    for (int i = 1; i <= n; i++) {
        while (!q.empty() && q.front() < L) q.pop_front();

        ll best = INF;
        if (ok[i - 1]) best = 0;
        if (!q.empty()) best = min(best, dp[q.front()]);

        dp[i] = c[i] + best;

        if (freq[s[i]] == 0) cnt++;
        freq[s[i]]++;

        while (cnt >= R && L <= i) {
            freq[s[L]]--;
            if (freq[s[L]] == 0) cnt--;
            L++;
        }

        while (!q.empty() && dp[q.back()] >= dp[i]) q.pop_back();
        q.push_back(i);
    }

    ll ans = INF;
    while (!q.empty() && q.front() < L) q.pop_front();
    if (!q.empty()) ans = min(ans, dp[q.front()]);
    printf("%lld\n", ans);
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}

另一种思路（供参考）

也可以做 $O(n\cdot r)$ 的朴素 DP：设 $f_j$ 表示当前前缀和余数为 $j$ 的最小代价，每次要么"不修改"（余数唯一转移 $(j+a_i)\bmod r$，且结果不能为 $0$），要么"修改"（可达任意非零余数，代价为 $\min f + c_i$）。这在 $r\le 5000$ 时可通过子任务 2。