题解：AT_abc367_d [ABC367D] Pedometer

Acord245 · 2024-08-18 09:14:29 · 题解

套路题

是 m 的倍数即在 mod \; m 意义下为 0 。区间问题转化为前缀问题。令 s_i 为前缀和。一段区间 l ~ r 合法当且仅当 s_{l-1} \equiv s_r(mod\; m) 。直接开一个桶计数。环问题直接破环为链即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch)) {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch)) {
        x =  x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
const int N = 4e5 + 100;
int n, m, ans, a[N], s[N], t[N * 5];
signed main() {
    n = read(), m = read();
    for(int i = 1; i <= n; ++i) a[i] = a[i + n] = read();
    for(int i = 1; i <= n * 2; ++i) s[i] = (s[i - 1] + a[i]) % m;
    for(int i = 1; i <= n * 2; ++i) {
        if(i > n) --t[s[i - n]];
        ans += t[s[i]];
        if(i <= n) ++t[s[i]];
    }
    cout << ans << '\n';
    return 0;
}