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):
n,k=map(int,input().split())
a=list(map(lambda x:(int(x)-1)%k,input().split()))
s=[0]
for i in a:
    s.append((s[-1]+i)%k)
mp={}
ans=0
for i in range(len(s)):
    if i-k>=0:
        mp[s[i-k]]-=1
    if s[i] in mp:
        ans+=mp[s[i]]
        mp[s[i]]+=1
    else:
        mp[s[i]]=1
print(ans)

Solution (Python):
n,k = map(int,input().split())
a = [ int(i) for i in input().split() ]
ans = 0
dp = dict()
dp[0] = 1
pref = [ 0 for i in range(n+1) ]
pre = 0
for i in range(n):
    pre += a[i] - 1
    pre %= k
    pref[i+1] = pre
    if i >= k-1:
        dp[pref[i-k+1]] -= 1

    try:
        ans += dp[pre]
        dp[pre] += 1
    except:
        dp[pre] = 1

print(ans)

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

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

mp={}
ans=0
for i in range(len(s)):
    if i-k>=0:
        mp[s[i-k]]-=1
    if s[i] in mp:
        ans+=mp[s[i]]
    if s[i] in mp:
        mp[s[i]]+=1
    else:
        mp[s[i]]=1
    
print(ans)

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))
B = [a%K for a in A]
cs = [0]
for b in B:
    c = (cs[-1] + b-1) % K
    cs.append(c)

from collections import deque
from collections import defaultdict
qs = defaultdict(lambda: deque())

ans = 0
for i,c in enumerate(cs):
    while qs[c] and qs[c][0] + K <= i:
        qs[c].popleft()
    ans += len(qs[c])
    qs[c].append(i)
print(ans)

Solution (Python):
import collections
def main():

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

    d = collections.defaultdict(int)

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

    ans = 0
    for j in range(N+1):
        v = (prefix[j] - j) % K
        ans += d[v]
        d[v] += 1
        if j >= K-1:
            d[(prefix[j-K+1] - (j-K+1)) % K] -= 1
        
    return ans



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

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

a = [0]

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

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

print(ans)

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

    C=defaultdict(list)
    for i in range(n+1):
        C[S[i]].append(i)

    ans=0
    C=list(C.values())
    for d in range(len(C)):
        n=len(C[d])
        if(n<=1): continue
        r=0
        for l in range(n):
            while(r+1<n and C[d][r+1]-C[d][l]<k):
                r+=1
            ans+=r-l
            if(r==l): r+=1
    print(ans)
resolve()

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

hm = {}
hm[A[0]] = 1
out = 0
for i in range(1,N):
  A[i] += A[i-1]
  A[i] %= K

for i in range(min(K-1,N)):
  if A[i]==0 and K != 1:
    out+=1
    
for i in range(1,min(N,K)):
  if A[i] in hm:
    hm[A[i]]+=1
  else:
    hm[A[i]]=1
  out += hm[A[i]]-1
  
for i in range(min(K,N),N):
  if A[i] in hm:
    hm[A[i]]+=1
  else:
    hm[A[i]]=1
  hm[A[i-K]] -= 1
  out += hm[A[i]]-1

print(int(out))

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

C = B[::]
C.sort()
I = dict()
itmp = 0
I[C[0]] = 0
for i in range(1, N+1):
    if C[i] != C[i-1]:
        itmp += 1
        I[C[i]] = itmp

tbl = [0] * (N+1)
for i in range(min(K,N+1)):
    tbl[I[B[i]]] += 1
    ans += tbl[I[B[i]]] - 1
for i in range(K, N+1):
    tbl[I[B[i-K]]] -= 1
    tbl[I[B[i]]] += 1
    ans += tbl[I[B[i]]] - 1
print(ans)

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

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

B = (np.add.accumulate(A) - np.arange(N+1)) % K

counter = defaultdict(int)
ans = 0

for j in range(N+1):
    if j - K >= 0:
        counter[B[j-K]] -= 1
    ans += counter[B[j]]
    counter[B[j]] += 1

print(ans)

Solution (Python):
N,K = map(int,input().split())
*A, = map(lambda x:(int(x)%K-1)%K,input().split())

class cumulative_sum:
    def __init__(self,A):
        N = len(A)
        self.S = [0]*(N+1)
        for i in range(N):
            self.S[i+1] = (self.S[i] + A[i])%K
    def get(self,i,j=None):
        if j==None:j=len(self.S)-1
        if j<=i:return 0
        return (self.S[j]-self.S[i])%K

