题解：AT_abc367_d [ABC367D] Pedometer

fantastic_dream · 2024-08-18 19:47:27 · 题解

解答

对于跨越边界的情况，先复制下步数序列把环转成序列，然后做出其前缀和。可以知道，如果点对 (s,t) 中 s 能走到 t，且步数前缀和模 M 的余数相等，则该点对合法。注意到模数不大，直接开个桶记录每个模数对应的 s 的个数，每次答案加上这个个数即可，注意不要重复计算，只需要把原序列记入桶中。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int ma=4e5+5;
int n,sz[ma],sum[ma],ans,p[ma*3],m;
main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>sz[i];
        sz[n+i]=sz[i];
        sum[i+1]=sum[i]+sz[i];
    }
    for(int i=n;i<n+n-1;i++)    sum[i+1]=sum[i]+sz[i];
    for(int i=1;i<n+n;i++){
        if(i>n) p[sum[i-n]%m]--;
        ans+=p[sum[i]%m];
        if(i<=n)    p[sum[i]%m]++;
    }
    cout<<ans;
    return 0;
}