Problem:
 Score : 500 points    Problem Statement Given are a sequence of N positive integers A_1, A_2, \ldots, A_N , and a positive integer K .  Find the number of non-empty contiguous subsequences in A such that the remainder when dividing the sum of its elements by K is equal to the number of its elements. We consider two subsequences different if they are taken from different positions, even if they are equal sequences.      Constraints  All values in input are integers.  1 \leq N \leq 2\times 10^5  1 \leq K \leq 10^9  1 \leq A_i \leq 10^9         Input Input is given from Standard Input in the following format:  N  K  A_1  A_2  \cdots  A_N       Output Print the number of subsequences that satisfy the condition.        Sample Input 1 5 4
1 4 2 3 5      Sample Output 1 4  Four sequences satisfy the condition: (1) , (4,2) , (1,4,2) , and (5) .       Sample Input 2 8 4
4 2 4 2 4 2 4 2      Sample Output 2 7  (4,2) is counted four times, and (2,4) is counted three times.       Sample Input 3 10 7
14 15 92 65 35 89 79 32 38 46      Sample Output 3 8

Solution (Python):
from collections import Counter

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

ans = 0
c = Counter()
c[0] = 1

S = [0] * (N+1)
s = 0

for idx, a in enumerate(A):
    idx += 1

    if idx >= K: c[S[idx-K]] -= 1
        
    s = (s+a) % K
    
    b = (s - idx) % K
    S[idx] = b    
    ans += c[b]
    c[b] += 1
    
print(ans)

Solution (Python):
from collections import defaultdict

n, k = map(int, input().split())
A = list(map(int, input().split()))

accm = [0] * (n + 1)
for i in range(n):
  accm[i + 1] = accm[i] + A[i]
  
li = [(val - itr) % k for itr, val in enumerate(accm)]

ans = 0
box = defaultdict(int)

for i in range(n + 1):
  if i >= k:
    box[li[i - k]] -= 1
  ans += box[li[i]]
  box[li[i]] += 1

print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    

    
    

    n,k = map(int, input().split())
    a = [0] + list(map(int, input().split()))
    a = list(accumulate(a))
    d = {}
    res = 0
    for i in range(n+1):
        b = (i - a[i]) % k
        if i - k < 0:
            if b not in d:
                d[b] = 1
            else:
                res += d[b]
                d[b] += 1
        else:
            j = i - k
            c = (j - a[j]) % k
            d[c] -= 1
            if b not in d:
                d[b] = 1
            else:
                res += d[b]
                d[b] += 1
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
N,K=map(int,input().split())
alist=list(map(int,input().split()))


slist=[0]
for i in range(N):
  slist.append(slist[-1]+alist[i])


sslist=[]
for i in range(N+1):
  sslist.append((slist[i]-i)%K)


answer=0
si_dic=defaultdict(int)
for i in range(N+1):
  if i-K>=0:
    si_dic[sslist[i-K]]-=1
    
  answer+=si_dic[sslist[i]]
  si_dic[sslist[i]]+=1
  
print(answer)

Solution (Python):
from collections import defaultdict
import itertools


n,k= map(int, input().split())
a= list(map(int, input().split()))
a=[0]+list(itertools.accumulate(a))
b=[0]*(n+1)
for i,x in enumerate(a):
    b[i]=(x-i)%k
d=defaultdict(int)
ans=0
for i in range(n+1):
    if i>=k:
        d[b[i-k]]-=1
    ans+=d[b[i]]
    d[b[i]]+=1
print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import defaultdict
from itertools import accumulate

n, k = map(int, readline().split())
a = list(map(lambda x: int(x) - 1, readline().split()))
cumsum = [0] + list(map(lambda x: int(x) % k, list(accumulate(a))))
dict = defaultdict(int)
ans = 0
for i, v in enumerate(cumsum):
    ans += dict[v]
    dict[v] += 1
    if i >= k - 1:
        dict[cumsum[i - k + 1]] -= 1
print(ans)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * (n + 1)
for i in range(1, n + 1):
    b[i] = b[i - 1] + a[i - 1]
for i in range(n + 1):
    b[i] -= i
    b[i] %= k
d = dict()
for i in range(min(n + 1, k)):
    if b[i] in d:
        d[b[i]] += 1
    else:
        d[b[i]] = 1
