D - Pedometer （abc367）

题意：有n个休息取，休息区按顺时针顺序编号为1，2，。。N从休息区i顺时针到i+1需要ai步，从休息区s顺时针到休息区t的最小步数是m的倍数，求（s，t）的可能对数

分析：前缀和为p，pt-ps为m的倍数，ps%m==pt%m，统计pi%m的个数即可，s到t之间不超过n个休息区

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
int main(){cin>>n>>m;ll a[n+10],cnt[m+10];memset(cnt,0,sizeof(cnt));ll sum=0,ans=0;for(int i=1;i<=n;i++){cin>>a[i];ans+=cnt[sum%m];cnt[sum%m]++;sum+=a[i];}ll s=sum;sum=0;for(int i=1;i<=n;i++){cnt[sum%m]--;ans+=cnt[s%m];s+=a[i];sum+=a[i];}cout<<ans<<endl;
}