SumA = cumulative_sum(A)

def binary_search(l,r,func):
    if func(l):return l-1
    if not func(r):return r
    while l+1<r:
        i = (l+r)//2
        if func(i):
            r = i
        else:
            l = i
    return l

def f(j):
    return cnt[s][j] > idx - K

ans = 0
cnt = {}
for idx,s in enumerate(SumA.S):
    if not s in cnt:
        cnt[s] = [-2*K]
    cnt[s].append(idx)
    l = len(cnt[s])
    j = binary_search(0,l-1,f)
    ans += (l-1)-(j+1)
print(ans)

Solution (Python):
n,k=map(int,input().split())
a=[0]+list(map(int,input().split()))
for i in range(1,n+1):
    a[i]+=a[i-1]
for i in range(1,n+1):
    a[i]=(a[i]-i)%k
b=[[] for i in range(n+1)]
for i in range(n+1):
    b[i]=[a[i],i]
b.sort()
left=0
right=0
ans=0
while left<n:
    while right<n:
        if b[left][0]==b[right+1][0] and b[right+1][1]-b[left][1]<k:
            right+=1
        else:
            break
    ans+=right-left
    left+=1
print(ans)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
a2 = [0]
for i in range(n):
    a2.append(a2[-1] + a[i] - 1)
a2 = [a2[i] % k for i in range(n + 1)]
count = {}
temp = a2[:min(k, len(a2))]
for i in temp:
    count.setdefault(i, 0)
    count[i] += 1
