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):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,K=MI()
    A=LI()
    for i in range(N):
        A[i]-=1
    *cumsum, = accumulate(A)
    for i in range(N):
        cumsum[i]%=K

    cnt = defaultdict(int)
    ans = 0
    for i,c in enumerate(cumsum):
        if i>=K:
            cnt[cumsum[i-K]]-=1
        if c==0 and i<K-1:
            ans += 1
        ans += cnt[c]
        cnt[c]+=1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import bisect
import heapq
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**15

def main():
    n, k = getlist()
    nums = getlist()
    acc = {0: [0]}
    tmp = 0
    for i, num in enumerate(nums):
        tmp += num
        tmp %= k
        tgt = ((tmp - i -1  + k) % k)
        if tgt not in acc:
            acc[tgt] = [i+1]
        else:
            acc[tgt].append(i+1)
        

    
    ans = 0
    for v in acc.values():
        for j, cur in enumerate(v):
            ins = bisect.bisect_left(v, cur+k)
            
            ans += ins - j - 1
        
    
    print(ans)

if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Solution (Python):
n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=[i-1 for i in arr]
acum=[0]
for i in range(n):
  acum.append(acum[-1]+arr[i])
acum=[i%k for i in acum]
ans=0
dic={}
for i in range(n+1):
  if acum[i]%k not in dic:
    dic[acum[i]]=1
  else:
    ans+=dic[acum[i]]
    dic[acum[i]]+=1
  if i>=k-1:
    dic[acum[i-k+1]]-=1
print(ans)

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

Solution (Python):
from collections import defaultdict
N, K = map(int, input().split())
A = [(int(c)%K)-1 for c in input().split()]
B = [0]
for c in A:
  B += [B[-1]+c]
dic = defaultdict(int)
ldic = defaultdict(int)
for i in range(min(K,N+1)):
  c = B[i]
  dic[c%K] += 1
ans = 0

for i in range(1,N+1):
  x = B[i-1]
  ldic[x%K] += 1
  ans += dic[x%K]-ldic[x%K]
  if K+i-1<=N:
    dic[B[K+i-1]%K] += 1
  """
  print('
  print(i,x, ans)
  print(dic)
  print(ldic)
  """
print(ans)

Solution (Python):
from collections import defaultdict
N, K = map(int, input().split())
A = [(int(c)%K)-1 for c in input().split()]
B = [0]
for c in A:
  B += [B[-1]+c]
dic = defaultdict(int)
ldic = defaultdict(int)
for i in range(min(K,N+1)):
  c = B[i]
  dic[c%K] += 1
ans = 0

for i in range(1,N+1):
  x = B[i-1]
  ldic[x%K] += 1
  ans += dic[x%K]-ldic[x%K]
  if K+i-1<=N:
    dic[B[K+i-1]%K] += 1
  """
  print('
  print(i,x, ans)
  print(dic)
  print(ldic)
  """
print(ans)

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

l = [c-1 for c in l]
 
l = [0] + l
from itertools import accumulate
cum =list(accumulate(l))
cum = [c%k for c in cum]

from collections import deque
ans = 0
d = {}
q = deque()
for i in range(n+1):
  if cum[i] not in d:
    d[cum[i]] = 1
  else:
    ans += d[cum[i]]
    d[cum[i]] += 1
  q.append(cum[i])
  if len(q) == k:
    rem = q.popleft()
    d[rem] -= 1
print(ans)

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

l = [c-1 for c in l]
 
l = [0] + l
from itertools import accumulate
cum =list(accumulate(l))
cum = [c%k for c in cum]

from collections import deque
ans = 0
d = {}
q = deque()
for i in range(n+1):
  if cum[i] not in d:
    d[cum[i]] = 1
  else:
    ans += d[cum[i]]
    d[cum[i]] += 1
  q.append(cum[i])
  if len(q) == k:
    rem = q.popleft()
    d[rem] -= 1
print(ans)

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

N, K=map(int, input().split())
A=list(map(int, input().split()))
for i in range(N):
    A[i]-=1
s=[0 for _ in range(N+1)]
for i in range(N):
    s[i+1]=(s[i]+A[i])%K
