桶

EricWan · 2024-08-18 10:34:15 · 题解

开一个桶，记录 1 走到每个点的距离模 m 的值，新来一个点，计算它前面有几个点与它有合法关系，如果向后绕一圈，它前面有几个点与它有合法关系。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, suma, sum, ans, box[10000005], a[10000005], sur[10000005], pre[10000005];
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        suma += a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    for (int i = n; i >= 1; i--) {
        sur[i] = sur[i + 1] + a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
        sum %= m;
        ans += box[sum];
        ans += box[(m - sur[i + 1] % m) % m];
        box[sum]++;
    }
    cout << ans;
    return 0;
}