ans = []
j = min(n + 1, k)
for i in range(n):
    ans.append(d[b[i]])
    d[b[i]] -= 1
    if j <= n:
        if b[j] in d:
            d[b[j]] += 1
        else:
            d[b[j]] = 1
    j += 1
ans = sum(ans) - n
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

N, K = map(int, input().strip().split(" "))
A = list(map(int, input().strip().split(" ")))
A = [0] + A
for i in range(1, N + 1):
    A[i] += A[i - 1]
    A[i - 1] -= i - 1
A[N] -= N

rem_count = {}
rem_count[0] = 1
ans = 0
for i in range(1, N + 1):
    if i - K >= 0:
        rem_count[A[i - K] % K] -= 1
    if A[i] % K in rem_count:
        ans += rem_count[A[i] % K]
        rem_count[A[i] % K] += 1
    else:
        rem_count[A[i] % K] = 1

print(ans)

Solution (Python):
import itertools
from collections import defaultdict

n,k = map(int,input().split())
lis = list(map(int,input().split()))
lis = [0] + [lis[i]-1 for i in range(n)]

ruiseki = list(itertools.accumulate(lis))

ruiseki = [x % k for x in ruiseki]
  

counter = defaultdict(int)
ans = 0

for i,x in enumerate(ruiseki):
    ans += counter[x]
    counter[x] += 1
    if i >= k-1:
        counter[ruiseki[i-k+1]] -= 1

print(ans)

Solution (Python):
import numpy as np
from collections import defaultdict,deque
N,K= map(int,input().split())
A = np.array([1]+list(map(int,input().split())))-1

Acs = np.cumsum(A)
Acs %= K

ans = 0
cnt = defaultdict(deque)
for i,c in enumerate(Acs):
    cnt[c].append(i)
    while cnt[c]:
        if i-cnt[c][0]> K-1:
            cnt[c].popleft()
        else:
            break
    ans += len(cnt[c]) - 1
print(ans)

Solution (Python):
"""
(sum(j) - sum(i)) % K = j - i
sum(j) % K - sum(i) % K = j- i
j - i < K
"""
n, k = map(int,input().split())
al = list(map(int,input().split()))

import itertools
al_ac = [0] + list(itertools.accumulate(al))

for i in range(n+1):
    al_ac[i] = (al_ac[i] - i) % k

from collections import defaultdict
dic = defaultdict(int)

ans = 0
for i in range(n+1):
    ans += dic[al_ac[i]]
    dic[al_ac[i]] += 1
    if i - k+1 >= 0:
        dic[al_ac[i-k+1]] -= 1

print(ans)

Solution (Python):
n,k=map(int,input().split())
a=[0]+list(map(int,input().split()))
from collections import defaultdict
d=defaultdict(int)
d[0]=1
ans=0
for i in range(1,n+1):
    a[i]+=a[i-1]-1
    if i>=k:
        d[a[i-k]]-=1
    a[i]%=k
    d[a[i]]+=1
    ans+=d[a[i]]-1
print(ans)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))

s = [0]
for i in range(n):
    s.append((s[-1] + a[i] - 1) % k)


dic = {0:1}
ans = 0
if n < k:
    for i in range(1, n+1):
        if s[i] in dic:
            ans += dic[s[i]]
            dic[s[i]] += 1
        else:
            dic[s[i]] = 1

else:
    for i in range(1, k):
        if s[i] in dic:
            ans += dic[s[i]]
            dic[s[i]] += 1
        else:
            dic[s[i]] = 1

    for i in range(k, n+1):
        dic[s[i-k]] -= 1
        if s[i] in dic:
            ans += dic[s[i]]
            dic[s[i]] += 1
        else:
            dic[s[i]] = 1

print(ans)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))

s = [0]
for i in range(n):
    s.append((s[-1] + a[i] - 1) % k)


dic = {0:1}
ans = 0
if n < k:
    for i in range(1, n+1):
        if s[i] in dic:
            ans += dic[s[i]]
            dic[s[i]] += 1
        else:
            dic[s[i]] = 1

else:
    for i in range(1, k):
        if s[i] in dic:
            ans += dic[s[i]]
            dic[s[i]] += 1
        else:
            dic[s[i]] = 1

    for i in range(k, n+1):
        dic[s[i-k]] -= 1
        if s[i] in dic:
            ans += dic[s[i]]
            dic[s[i]] += 1
        else:
            dic[s[i]] = 1

