多多路上从左到右有N棵树(编号1~N),其中第i个颗树有和谐值Ai。
多多鸡认为,如果一段连续的树,它们的和谐值之和可以被M整除,那么这个区间整体看起来就是和谐的。现在多多鸡想请你帮忙计算一下,满足和谐条件的区间的数量。
第一行,有2个整数N和M,表示树的数量以及计算和谐值的参数。
( 1 <= N <= 100,000, 1 <= M <= 100 )
第二行,有N个整数Ai, 分别表示第i个颗树的和谐值。
( 0 <= Ai <= 1,000,000,000 )
共1行,每行1个整数,表示满足整体是和谐的区间的数量。
5 2 1 2 3 4 5
6
长度为1: [2], [4]
长度为2: 无
长度为3: [1,2,3], [3,4,5]
长度为4: [1,2,3,4], [2,3,4,5]
长度为5: 无
共6个区间的和谐值之和可以被2整除。
对于50%的数据,有N<=1,000对于100%的数据,有N<=100,000
private static int f(int[] arr,int mod){ int n = arr.length,count=0; //c代表区间长度 for(int c=1;c<=n;c++){ //区间开始结束值以及区间和的大小 int end=0,start=0; long sum=0; while (end<c-1){ sum+=arr[end++]; } //从左到右“滑动区间”并计算是否满足条件 while (end<n){ sum+=arr[end++]; if(sum%mod==0){ count++; } sum-=arr[start++]; } } return count; }
private static int f(int[] arr,int mod){ long[] prefix=new long[arr.length+1]; int k=1; for(int i : arr){ prefix[k]=prefix[k-1]+i; k++; } int n = arr.length,count=0; for(int c=1;c<=n;c++){ int start=0; int end = start+c-1; if(end<n){ while(end<n){ if((prefix[end+1]-prefix[start])%mod==0){ count++; } start++;end++; } }else { break; } } return count; }
private static long f(int[] arr,int mod){ long[] prefix=new long[arr.length]; prefix[0]=arr[0]; Map<Long,Long> map = new HashMap<>(); map.put(prefix[0]%mod,1L); for(int i=1;i<arr.length;i++){ prefix[i]=prefix[i-1]+arr[i]; map.put(prefix[i]%mod,map.getOrDefault(prefix[i]%mod,0L)+1); } return map.values().stream().mapToLong(n->n*(n-1)/2).sum() +map.getOrDefault(0L,0L); //需要加上单值区间直接可以mod到0的情况 }