d=defaultdict(int)
ans=0
q=deque()
for j in range(N+1):
    ans+=d[s[j]]
    d[s[j]]+=1
    q.append(s[j])
    if len(q)==K:
        d[q[0]]-=1
        q.popleft()
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([0] + lr())
A = (A-1) % K
Acum = A.cumsum() % K
counter = defaultdict(int)
answer = 0
for i, x in enumerate(Acum):
    answer += counter[x]
    counter[x] += 1
    if i >= K-1:
        counter[Acum[i-(K-1)]] -= 1

print(answer)

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
Acum = A.cumsum() % K
counter = defaultdict(int)
answer = 0
for i in range(len(Acum)):
    x = Acum[i]
    answer += counter[x]
    counter[x] += 1
    if i >= K-1:
        counter[Acum[i-(K-1)]] -= 1

print(answer)

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
d = defaultdict(int)
answer = 0
for i, x in enumerate(Acum):
    answer += d[x]
    d[x] += 1
    if i >= K-1:
        d[Acum[i-(K-1)]] -= 1

print(answer)

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()
d = defaultdict(int)
answer = 0
for i, x in enumerate(Acum):
    answer += d[x]
    d[x] += 1
    if i >= K-1:
        d[Acum[i-(K-1)]] -= 1

print(answer)

Solution (Python):

n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(n):
  a[i] -= 1
  a[i] %= k
b = [0]
for i in range(n):
  b.append((b[-1]+a[i]) % k)
ans = 0
now = {}
for i in range(n+1):
  tmp = b[i]
  if tmp in now:
    ans += now[tmp]
    now[tmp] += 1
  else:
    now[tmp] = 1
  if i - k + 1 >= 0:
    now[b[i-k+1]] -= 1
print(ans)

Solution (Python):

n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(n):
  a[i] -= 1
  a[i] %= k

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


ans = 0
now = {}
for i in range(n+1):
  if b[i] in now:
    ans += now[b[i]]
    now[b[i]] += 1
  else:
    now[b[i]] = 1
  if i - k + 1 >= 0:
    now[b[i-k+1]] -= 1
  
print(ans)

Solution (Python):
from collections import defaultdict

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    acca = [0]
    for _a in a:
        acca.append(acca[-1] + _a)
    
    ans = 0
    cnt = defaultdict(lambda : 0)
    for i, ac in enumerate(acca):
        ans += cnt[(ac - i) % k]
        cnt[(ac - i) % k] += 1
        if i >= k - 1:
            cnt[(acca[i - k + 1] - (i - k + 1)) % k] -= 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque


n, k = map(int, input().split())
a = [int(i) - 1 for i in input().split()]

total = 0
s = [0] * (n + 1)
for i in range(n):
    total += a[i]
    s[i+1] = total % k

queue = deque()
mp = {}

ans = 0
for j in range(n+1):
    rem = s[j]
    queue.append(rem)
    if rem in mp:
        ans += mp[rem]
        mp[rem] += 1
    else:
        mp[rem] = 1
    
    if len(queue) == k:
        mp[queue.popleft()] -= 1

print(ans)

Solution (Python):
N,K=map(int,input().split())
a=list(map(int,input().split()))
A=[0]
for i in range(N):
    A.append((A[-1]+a[i]-1))
for i in range(len(A)):
    A[i]%=K


D={}
D[0]=1
ans=0

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

if K==1:
    print(0)
else:
    print(ans)

Solution (Python):
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import itertools



readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

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

A = [0] + A
A = list(itertools.accumulate(A))
A = [x % K for x in A]

cnt = defaultdict(int)
ans = 0
for i, a in enumerate(A):
    x = (a - i) % K
    

    ans += cnt[x]
    cnt[x] += 1

    if i >= K-1:
        y = (A[i-K+1] - (i-K+1)) % K
        cnt[y] -= 1

print(ans)

Solution (Python):
from collections import defaultdict

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

A = [a - 1 for a in A]
Acum = [0]
for a in A:
  Acum.append((Acum[-1] + a) % K)

answer = 0
counter = defaultdict(int)
for i, ai in enumerate(Acum):
  answer += counter[ai]
  counter[ai] += 1
  if i - K + 1 >= 0:
    counter[Acum[i - K + 1]] -= 1
    
print(answer)