print(ans)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
X = [0 for _ in range(N)]
D = {0: [-1]}
E = {0: 1}
X[0] = (A[0] - 1) % K
if X[0] in D:
  D[X[0]].append(0)
  E[X[0]] += 1
else:
  D[X[0]] = [0]
  E[X[0]] = 1
for i in range(1, N):
  X[i] = (X[i-1] + A[i] - 1) % K
  if X[i] in D:
    D[X[i]].append(i)
    E[X[i]] += 1
  else:
    D[X[i]] = [i]
    E[X[i]] = 1
S = 0
for i in D:
  n = E[i]
  if n > 1:
    L = D[i][:]
    m = L[-1]
    for j in range(n-1):
      x = L[j]
      if m - x < K:
        S += n - 1 - j
      else:
        l, r = j, n
        d = (l + r) // 2
        tmp = 2 * n
        while tmp != 0:
          if L[d] - x <= K - 1:
            l = d
            d = (l + r) // 2
          else:
            r = d
            d = (l + r) // 2
          tmp //= 2
        S += d - j
print(S)

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))

for i in range(1,N):
    A[i]+=A[i-1]

A.append(0)
A.sort()

A=[((A[i]-i)%K,i) for i in range(0,N+1)]
A.sort()
count=0
s=0
t=1
while N>=t and N>=s:
    if A[t][0]==A[s][0] and K>A[t][1]-A[s][1]:
        t+=1
        if t==N+1:
            count+=((t-s)*(t-s-1))//2
    else:
        count+=t-s-1
        s+=1
        if s==t:
            t+=1

print(count)

Solution (Python):
from collections import defaultdict
from itertools import accumulate

n,k = map(int, input().split())

a = list(map(int,input().split()))
s = list(accumulate([0]+a))
b = [(s[i]-i)%k for i in range(n+1)]

d = defaultdict(int)

for i in range(min(k-1,n+1)):
    d[b[i]]+=1

ans = 0
for i in range(n):
    
    d[b[i]]-=1
    if i+k-1<=n:
        d[b[i+k-1]]+=1
    ans += d[b[i]]

print(ans)

Solution (Python):
from collections import defaultdict
from itertools import accumulate
import bisect


n,k = map(int, input().split())

a = list(map(int,input().split()))

s = list(accumulate([0]+a))

b = [s[i]-i for i in range(n+1)]

d = defaultdict(list)

for i in range(n+1):
    d[b[i]%k].append(i)

ans = 0
for x in d.keys():
    l = d[x]
    for j in range(len(l)):
        y = l[j]
        ans += max(0,bisect.bisect_right(l,k+y-1)-j-1)

print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from collections import defaultdict

def main():
    N,K = map(int,input().split())
    a = list(map(int,input().split()))
    
    d = defaultdict(int)
    cum = [0]
    for i in range(N):
        cum.append((cum[-1]+a[i]-1)%K)
    
    ans = 0
    for i in range(N+1):
        ans += d[cum[i]]
        d[cum[i]] += 1
        if i >= K-1:
            d[cum[i-K+1]] -= 1
    
    print(ans)
    
if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict
n,k = map(int,input().split())
s = [0] + list(map(int,input().split()))
for i in range(n):
    s[i+1] += s[i]
dic = defaultdict(int)
ans = 0
for i in range(n+1):
    x = (s[i]-i) % k
    ans += dic[x]
    dic[x] += 1
    if i >= k-1:
        y = (s[i-k+1]-(i-k+1)) % k
        dic[y] -= 1
print(ans)

Solution (Python):
import sys
def main():
  input=sys.stdin.readline
  n,k=map(int,input().split())
  a=list(map(int,input().split()))
  accum=[0]*n
  accum[0]=a[0]
  d=dict()
  ans=0
  for i in range(1,n):
    accum[i]+=a[i]+accum[i-1]
  accum=[0]+accum
  for j in range(n+1):
    if j-k>=0:
      d[(accum[j-k]-(j-k))%k]-=1
    if (accum[j]-j)%k not in d:
      d[(accum[j]-j)%k]=1
    else:
      ans+=d[(accum[j]-j)%k]
      d[(accum[j]-j)%k]+=1
    
  return print(ans)