ans = 0
for i in count.values():
    ans += (i * (i - 1) // 2)
for i in range(1, len(a2) - len(temp) + 1):
    temp = a2[i: i + len(temp)]
    temp2 = temp[:-1]
    ans += temp2.count(temp[-1])
print(ans)

Solution (Python):
import sys
import math
from itertools import accumulate as acc

def func(s):
    return (int(s)-1)%K


N,K=map(int,input().split())
a=list(map(int,input().split()))
x=[0]
tmp=0
for i in range(N):
    tmp=(tmp+a[i]-1)%K
    x+=[tmp]
dic={}
ans=0
if N<K:
    for i in range(N+1):
        if x[i] in dic: dic[x[i]]+=1
        else: dic[x[i]]=1
    for i in dic:
        ans+=dic[i]*(dic[i]-1)//2

    
else:
    for i in range(K):
        p=x[i]
        if p in dic: dic[p]+=1
        else: dic[p]=1
        ans+=dic[p]-1
    for i in range(K,N+1):
        p=x[i]
        if p in dic: dic[p]+=1
        else: dic[p]=1
        dic[x[i-K]]-=1
        ans+=dic[p]-1

print(ans)

Solution (Python):
import sys
import math
from itertools import accumulate as acc

def func(s):
    return (int(s)-1)%K


N,K=map(int,input().split())
a=list(map(int,input().split()))
x=[0]
tmp=0
for i in range(N):
    tmp=(tmp+a[i]-1)%K
    x+=[tmp]
dic={}
ans=0
if N<K:
    for i in range(N+1):
        if x[i] in dic: dic[x[i]]+=1
        else: dic[x[i]]=1
    for i in dic:
        ans+=dic[i]*(dic[i]-1)//2

    
else:
    for i in range(K):
        p=x[i]
        if p in dic: dic[p]+=1
        else: dic[p]=1
        ans+=dic[p]-1
    for i in range(K,N+1):
        p=x[i]
        if p in dic: dic[p]+=1
        else: dic[p]=1
        dic[x[i-K]]-=1
        ans+=dic[p]-1

print(int(ans))

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

n, k = map(int, input().split())
aaa = list(map(int, input().split()))
bbb = list(accumulate(aaa))
ccc = list(-i % k for i in range(n))
ddd = [(b + c) % k for b, c in zip(bbb, ccc)]






count = dict(Counter(ddd[:k - 1]))
ans = 0
for i in range(n):
    key = (1 - aaa[i] + bbb[i] + ccc[i]) % k
    if key in count:
        ans += count[key]

    j = i + k - 1
    if j < n:
        dj = ddd[j]
        if dj not in count:
            count[dj] = 1
        else:
            count[dj] += 1

    di = ddd[i]
    count[di] -= 1
    if count[di] == 0:
        count.pop(di)

print(ans)

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

if K == 1:
  print(0)
  exit()

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

n = 1
if n in D:
  ans = D[n]
else:
  ans = 0
for i in range(N):
  if L[i] != -1:
    D[L[i]] -= 1
  if i + K - 1 < N:
    t = (t + A[i + K - 1] - 1) % K
    if t < 0:
      t += K
    if t in D:
      D[t] += 1
    else:
      D[t] = 1
    L[i + K - 1] = t
  n = (n - 1 + A[i]) % K
  
  if n < 0:
    n += K
  if n in D:
    ans += D[n]
  
print(ans)

Solution (Python):
from bisect import bisect_right

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

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

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

dic = {}
for i, b in enumerate(B):
    if not b in dic.keys():
        dic[b] = [i]
    else:
        dic[b].append(i)

ans = 0
for L in dic.values():
    for i in range(len(L)):
        
        j = bisect_right(L, L[i]+K-1)
        
        ans += j-i-1
print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
A = [0] + LI()



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


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



ans = 0
D = defaultdict(int)
for j in range(n, -1, -1):
    ans += D[A[j]]
    D[A[j]] += 1
    if j + k - 1 < n + 1:
        D[A[j + k - 1]] -= 1


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

Solution (Python):
import itertools, collections
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
C = list(itertools.accumulate([0] + A))
D = [(v - i) % K for i, v in enumerate(C)]

dp = collections.Counter(D[:K])
ans = 0
for i in range(N):
    dp[D[i]] -= 1
    ans += dp[D[i]]
    if i + K < len(D):
        dp[D[i + K]] += 1
print(ans)

Solution (Python):
import itertools, collections
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
C = list(itertools.accumulate([0] + A))
D = [(v - i) % K for i, v in enumerate(C)]

dp = collections.Counter(D[:K])
ans = 0
for i in range(N):
    dp[D[i]] -= 1
    ans += dp[D[i]]
    if i + K < len(D):
        dp[D[i + K]] += 1
print(ans)

Solution (Python):
from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, K = inpl()
A = inpl()
if K == 1:
    print(0)
    exit()
C = defaultdict(list)
k_list = set()
m = 0
C[0].append(-1)
for i in range(N):
    m = (m + A[i] - 1) % K
    C[m].append(i)
    k_list.add(m)

ans = 0
for k in k_list:
    L = len(C[k])
    if L <= 1:
        continue
    l = r = 0
    while r < L:
        r = bisect_left(C[k], C[k][l]+K-1, l)
        if r == L:
            ans += (L-l)*(L-l-1)//2
        else:
            ans += r - l - 1
            if C[k][r] == C[k][l]+K-1:
                ans += 1
            l += 1
print(ans)

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

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
r = 0
s = {0: [0]}
for i in range(n):
    r = (r + a[i] - 1) % k
    if r in s:
        s[r].append(i + 1)
    else:
        s[r] = [i + 1]
ret = 0
for key in s:
    a = s[key]
    en = 0
    for st in range(len(a)):
        while en < len(a) and a[en] - a[st] < k:
            en += 1
        ret += en - st - 1
print(ret)

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

kinds = set(S)
counts = {}
ans = 0
for k in kinds:
	counts[k] = 0
for i in range(N+1):
	counts[S[i]] += 1
	if i >= K:
		counts[S[i-K]] -= 1
	ans += (counts[S[i]] - 1)
print(ans)

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

ans = 0
for k in d:
    l = d[k]
    for i in range(len(l)):
        n = l[i]
        j = bisect.bisect_left(l,n+K)
        ans += j-i-1
    if k==1:
        j = bisect.bisect_left(l,K-1)
        ans += j
            
print(ans)

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))
B = [a%K for a in A]
cs = [0]
for b in B:
    c = (cs[-1] + b-1) % K
    cs.append(c)

from collections import deque
from collections import defaultdict
qs = defaultdict(lambda: deque())

ans = 0
for i,c in enumerate(cs):
    while qs[c] and qs[c][0] + K <= i:
        qs[c].popleft()
    ans += len(qs[c])
    qs[c].append(i)
print(ans)

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

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

ss = []
for i in range(len(s)):
    ss.append((s[i] - i) % k)



ans = 0
from collections import Counter
c = Counter(ss[1: min(k, len(ss))])
for i in range(len(ss)):
    
    ans += c[ss[i]]

    if i + 1 < len(ss):
        c[ss[i + 1]] -= 1
    if i + k < len(ss):
        c[ss[i + k]] += 1