Solution (Python):
import sys
from bisect import bisect_left

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [(int(a) % K) - 1 for a in input().split()]
    sum_A = [0 for _ in range(N + 1)]

    count = 0
    modK = dict()
    modK[0] = [0]
    for i in range(N):
        sum_A[i + 1] = (sum_A[i] + A[i]) % K
        if sum_A[i+1] not in modK: modK[sum_A[i+1]] = [i + 1]
        else: modK[sum_A[i+1]].append(i+1)
    
    for key in modK: 
        lenK = len(modK[key])
        for i, a in enumerate(modK[key]):
            count += bisect_left(modK[key], a + K, i, lenK) - i - 1

    print(count)
    return 0

if __name__ == "__main__":
    solve()

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

import copy
B = copy.deepcopy(A)
for i in range(N):
    B[i] -= 1

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

from collections import defaultdict
D = defaultdict(list)
for i in range(N+1):
    D[C[i]].append(i)

ans = 0



for i in D:
    E = D[i]
    
    if len(E)>=2:
        left = 0
        right = 1
        count = 0
        flag = 0
        while left != len(E)-1 :
            if E[right]-E[left] < K:
                if right == len(E)-1:
                    if flag == 0:
                        count += 1
                        flag = 1
                    ans += count
                    left += 1
                    count -= 1
                else:
                    count += 1
                    right += 1
            else:
                ans += count
                count -= 1
                left += 1
print(ans)

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


from bisect import bisect_right as br
def main():
    dic = {}
    for i in range(1,N + 1):
        A[ i ] += A[ i - 1 ]
    for j in range(N + 1):
        if (A[j] - j)%K in dic:
            dic[(A[j] - j)%K].append(j)
        else:
            dic[(A[j] - j)%K] = [j]

    ans = 0
    
    for i in range(1,N + 1):
        tmp = dic[(A[i] - i)%K]
        left = br(tmp,i - K)
        right = br(tmp,i) - 1
        ans += right - left
    print(ans)
    return 

if __name__ == "__main__":
    main()

Solution (Python):
def shaku(K,lists):
    ans=0
    SUMS=0
    index=0
    for  l  in range(len(lists)):
        while index < l or index< len(lists) and SUMS +lists[index] < K:
            SUMS += lists[index]
            index+= 1
        ans += index-l
        SUMS -= lists[l]

    return ans


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

uselist=[0 for i in range(n+1)]
for i in range(n):
    uselist[i+1]=(uselist[i]+lists[i])
anslist=[0 for i in range(n+1)]
for j in range(1,n+1):
    anslist[j]=(uselist[j]-j)%k
dic={}
for i in range(n+1):
    if anslist[i] in  dic.keys():
        dic[anslist[i]].append(i+1)
    else:
        dic[anslist[i]]=[1+i]

answer=0
for lis in dic.values(): 
    sublis=[lis[0]]
    for a in range(1,len(lis)):
        sublis.append(lis[a]-lis[a-1])
    P=shaku(k,sublis)

    for some in lis:
      if some<k:
        answer-=1
    answer+=P
print(answer)

Solution (Python):
from collections import Counter

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

Ss = [0]
S = 0
for A in As:
    S += A-1
    S %= K
    Ss.append(S)

ans = 0
cnt = Counter()
for i in range(N+1):
    ans += cnt[Ss[i]]
    cnt[Ss[i]] += 1
    if i >= K-1:
        cnt[Ss[i-K+1]] -= 1

print(ans)

Solution (Python):
from collections import defaultdict
import bisect
n,k=map(int,input().split())
a=[1]+list(map(int,input().split()))
d = defaultdict(list)
for i in range(n+1):
  a[i]-=1
d[a[0]%k].append(0)
for i in range(n):
  a[i + 1] += a[i]
  d[a[i+1]%k].append(i+1)
ans=0
for l in d.values():
  for i, idx in enumerate(l):
    ans += bisect.bisect_left(l,idx+k)-i-1
print(ans)

Solution (Python):
from itertools import accumulate
n,k=map(int, input().split()) 
A=list(map(int, input().split()))
S=[0]+list(accumulate(A))
R=[(S[i]-i)%k for i in range(n+1)]

r_dict={}
ans=0
for i in range(n+1):
    if R[i] in r_dict:
        ans+=r_dict[R[i]]
        r_dict[R[i]]+=1
    else:
        r_dict[R[i]]=1
    if i-k+1>=0:
        r_dict[R[i-k+1]]-=1
    
print(ans)