if __name__=='__main__':
  main()

Solution (Python):
from bisect import *
n,k = map(int,input().split())
A = list(map(int,input().split()))

s = 0
sl = {0:[0]}
for i in range(n):
    s += A[i] - 1
    s %= k
    if s not in sl.keys():
        sl[s] = []
    sl[s].append(i+1)
ans = 0
for ls in sl.values():
    for i,l in enumerate(ls):
        x = bisect_right(ls, l + k - 1)
        ans += x - i - 1
print(ans)

Solution (Python):
from itertools import accumulate
from collections import defaultdict
import bisect

n,k = map(int, input().split())
a = list(map(int, input().split()))
a = [0] + list(accumulate([(i-1) % k for i in a]))
a = [i % k for i in a]
ans = 0
maps = defaultdict(list)
for k1,v in enumerate(a):
  maps[v].append(k1)
for i in range(n):
  v = a[i]
  ans += bisect.bisect_right(maps[v],i+k-1) - bisect.bisect_right(maps[v],i)
print(ans)

Solution (Python):
from itertools import accumulate
from collections import defaultdict
import bisect

n,k = map(int, input().split())
a = list(map(int, input().split()))
a = [0] + list(accumulate([(i-1) % k for i in a]))
a = [i % k for i in a]
ans = 0
maps = defaultdict(list)
for k1,v in enumerate(a):
  maps[v].append(k1)
for i in range(n):
  v = a[i]
  ans += bisect.bisect_right(maps[v],i+k-1) - bisect.bisect_right(maps[v],i)
print(ans)

Solution (Python):

from collections import defaultdict
n, k = map(int, input().split()) 
nums = [int(i) for i in input().split()] 

nums = [0] + nums
for i in range(n):
    nums[i + 1] = (nums[i] + nums[i + 1] + k - 1) % k
ans = 0
d = defaultdict(int)
for i in range(n + 1):
    ans += d[nums[i]]
    d[nums[i]] += 1
    if i - (k - 1) >= 0:
        d[nums[i - (k - 1)]] -= 1
print(ans)

Solution (Python):
def main():
    n, k = map(int, input().split())
    b = list(map(int, input().split()))
    a = [0]*(n+1)
    for i in range(n):
        a[i+1] = b[i]
    for i in range(n+1):
        if 0 < i:
            a[i] += a[i-1]
        a[i] %= k
    for i in range(1, n+1):
        a[i] = (a[i] - (i%k) + k) % k
    dic = {}
    ans = 0
    l, r = 0, 0

    while r < n+1:
        x = a[r]
        if k <= r-l:
            dic[a[l]] -= 1
            l += 1
        if x in dic.keys():
            ans += dic[x]
            dic[x] += 1
        else:
            dic[x] = 1

        r += 1
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    from collections import defaultdict, deque

    N, K = map(int, input().split())
    a = map(int, input().split())

    def accumulate(a, mod):
        s = 0
        yield s
        for x in a:
            s = (s + x - 1) % mod
            yield s

    acc = accumulate(a, mod=K)

    d = defaultdict(int)
    dq = deque()
    ans = 0
    for x in acc:
        if x in d:  
            ans += d[x]
        d[x] += 1
        dq.append(x)
        if len(dq) >= K:
            r = dq.popleft()
            d[r] -= 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from collections import defaultdict, deque

    N, K = map(int, input().split())
    a = map(int, input().split())

    def accumulate(a, mod):
        s = 0
        yield s
        for x in a:
            s = (s + x - 1) % mod
            yield s

    acc = accumulate(a, mod=K)

    d = defaultdict(int)
    dq = deque()
    ans = 0
    for x in acc:
        ans += d[x]
        d[x] += 1
        dq.append(x)
        if len(dq) >= K:
            r = dq.popleft()
            d[r] -= 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from collections import defaultdict, deque

    N, K = map(int, input().split())
    a = map(int, input().split())

    def accumulate(a, mod):
        s = 0
        yield s
        for x in a:
            s = (s + x - 1) % mod
            yield s

    *acc, = accumulate(a, mod=K)

    d = defaultdict(int)
    dq = deque()
    ans = 0
    for x in acc:
        ans += d[x]
        d[x] += 1
        dq.append(x)
        if len(dq) >= K:
            r = dq.popleft()
            d[r] -= 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter, deque

