Submission #8622850

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <string>
#include <random>
#include <stack>
#include <set>
#include <unordered_set>

#define bug(x) cout<<"zdongdebug: "<<x<<endl;
#define bug2(x, y) cout<<"zdongdebug: "<<x<<" "<<y<<endl;
using namespace std;
typedef long long ll;
const int maxn = 200005;
const int mod = 1000000007;

ll s[maxn];

int main() {
#ifdef suiyuan2009
  freopen("/Users/suiyuan2009/CLionProjects/icpc/input.txt", "r", stdin);
  //freopen("/Users/suiyuan2009/CLionProjects/icpc/output.txt", "w", stdout);
#endif
  unordered_map<int,int>mp;
  int n,K;
  cin>>n>>K;
  mp[0] = 1;
  ll sum = 0,ret = 0;
  for(int i=1;i<=n;i++){
    if(i>=K){
      mp[s[i-K]%K-(i-K)]--;
    }
    int x;
    cin>>x;
    sum+=x;
    s[i] = sum;
    int tt = sum%K-i;
    //bug2(i,tt)
    ret+=mp[tt];
    tt = sum%K - i + K;
    ret+=mp[tt];
    //if(i==5)bug2(tt,mp[tt]);
    mp[sum%K-i]++;
  }
  if(K==1)ret=0;
  cout<<ret<<endl;
  return 0;
}

Submission Info

Judge Result