print(ans)

Solution (Python):


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = [0]*(N+1)

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

    Q = {}
    X = 0

    for i, b in enumerate(B):
        if i>=K:
            Q[B[i-K]] -= 1

        if b in Q:
            X += Q[b]
            Q[b] += 1
        else:
            Q[b] = 1

    print(X)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

N, K = map(int, input().split())
A = [int(i) for i in input().split()]

s = [0]

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

d = defaultdict(int)

ret = 0
for i in range(min(K, N + 1)) :
    ret += d[s[i]]
    d[s[i]] += 1
for i in range(K, N + 1) :
    d[s[i-K]] -= 1
    ret += d[s[i]]
    d[s[i]] += 1

print(ret)

Solution (Python):

import sys
from collections import Counter
input = sys.stdin.readline
INF = 10**9

n, k = [int(item) for item in input().split()]
a = [int(item) - 1 for item in input().split()]
cumsum = [0] * (n + 1)
for i in range(n):
    cumsum[i+1] = cumsum[i] + a[i]
    cumsum[i+1] %= k

ls = list(set(cumsum))
dic = dict()
for i, item in enumerate(ls):
    dic[item] = i

cnt = [0] * (n + 10)
num = 0
ans = 0
for i, item in enumerate(cumsum):
    index = dic[item]
    ans += cnt[index]
    cnt[index] += 1
    num += 1
    if num >= k:
        left = cumsum[i - k + 1]
        index = dic[left]
        if cnt[index] > 0:
            cnt[index] -= 1
        num -= 1

print(ans)

Solution (Python):
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
s = 0
B = [0]
C = {0:[0]}
for i, a in enumerate(A):
    s = (s+a)%K
    n = (s-i-1)%K
    B.append(n)
    if n not in C: C[n] = []
    C[n].append(i+1)

ans = 0

for k, v in C.items():
    if len(v)<=1: continue
    ans_k = 0
    ir=0
    for il in range(0,len(v)-1):
        l = v[il]
        while(ir<len(v) and v[ir]-l<=K-1): ir+=1
        ans_k+=(ir-1)-il
    ans+=ans_k
print(ans)

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

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


N, K = list(map(int, sys.stdin.buffer.readline().split()))
A = list(map(int, sys.stdin.buffer.readline().split()))

if K == 1:
    print(0)
    exit()
if K == 2:
    ans = sum([1 for a in A if a % 2 == 1], 0)
    
    print(ans)
    exit()


def test():
    ans = 0
    for i, a in enumerate(A):
        if a % K == 1:
            ans += 1
        j = 1
        while i - j >= 0 and j + 1 < K:
            if (sum(A[i - j: i]) + a) % K == j + 1:
                ans += 1
            j += 1
    print(ans)



counts = defaultdict(int)
hist = [-1] * N
offset = 0
ans = 0
for i, a in enumerate(A):
    a %= K
    if a == 1:
        ans += 1
    ans += counts[(K - a + 1 - offset) % K]
    offset += a - 1
    offset %= K
    counts[(a - 1 - offset) % K] += 1

    if i - K + 2 >= 0:
        counts[hist[i - K + 2]] -= 1
    hist[i] = (a - 1 - offset) % K
print(ans)

Solution (Python):
import bisect

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

memo = {0 : []}
for i in range(n):
  if a[i] % k not in memo.keys():
    memo[a[i] % k] = [i]
  else:
    memo[a[i] % k].append(i)

ans = bisect.bisect_left(memo[0], k - 1)

for i in memo.keys():
  for j in range(len(memo[i]) - 1):
    ans += bisect.bisect_left(memo[i], memo[i][j] + k) - 1 - j

print(ans)

Solution (Python):
import bisect
n, k = map(int, input().split())
a = [0] + list(map(int, input().split()))
for i in range(n):
    a[i + 1] += a[i]
ans = 0
for i in range(n):
    a[i + 1] -= i + 1
    a[i + 1] %= k
d = dict()
for i, x in enumerate(a):
    if x in d:
        d[x].append(i)
    else:
        d[x] = [i]
ans = 0
for v in d.values():
    for i, x in enumerate(v):
        t = bisect.bisect_right(v, x + k - 1) - i - 1
        ans += t
print(ans)

Solution (Python):
from bisect import bisect_left
n,k = map(int,input().split( ))
a = list(map(int, input().split( )))
ans = 0
for i in range(n):
    a[i] -= 1