N, K = map(int, input().split())
A = list(map(int, input().split()))
INF = 10**18

cnt = Counter()
cnt[0] = 1
que = deque([0])
sumR = 0
ans = 0
for right, a in enumerate(A, start=1):
    if len(que) >= K:
        cnt[que.popleft()] -= 1
    sumR = (a + sumR) % K
    D = (sumR - right) % K
    ans += cnt[D]
    cnt[D] += 1
    que.append(D)
print(ans)

Solution (Python):
n,k = map(int,input().split())
a = [0]+list(map(int,input().split()))
for i in range(n):
    a[i+1] += a[i]
    a[i+1] %=k
cnt = {}
ans = 0
for i in range(n+1):
    left = i-k
    if left >=0:
        ldiff = (a[left] - left)%k
        cnt[ldiff] -= 1
    x = (a[i] - i)%k
    if x <0:x+=k
    if x not in cnt:cnt[x] = 0
    ans+= cnt[x]    
    cnt[x] +=1
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
c1=[0]
c2=[k]
s=0
if k==1:
    print(0)
    sys.exit()
for i in range(n):
    s=(s+a[i])%k
    c1.append(s-i-1)
    c2.append(s+k-i-1)
d1={}
for i in range(1,n+1):
    if c1[i] in d1:
        d1[c1[i]]+=1
    else:
        d1[c1[i]]=1
ans=0
for i in range(n):
    if c1[i] in d1:
        ans+=d1[c1[i]]
    d1[c1[i+1]]-=1
d2={}
for i in range(1,min(k,n+1)):
    if c2[i] in d2:
        d2[c2[i]]+=1
    else:
        d2[c2[i]]=1
for i in range(n):
    if c1[i] in d2:
        ans+=d2[c1[i]]
    d2[c2[i+1]]-=1
    if i+k<=n:
        if c2[i+k] in d2:
            d2[c2[i+k]]+=1
        else:
            d2[c2[i+k]]=1
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import *

N, K = map(int, input().split())
A = list(map(int, input().split()))
acc = [0]

for Ai in A:
    acc.append(acc[-1]+Ai)

cnt = defaultdict(int)
ans = 0

for i in range(N+1):
    ans += cnt[(acc[i]-i)%K]
    cnt[(acc[i]-i)%K] += 1
    
    if i>=K-1:
        j = i-(K-1)
        cnt[(acc[j]-j)%K] -= 1

print(ans)

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]


def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,k,*aaa = get_all_int()

ruiseki = [0] * (n+1)
for i,a in enumerate(aaa):
    ruiseki[i+1] = (ruiseki[i] + a - 1) % k

count = {}
ans = 0
for right in range(len(ruiseki)):
    x = ruiseki[right]
    
    count[x] = count.get(x, 0) + 1

    if right >= k:
        y = ruiseki[right-k]
        count[y] -= 1

    ans += count.get(x, 0) - 1

print(ans)

Solution (Python):
from collections import defaultdict
import numpy as np
n,k=map(int,input().split())
a=[0]+list(np.cumsum(list(map(int,input().split()))))

dic = defaultdict(int)
c = 0
for i in range(len(a)):
    p = (a[i] - i) % k
    c += dic[p]
    dic[p] += 1
    if i >= k - 1:
        dic[(a[i - k + 1] - (i - k + 1)) % k] -= 1
print(c)

Solution (Python):
n,k = map(int,input().split())
a = list(map(lambda x: (int(x)-1)%k ,input().split()))

sum_a = sum(a)%k

left = [0] * (n+1)
right = [0] * (n+1)
for i,num in enumerate(a,1):
    left[i] = (left[i-1] + num)%k
for i,num in enumerate(a[::-1],1):
    right[-i-1] = (right[-i] + num)%k

from collections import defaultdict
right_d = defaultdict(int)
right_d_over = defaultdict(int)
ans = 0
for i in range(n,-1,-1):
    ans += right_d[(sum_a - left[i])%k] - right_d_over[(sum_a - left[i])%k]
    right_d[right[i]] += 1
    if( (n-i+1) >= k ):
        right_d_over[right[i+k-1]] += 1

print(ans)

