fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5. int n,k;
  6. cin>>n>>k;
  7.  
  8. vector<int> numbers(n);
  9.  
  10. for(auto& number: numbers){
  11. cin>>number;
  12. }
  13.  
  14. int answer = 0;
  15.  
  16. unordered_map<int,int> prefixSum;
  17.  
  18. prefixSum[0] = 1;
  19.  
  20. int sum = 0;
  21.  
  22.  
  23. for(int i=0; i<n; i++){
  24. sum += numbers[i];
  25.  
  26.  
  27. if(prefixSum.find((sum%k - i%k - 1 + k)%k) != prefixSum.end()){
  28. answer+=prefixSum[(sum%k-i%k-1+k)%k];
  29. }
  30.  
  31. prefixSum[(sum%k-i%k-1+k)%k]++;
  32. }
  33.  
  34. cout << answer;
  35.  
  36. return 0;
  37. }
Success #stdin #stdout 0s 5324KB
stdin
5 4 
1 4 3 2 4
stdout
2