sm= 0
a_sm = [0]
for i in range(n):
    sm += a[i]
    sm%=k
    a_sm.append(sm)

dic = {}
for i in range(n+1):
    if a_sm[i] in dic:
        dic[a_sm[i]].append(i)
    else:
        dic[a_sm[i]]=[i]

for t in dic:
    for j in range(len(dic[t])-1):
        dm = bisect_left(dic[t],dic[t][j]+k)
        ans += dm - j - 1

       
print(ans)

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

B=[a-1 for a in A]

S=[0]
for b in B:
    S.append((S[-1]+b)%K)

from collections import Counter
C=Counter()

ANS=0
for i in range(N+1):
    ANS+=C[S[i]]
    
    C[S[i]]+=1

    if i-K+1>=0:
        C[S[i-K+1]]-=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()))
A_cum = [0] + list(accumulate(A))
ans = 0
dd = defaultdict(int)
q = []
for i, a in enumerate(A_cum):
    a -= i
    a %= K
    if i-K >= 0:
        dd[q[i-K]] -= 1
    ans += dd[a]
    dd[a] += 1
    q.append(a)
print(ans)

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 


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


acc = [0]
for ai in a:
    acc.append((acc[-1]+ai)%k)


ans = 0
d = {}
for num,i in enumerate(acc):
    
    if num >= k:
        d[acc[num-k]] -= 1
    
    if i in d:
        ans += d[i]
        d[i] += 1
    else:
        d[i] = 1
    

print(ans)

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

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

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

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

    

    d = defaultdict(int)

    for i in range(1, min(N + 1, K)):
        d[A[i]] += 1

    ans = 0
    tmp = min(N + 1, K)
    for i in range(N):
        ans += d[A[i]]
        d[A[i + 1]] -= 1
        if tmp <= N:
            d[A[tmp]] += 1
            tmp += 1

    print (ans)

if __name__ == '__main__':
    main()

Solution (Python):
import bisect
from collections import defaultdict

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

A = [(a-1) % K for a in A_raw]
acc = [0] * (N+1)
for i in range(N):
    acc[i+1] = (acc[i] + A[i]) % K

cnt = defaultdict(list)
cnt[0].append(-1)
ans = 0
for i, a in enumerate(acc[1:]):
    if cnt[a]:
        ans += len(cnt[a]) - bisect.bisect_left(cnt[a], i - K+1)
        
        
    cnt[a].append(i)

print(ans)

Solution (Python):
import queue
import math
import copy
"""
N = int(input())



A = []
for i in range(N):
	A.append(int(input()))

print(A)

"""
(N,M) = (int(i) for i in input().split(" "))
A = [int(i)-1 for i in input().split()]

mp={}
mp[0] = 1
hT = [0]
T = 0
ans = 0
for i,a in enumerate(A):
	T += a
	T %= M
	if i>=M-1:
		mp[hT[i-M+1]]-=1
	if T in mp.keys():
		ans += mp[T]
		mp[T] += 1
	else:
		mp[T] = 1
	hT.append(T)

print(ans)

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

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

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

A = accumulate(chain((0,),map(lambda x: int(x)-1, input().split())))

d = defaultdict(list)
for i,a in enumerate(A):
    d[a%K].append(i)

cnt = 0
for l in d.values():
    if len(l) == 1:
        continue
    j = 0
    for i,li in enumerate(l):
        li += K
        while j < len(l) and l[j] < li:
            j += 1
        cnt += j-i-1

print(cnt)

Solution (Python):

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

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

sa = [0]

for i in range(N):

    if i == 0:
        sa.append(A[0] % K)
    else:
        sa.append((sa[-1] + A[i]) % K)



nm = 1
for i in range(N):
    i += 1

    if sa[i] < nm:
        sa[i] += K
    sa[i] -= nm
    nm += 1
    nm %= K



ndic = {}

ans = 0
for i in range(N+1):

    if sa[i] in ndic:
        ans += ndic[sa[i]]
        ndic[sa[i]] += 1
    else:
        ndic[sa[i]] = 1

    if i - (K-1) >= 0:
        ndic[sa[i-(K-1)]] -= 1

print (ans)

Solution (Python):
from collections import defaultdict

n,k = map(int, input().split())
a = list(map(int, input().split()))
if k == 1:
    print(0)
    exit()