Solution (Python):
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    
    cum = [0] * (n + 1)
    dic = {0:1}
    ans = 0
    for i in range(min(n,k - 1)):
        cum[i + 1] = (cum[i] + a[i])%k
        tmp = (cum[i + 1] - i - 1)%k
        if tmp in dic:
            dic[tmp] += 1
        else:
            dic[tmp] = 1

    for v in dic.values():
        ans += v * (v - 1)//2


    for i in range(max(n - k + 1,0)):
        dic[(cum[i] - i)%k] -= 1
        cum[i + k] = (cum[i + k - 1] + a[i + k - 1])%k
        tmp = (cum[i + k] - i - k)%k
        if tmp in dic:
            ans += dic[tmp]
            dic[tmp] += 1
        else:
            dic[tmp] = 1

    print(ans)
if __name__ =='__main__':
    main()

Solution (Python):
n,k=map(int,input().split())
l=[0]+[i%k-1 for i in list(map(int,input().split()))]
from itertools import accumulate
l=list(accumulate(l))
import collections
d=collections.defaultdict(int)
d[0]+=1
ans=0
for i in range(1,n+1):
    if i>=k:
        d[l[i-k]%k]-=1
    ans+=d[l[i]%k]
    d[l[i]%k]+=1
print(ans)

Solution (Python):
def main():
    N, K  = [int(i) for i in input().split()]
    A  = [int(i) for i in input().split()]
    v = {0: 1}
    n = [0]
    r = 0
    t = 0
    for i, a in enumerate(A, 1):
        if i >= K:
            v[n[i - K]] -= 1
        t += a
        j = (t - i) % K
        r += v.get(j, 0)
        v[j] = v.get(j, 0) + 1
        n.append(j)

    return r


print(main())

Solution (Python):
def main():
    N, K = map(int,input().split())
    A = list(map(int, input().split()))
    s = 0
    d = {}
    d[0] = {0}
    r = 0
    l = [0] * (N + 1)
    for i, v in enumerate(A, start=1):
        if i - K >= 0:
           x = l[i - K]
           d[x].remove(i-K)
        s += v % K
        s %= K
        t = (s - i) % K
        l[i] = t
        if t in d:
            r += len(d[t])
            d[t].add(i)
        else:
            d[t] = {i}
    return r
print(main())

Solution (Python):
from collections import defaultdict
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
S = [0] * (N+1)
T = [0] * (N+1)
for i in range(N):
    S[i+1] = (S[i] + A[i])%K
    T[i+1] = (S[i+1] - (i+1))%K
rest = defaultdict(int)
for i in range(N+1):
    if i < K:
        ans += rest[T[i]]
        rest[T[i]] += 1
    else:
        rest[T[i-K]] -= 1
        ans += rest[T[i]]
        rest[T[i]] += 1
print(ans)

Solution (Python):
import sys
import numpy as np
from collections import defaultdict

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = np.array([1] + lr())
A = (A-1) % K
N += 1

Acum = (A.cumsum() % K).tolist()
answer = 0
dic = defaultdict(int)
for i, cur in enumerate(Acum): 
    answer += dic[cur]
    dic[cur] += 1
    if i >= K-1:
        vanish = Acum[i-(K-1)]
        dic[vanish] -= 1

print(answer)

Solution (Python):
from collections import defaultdict
n,k = map(int,input().split())
l = list(map(int,input().split()))

mod = [0]
for i in range(n):
    a = (l[i]-1)%k
    mod.append((mod[-1]+a)%k)
dic = defaultdict(int)
ans = 0
for i in range(n+1):
    if i < k:
        ans += dic[mod[i]]
        dic[mod[i]] += 1
    else:
        dic[mod[i-k]] -= 1
        ans += dic[mod[i]]
        dic[mod[i]] += 1
    
print(ans)

Solution (Python):
from collections import defaultdict
n,k = map(int,input().split())
l = list(map(int,input().split()))

mod = [0]
for i in range(n):
    a = (l[i]-1)%k
    mod.append((mod[-1]+a)%k)
dic = {0:1}
ans = 0
for i in range(1,n+1):
    if i < k:
        if mod[i] in dic:
            ans += dic[mod[i]]
            dic[mod[i]] += 1
        else:
            dic[mod[i]] = 1
    else:
        dic[mod[i-k]] -= 1
        if mod[i] in dic:
            ans += dic[mod[i]]
            dic[mod[i]] += 1
        else:
            dic[mod[i]] = 1
    