Solution (Python):
def bfs(n,e,fordfs,D):
    
    W = [-1]*(n-1)
    
    used = defaultdict(bool)
    que = deque()
    que.append(e)
    while que:
        now = que.popleft()
        i = 1
        for ne in fordfs[now]:
            l = min(now,ne); r = max(now,ne)
            if W[D[(l,r)]] == -1:
                while(True):
                    if not used[(now,i)]:
                        used[(now, i)] = True
                        used[(ne, i)] = True
                        break
                    i +=1
                que.append(ne)
                W[D[(l,r)]] = i
    return W
def examD():
    N = I()
    V = [[]for _ in range(N)]
    d = defaultdict(int)
    for i in range(N-1):
        a, b = LI()
        V[a-1].append(b-1)
        V[b-1].append(a-1)
        d[(a-1,b-1)] = i
    ans = bfs(N,0,V,d)
    print(max(ans))
    for v in ans:
        print(v)
    return

def examE():
    N, K = LI()
    A = LI()
    d = defaultdict(list)
    cumA = 0
    d[cumA].append(0)
    for i in range(N):
        cumA +=A[i]-1
        cumA %=K
        d[cumA].append(i+1)

    ans = 0
    for l in d.values():
        for i in range(len(l)):
            left = i; r = len(l)
            while(r-left>1):
                now = (left+r)//2
                if l[now]-l[i]>=K:
                    r = now
                else:
                    left = now
            ans += left-i
    print(ans)
    return

def examF():
    N, M = LI()
    S = SI()
    ans = []
    cur = N
    while(cur>0):
        k = min(M,cur)
        while(S[cur-k]=="1"):
            k -=1
            if k==0:
                print("-1")
                return
        ans.append(k)
        cur -=k
    for v in ans[::-1]:
        print(v)
    return


import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

Solution (Python):
import sys
import math
import heapq
import bisect
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y




N,K=LI()
As=LI()

Cum=[0]*(N+1)
for i in range(N):
    Cum[i+1] = Cum[i] + As[i]

REM2IDX = {}
for i in range(0,N+1):
    rem = (Cum[i] - i) % K
    if not rem in REM2IDX: REM2IDX[rem] = []
    REM2IDX[rem].append(i)

res = 0
for i in range(0,N+1):
    rem = (Cum[i] - i) % K
    cnt = len(REM2IDX[rem])
    l = bisect.bisect_right(REM2IDX[rem], i)
    r = bisect.bisect_right(REM2IDX[rem], i+K-1)
    res += (r-l)

print(res)

Solution (Python):
from collections import defaultdict

n, k = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * (n + 1)
for i in range(n):
    S[i+1] = S[i] + A[i]

f = lambda n: (S[n] - n) % k
C = defaultdict(int)
ans = 0
for i in range(n):
    C[f(i)] += 1
    j = i - k + 1
    if 0 <= j:
        C[f(j)] -= 1
    ans += C[f(i+1)]
print(ans)

Solution (Python):

import sys
from itertools import accumulate
from collections import Counter
INF = float("inf")


def solve(N: int, K: int, A: "List[int]"):

    ans = 0

    
    acc = [0]+list(accumulate(A))

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

        
        if j-K >= 0:
            cnt[(acc[j-K]-(j-K)) % K] -= 1

        
        ans += cnt[(acc[j]-j) % K]
    print(ans)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    solve(N, K, A)


if __name__ == '__main__':
    main()

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,K=map(int,input().split())
A = list(map(int,input().split()))
for i in range(n):
    A[i]-=1
B=[0]+A[:]
for i in range(n):
    B[i+1]=(B[i+1]+B[i])%K
C=collections.Counter(B[:K])
for ci in C.values():
    ans+=ci*(ci-1)//2
for i in range(K,n+1):
    
    C[B[i-K]]-=1
    ans+=C[B[i]]
    C[B[i]]+=1


print(ans)

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


def solve():
    N, K, *A = map(int, open(0).read().split())
    
    Acumsum = [0] + list(accumulate(A))
    si = [(Acumsum[i] - i) % K for i in range(N + 1)]
    counter = defaultdict(int)
    
    ans = 0
    for j in range(N):
        counter[si[j]] += 1
        if 0 <= j - K + 1:
            counter[si[j - K + 1]] -= 1
        ans += counter[si[j + 1]]
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
from itertools import accumulate
from collections import defaultdict
input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))
a = [i-1 for i in a]
suma = [0]+list(accumulate(a))
suma = [i%k for i in suma]
rem = defaultdict(int)
ans = 0
if k > n:
    for i in range(n+1):
        x = suma[i]
        rem[x] += 1
    for s in rem.values():
        ans += s*(s-1)//2
    print(ans)
    exit()
