本文主要是介绍D - Pedometer AtCoder Beginner Contest 367,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意:
一个长度为n的数组a首尾相接,求满足a[i]~a[j]的和是m的倍数的[i,j]对数
思路:
由于首位相接,那么区间i-->j的所有数有两种情况:第一种是i<j的情况,第二种是i>j的情况
为了简化处理,我们可以将他变为一个线性数组,也就是原数组的后面再加一个原数组,那么新数组的所有区间就包含了以上两种情况:
设s[i]为前缀和数组,a[i]到a[j]的数的和是m的倍数--->(s[j]-s[i-1])%m=0-->s[i-1]%m=s[j]%m
那么就转换为求满足s[j-1]%m=s[i]%m的i和j的对数
先寻找i<j的[i,j]对:
设s[i]%m=k,那么我们用d[k]来记录从第一个位置到当前位置的所有满足s[i]%m=k的i的个数
那么我们对于当前位置i,可以算出满足s[i]%m=s[j]%m且j<i的个数,即d[s[i]%m]
那么对于j>i的情况,j和i之间间隔的长度不能大于数组长度,否则会重复
那么我们每次到i的时候将前面与他间隔长度大于n的数都删除
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10;
int n,m;
typedef long long ll;
ll a[N],s[N];
map<ll,ll> mp;
int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]+a[i];a[i+n]=a[i];}for(int i=1+n;i<=2*n;i++)s[i]=s[i-1]+a[i];ll ans=0;for(int i=1;i<=n;i++){ll x=s[i]%m;if(mp.count(x)){ans+=mp[x];}mp[x]++;}for(int i=1,j=1+n;i<=n;i++,j++){ll x=s[i]%m;mp[x]--;ll xx=s[j]%m;ans+=mp[xx];}cout<<ans;return 0;
}
这篇关于D - Pedometer AtCoder Beginner Contest 367的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!