print(ans)

Solution (Python):
n,k = map(int,input().split())
l = list(map(int,input().split()))
mo = [0]
mod = [0]
for i in range(n):
    a = l[i]%k
    mo.append((a+mo[-1])%k)
    mod.append((mo[-1]-(i+1))%k)
dic = {0:1}
le = 1
ans = 0
for i in range(1,n+1):
    if le < k:
        if mod[i] in dic:
            ans += dic[mod[i]]
            dic[mod[i]] += 1
        else:
            dic[mod[i]] = 1
        le += 1
    else:
        dic[mod[i-k]] -= 1
        if mod[i] in dic:
            ans += dic[mod[i]]
            dic[mod[i]] += 1
        else:
            dic[mod[i]] = 1
    
print(ans)

Solution (Python):
from itertools import accumulate
from collections import defaultdict

n, k = map(int, input().split())
a = list(map(int, input().split()))

acc = [0] + list(accumulate(a))
sm = [(e - i) % k for i, e in enumerate(acc)]

d = defaultdict(int)
ans = 0
for r in range(1, n + 1):
    if r - k >= 0:
        e = sm[r - k]
        d[e] -= 1

    e = sm[r - 1]
    d[e] += 1

    e = sm[r]
    ans += d[e]

print(ans)

Solution (Python):
from collections import defaultdict
import bisect

N, K = map(int, input().split())
A = list(map(int, input().split()))

s = 0
S = [0]
for i, a in enumerate(A):
    s += a
    S.append(s % K)

cnt = 0
dic = {}

for i, s in enumerate(S):
    x = (s - i) % K

    if x in dic:
        cnt += dic[x]
        dic[x] += 1
    else:
        dic[x] = 1

    K_prev = i - K + 1

    if K_prev >= 0:
        y = (S[K_prev] - (K_prev)) % K
        dic[y] -= 1


print(cnt)

Solution (Python):
n,k = map(int,input().split())
a = [0]+list(map(int,input().split()))
for i in range(n):
    a[i+1] += a[i]
cnt = {}
ans = 0
for i in range(n+1):
    left = i-k
    if left >= 0:
        ldiff = (a[left] - left)%k
        cnt[ldiff]-=1
    diff = (a[i]-i)%k
    if diff not in cnt:cnt[diff] = 0
    ans += cnt[diff]
    cnt[diff] +=1
print(ans)

Solution (Python):
from itertools import accumulate 
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
S=list(accumulate(A))
S.insert(0,0)

