考试的时候想了好久都没想出正解 >_<
后来一听正解觉得很简单。。。只怪当时没想到
对前缀和取余
对于两个余数相等的前缀和 sum[i] 和 sum[j]
子串 i~j 即为符合条件子串
注意要处理有负数的情况 要保证每个前缀和取余后都要为正
最后对于余0的再加一遍即可
1 #include <cstring> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5 #define N 500500 6 typedef long long LL; 7 8 int n,k; 9 int num[N]; 10 int sum[N]; 11 LL ans; 12 13 int main() { 14 scanf("%d%d",&n,&k); 15 sum[0]=0; 16 memset(num,0,sizeof(num)); 17 for (int i=1;i<=n;i++) { 18 scanf("%d",&sum[i]); 19 sum[i]=sum[i]%k; 20 if (sum[i]<0) sum[i]+=k; 21 sum[i]=(sum[i]+sum[i-1])%k; 22 ans+=num[sum[i]]; 23 num[sum[i]]++; 24 } 25 ans+=num[0]; 26 printf("%lld",ans); 27 }