for i in range(k):
    x = suma[i]
    rem[x] += 1
for s in rem.values():
    ans += s*(s-1)//2
for i in range(n-k+1):
    rem[suma[i]%k] -= 1
    rem[suma[i+k]%k] += 1
    ans += rem[suma[i+k]] -1
print(ans)

Solution (Python):
from fractions import gcd

from heapq import*
import math
from collections import defaultdict, Counter, deque
from bisect import *
import itertools
import fractions


MOD = 10 ** 9 + 7






def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    for i in range(n):
        a[i] -= 1
    r = [a[0] % k]
    for i in range(1,n):
        r.append((r[i - 1] + a[i]) %k)
    
    d = defaultdict(int)
    r = [0] + r
    d[0] = 1
    ans = 0
    for i in range(n):
        if i >= k - 1:
            d[r[i - k  + 1]]-=1
        ans+=d[r[i+1]]
        d[r[i+1]] += 1
    print(ans)



        


if __name__ == '__main__':
    main()
1

Solution (Python):
from itertools import *
from collections import defaultdict
def ints():
  return [int(x) for x in input().split()]
def readi():
  return int(input())

N, K = ints()
A = ints()
S = [0] + list(accumulate(A))

def f(i):
  return (S[i]-i)%K

s = 0
memo = defaultdict(int)
for j in range(1, N+1):
  fj = f(j)

  if j-K>=0:
    memo[f(j-K)] -= 1
  memo[f(j-1)] += 1

  s += memo[fj]
print(s)

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

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

ans = 0
dic = defaultdict(int)
dic[0] = 1
for i in range(1,n+1):
    if i >= k:
        dic[S[i-k]] -= 1
    ans += max(0,dic[S[i]])
    dic[(S[i])] += 1

print(ans)

Solution (Python):
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

S = [0]*(N+1)
for i in range(N):
    S[i+1] = (S[i] + A[i]) % K
    
for i in range(N+1):
    S[i] = (S[i] - i) % K
    
dic = {}
for i in range(min(K, N+1)):
    if S[i] in dic:
        dic[S[i]] += 1
    else:
        dic[S[i]] = 1
        

ans = 0
for key in dic:
    ans += dic[key]*(dic[key]-1)//2
    
if K < N+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):
from collections import defaultdict
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
a = inl()
h =defaultdict(int)
b = [0]*(n+1)
s = [0]*(n+1)
for i in range(n):
    s[i+1] = s[i]+a[i]
    b[i+1] = (s[i+1]-i-1)%k
ddprint(s)
ddprint(b)
acc = 0
for i in range(n+1):
    if i>=k:
        h[b[i-k]] -= 1
    acc += h[b[i]]
    h[b[i]] += 1
    
print(acc)

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


   if k == 1:
      res = 0
      print(res)
   elif k == 2:
      res = 0
      for e in a:
         if e%k == 1:
            res += 1
      print(res)
   else:
      for i in range(n):
         a[i] = (a[i]-1)%k
      b = [0]
      d = {}
      d[0] = 1

      res = 0
      p = 0

      for i,e in enumerate(a):
         p = (p+e)%k
         if p in d:
            res += d[p]
            d[p] += 1
         else:
            d[p] = 1
         b.append(p)
         if i >= k-2:
            d[b[i-(k-2)]] -= 1
      print(res)

if __name__ == '__main__':
      main()

Solution (Python):
from collections import Counter


N, K = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * (N + 1)

for i, a in enumerate(A):
    S[i + 1] = (S[i] + a - 1) % K

C = Counter()
ans = 0
for j in range(1, N + 1):
    C[S[j - 1]] += 1
    if (j - K) >= 0:
        C[S[j - K]] -= 1

    ans += C[S[j]]


print(ans)

Solution (Python):
N, K = map(int,input().split())
A = list(map(int, input().split()))
S = [0]*(N+1)
S2 = [0]*(N+1)
dict = {}

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

ans =0
for i in range(N+1):
    if dict.get(S2[i],0):
        ans += dict[S2[i]]
    dict[S2[i]]=dict.get(S2[i],0)+1
    if i >=K-1:
        dict[S2[i-(K-1)]]-=1