L=[ (s-i)%k  for i,s in enumerate(S)]
def f(l):
    return sum([x*(x-1)//2 for x in l])

from collections import Counter

ans=0
d = Counter(L[1:k])
for i in range(n):
    ans += d[L[i]]
    
    d[L[i+1]] -= 1
    if i+k <= n:
        d[L[i+k]] += 1
print(ans)

Solution (Python):

from collections import defaultdict

n,k = map(int,input().split())
a = list(map(int,input().split()))
cum_sum = [0]*(n+1)
for i in range(n):
  cum_sum[i+1] = (cum_sum[i]+a[i]-1) % k
D = defaultdict(int)

count = 0
for i in range(n+1):
  count += D[cum_sum[i]] 
  D[cum_sum[i]] += 1
  if i-k+1 >= 0:
    D[cum_sum[i-k+1]] -=1
print(count)

Solution (Python):
from collections import defaultdict
n, k = map(int, input().split())
a = list(map(int, input().split()))

d = [0]
for i in a:
    a_i = (d[-1] + i) % k
    d.append(a_i)

ans = 0
counter = defaultdict(int)
for i, s in enumerate(d):
    ans += counter[(s-i) % k]
    counter[(s-i) % k] += 1
    if i - k + 1 >= 0:
        counter[(d[i - k + 1]-i+k-1) % k] -= 1

print(ans)

Solution (Python):
N, K = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
s = [0] * (N+1)

for i in range(N):
    s[i+1] = s[i] + A[i]
    s[i+1] %= K
s.reverse()
for i in range(N+1):
    s[i] += (i%K)
    s[i] %= K

d = {}
ans = 0
for i in range(N+1):
    if s[i] not in d:
        d[s[i]] = 0
    if i >= K:
        d[s[i-K]] -= 1
    ans += d[s[i]]
    d[s[i]] += 1

print(ans)

Solution (Python):
from collections import defaultdict

N,K = map(int,input().split())
A = list(map(int,input().split()))

S = [0]
for i in range(N):
    S.append((S[-1]+A[i]-1)%K)

D = defaultdict(int)

count = 0

for i in range(N+1):
    count += D[S[i]]
    D[S[i]] += 1
    if i-K+1 >= 0:
        D[S[i-K+1]] -= 1

print(count)

Solution (Python):
from itertools import accumulate
from collections import deque
from collections import defaultdict

def func(x):
    return x - 1

def main():
    N, K = map(int, input().split())
    A = list(map(func, map(int, input().split())))
    B = [0] + list(accumulate(A))
    for i in range(N+1):
        B[i] %= K

    Q = deque()
    d = defaultdict(int)
    ans = 0
    for i in range(N+1):
        ans += d[B[i]]
        d[B[i]] += 1
        Q.append(B[i])
        if len(Q) == K:
            a = Q.popleft()
            d[a] -= 1

    print(ans)


    


if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict
import numpy as np
N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
A = np.array(A)
A %= K
A = A.cumsum()
tmp = np.arange(N + 1)

B = (A - tmp) % K

ans = 0
d = defaultdict(int)
for i in range(min(K, N + 1)):
    x = B[i]
    ans += d[x]
    d[x] += 1

if N > K:
    for i in range(K, N + 1):
        x = B[i]
        y = B[i - K]
        d[y] -= 1
        ans += d[x]
        d[x] += 1

print(ans)

Solution (Python):
from collections import *
import copy
N,K=map(int,input().split())
A=list(map(int,input().split()))

lst=[0]
for i in range(0,N):
    lst.append((A[i]%K+lst[i])%K)
for i in range(len(lst)):
    lst[i]-=i
    lst[i]%=K

dic={}
count=0
for i in range(0,len(lst)):
    if lst[i] in dic:
        count+=dic[lst[i]]
        dic[lst[i]]+=1
    else:
        dic.update({lst[i]:1})
    a=i-K+1
    if a>=0:
        dic[lst[a]]-=1
print(count)

Solution (Python):
def main():
    from itertools import accumulate
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    A=list(accumulate(A))
    A=[[(A[i]-i-1)%K,i+1] for i in range(0,N)]
    A.append([0,0])
    A.sort()
    s=1
    start=0
    count=0
    for i in range(0,N):
        if A[i][0]==A[i+1][0]:
            s+=1
        else:
            X=[A[i][1] for i in range(start,start+s)]
            a=0
            b=0
            subcount=0
            while len(X)-1>=a and len(X)-1>=b:
                if K-1>=X[b]-X[a]:
                    b+=1
                else:
                    subcount+=len(X)-b
                    a+=1
            count+=len(X)*(len(X)-1)//2-subcount
            start+=s
            s=1
    X=[A[i][1] for i in range(start,start+s)]
    a=0
    b=0
    subcount=0
    while len(X)-1>=a and len(X)-1>=b:
        if K-1>=X[b]-X[a]:
            b+=1
        else:
            subcount+=len(X)-b
            a+=1
    count+=len(X)*(len(X)-1)//2-subcount
    print(count)

if __name__ == '__main__':
    main()

Solution (Python):
import collections
N, K = map(int, input().split())
A = list(map(int, input().split()))
table = collections.defaultdict(int)

ans = 0
s = [0]*(N+1)
a = set()
for i in range(N):
    s[i+1] = s[i]+A[i]

s = [(s[i]-i) % K for i in range(N+1)]
for i in range(N+1):
    ans += table[s[i]]  
    table[s[i]] += 1
    if i >= K-1:
        
        table[s[i-K+1]] -= 1

print(ans)

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=[0]*(N+1)
for i in range(N):
    B[i+1]=(B[i]+A[i]-1)%K
r=0
from collections import defaultdict
d=defaultdict(int)
for i in range(N+1):
    r+=d[B[i]]
    d[B[i]]+=1
    if K-1<=i:
        d[B[i-K+1]]-=1
print(r)