s = [0]
for i in a:
    s.append((s[-1]+i-1)%k)

d = defaultdict(int)
d[0] = 1
ans = 0
for r in range(1, n+1):
    sr = s[r]
    if d[sr]>0:
        ans += d[sr]
    d[sr] += 1
    l = r-k+1
    if l >= 0:
        d[s[l]] -= 1
print(ans)

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

cnt = {0:1}

ans = 0

for i in range(1, n+1):
    left = i - k
    if left >= 0:
        ldif = (a[left] - left) % k
        if ldif < 0: ldif += k
        cnt[ldif] -= 1
    
    a[i] += a[i-1]
    dif = (a[i] - i) % k
    if dif < 0: dif += k
    if dif not in cnt:
        cnt[dif] = 0
        
    ans += cnt[dif]
    cnt[dif] += 1

print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    a = LI()
    s = [0]
    for i in a:
        s.append((s[-1]+i-1)%k)
    ans = 0
    d = defaultdict(lambda : 0)
    for i in range(n+1):
        ans += d[s[i]]
        d[s[i]] += 1
        j = i-k+1
        if j >= 0:
            d[s[j]] -= 1
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]


def bi(x, a):
    mi = 0
    ma = len(x) - 1
    while mi != ma:
        m = (mi + ma) // 2+1
        if x[m] < a:
            mi = m
        else:
            ma = m - 1
    return mi


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

c = {}
for l, j in enumerate(b):
    i = j % k
    if i in c:
        c[i].append(l)
    else:
        c[i] = [l]
j = 0
for i in c:
    i = c[i]
    i.sort()
    for m, l in enumerate(i):
        j += bi(i, l+k)-m
print(j)

Solution (Python):
from collections import defaultdict


def solve(n, k, a_list):
    b_list = [a - 1 for a in a_list]
    res_dict = defaultdict(list)
    res_dict[0].append(0)

    r = 0
    for i in range(n):
        r += b_list[i]
        r %= k
        res_dict[r].append(i + 1)

    res = 0
    for r in res_dict.keys():
        r_list = res_dict[r]
        if len(r_list) == 1:
            continue
        i = 0
        j = 0
        
        while i < len(r_list) - 1:
            if j < len(r_list) - 1:
                while r_list[j + 1] - r_list[i] < k:
                    j += 1
                    if j == len(r_list) - 1:
                        break
            res += j - i
            
            i += 1
    return res


def main():
    n, k = map(int, input().split())
    a_list = list(map(int, input().split()))
    res = solve(n, k, a_list)
    print(res)


def test():
    assert solve(5, 4, [1, 4, 2, 3, 5]) == 4
    assert solve(8, 4, [4, 2, 4, 2, 4, 2, 4, 2]) == 7
    assert solve(10, 7, [14, 15, 92, 65, 35, 89, 79, 32, 38, 46]) == 8


if __name__ == "__main__":
    
    main()

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]-1)%k
d = dict()
ans = 0
for i in range(n+1):
    if i >= k:
        d[a[i-k]] -= 1
    if a[i] in d:
        ans += d[a[i]]
        d[a[i]] += 1
    else:
        d[a[i]] = 1
print(ans)

Solution (Python):
import sys
from collections import defaultdict
import bisect
sys.setrecursionlimit(10**9)
N, K = map(int, input().split())
A = list(map(lambda x:int(x)-1, input().split()))
S = [0]*(N+1)
R = defaultdict(list)
R[0].append(0)
for i in range(N):
    S[i+1] = (S[i]+A[i])%K
    R[S[i+1]].append(i+1)
ans = 0
for i in range(N+1):
    a = bisect.bisect_right(R[S[i]], i)
    b = bisect.bisect_left(R[S[i]], i+K)
    ans+=b-a
print(ans)

Solution (Python):

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,K = inpl()
AA = inpl()

rAA = [0]
for a in AA:
    rAA.append(rAA[-1]+a)


AA = [(A+N-i)%K for i,A in enumerate(rAA)]


cnts = defaultdict(int)
ans = 0
for i,a in enumerate(AA):
    if i >= K:
        cnts[AA[i-K]] -= 1

    ans += cnts[a]
    cnts[a] += 1



print(ans)

Solution (Python):
import sys
from collections import defaultdict

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

n, k = na()
a = na()

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

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools
from collections import defaultdict

N,K,*A = map(int,read().split())

A = [0] + [x-1 for x in A]



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

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)