print(ans)

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

Solution (Python):

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
write = sys.stdout.write



def solve():
    n,k=map(int, readline().split())
    a = list(map(int, readline().split()))
    b=[0]*(n+1)

    for i in range(n):
        b[i+1]=b[i]+a[i]-1
        b[i+1]%=k
    count=0
    from collections import defaultdict
    dp=defaultdict(list)
    for i in range(n+1):
        dp[b[i]].append(i)
    
    for item in dp:
        
        if len(dp[item])<2:
            continue
        l=0
        r=1
        li=dp[item]
        while(l<len(li)):
            if l==r:
                r+=1
                continue
            if r<len(li) and li[r]-li[l]<k:
                r+=1
            else:
                count+=r-l-1
                l+=1
    print(count)

        
'''
    for i in range(k):
        if dp[i]<2:
            continue
        count+=dp[i]*(dp[i]-1)//2
'''
    


if __name__ == "__main__":
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from collections import defaultdict
def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    S=[0]*(n+1)
    for i in range(n):
        S[i+1]=S[i]+A[i]
    for i in range(n+1):
        S[i]-=i
        S[i]%=k

    ans=0
    D=defaultdict(int)
    for i in range(n+1):
        s=S[i]
        ans+=D[s]
        D[s]+=1
        if(i>=k-1):
            D[S[i-k+1]]-=1
    print(ans)
resolve()

Solution (Python):
N, K = [int(n) for n in input().split()]

A = [int(n) for n in input().split()]

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

check = {0: [0,1,[0]]}

s = 0
for i in range(1,N+1):
    s = (s + A[i-1]) % K
    if s in check:
        j = check[s][0]
        l = check[s][1]
        while j < l and i - check[s][2][j] >= K:
            j += 1
        check[s][0] = j
        count += l - j
        check[s][2].append(i)
        check[s][1] = l + 1
    else:
        check[s] = [0,1,[i]]

print(count)

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

ans = 0
accum = [0]
d = {0 : 1}

for i, a in enumerate(A):
  accum.append((accum[-1] + a - 1)%K)
  if i >= K - 1:
    d[accum[i-K+1]] -= 1
  
  if accum[-1] in d:
    ans += d[accum[-1]]
    d[accum[-1]] += 1
  
  else:
    d[accum[-1]] = 1

print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



N,K = II()
A = [0] + III()

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

d = defaultdict(int)
ans = 0
for i in range(N+1):
    ans += d[S[i]]
    d[S[i]] += 1
    if i-K+1>=0:
        d[S[i-K+1]] -= 1

print(ans)

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







sums = [0]
for x in nums:
  sums.append(sums[-1] + x)

a = [(sums[i] - i) % k for i in range(len(sums))]

res = 0
memo = {}
i = 0 
for j in range(len(a)):
  memo[a[j]] = memo.get(a[j], 0) + 1
  if j - i + 1 > k:
    memo[a[i]] -= 1
    i += 1
  res += memo[a[j]] - 1
print(res)

Solution (Python):
N,K = map(int,input().split())
S = []
d = {}
A = list(map(int,input().split()))
ans = 0
sum =0
for i in range(1,N+1):
    sum += A[i-1] % K
    s = (sum - i) % K
    if i > K:
        x = S.pop(0)
        d[x] -= 1
    elif i < K:
        if s == 0:
            ans += 1
    if s not in d:
        d[s] = 0
    ans += d[s]
    d[s] += 1
    S.append(s)
print(ans)

Solution (Python):
from itertools import accumulate
from collections import defaultdict
N,K = map(int, input().split())
Xs = list(accumulate([0] + [int(x) for x in input().split()]))
Xs = [(x-i)%K for i, x in enumerate(Xs)]
d,r=defaultdict(int),0
for i, x in enumerate(Xs):
    d[x]+=1
    if i >= K:
        d[Xs[i-K]] -= 1
    r += d[x]-1
print(r)

Solution (Python):
N, K = map(int, input().split())
A = [0] + [int(a) - 1 for a in input().split()]
for i in range(1, N+1):
    A[i] = (A[i] + A[i-1]) % K

D = {0: 1}
ans = 0
for i in range(1, N+1):
    if i >= K:
        D[A[i-K]] -= 1
    a = A[i]
    if a not in D: D[a] = 0
    ans += D[a]
    D[a] += 1
print(ans)