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 collections
n,k=map(int,input().split())
a=list(map(int,input().split()))
m=[0]
for i in range(n):
  m.append((m[-1]+a[i]))
for i in range(n+1):
  m[i]-=i
  m[i]%=k

ans=0
dict=collections.defaultdict(int)
for i in range(1,n+1):
  x=m[i]
  if i<=k-1:
    dict[m[i-1]]+=1
  else:
    dict[m[i-1]]+=1
    dict[m[i-k]]-=1
  ans+=dict[x]
print(ans)

Solution (Python):
import collections
n,k=map(int,input().split())
a=list(map(int,input().split()))
m=[]
m2=[0]
for i in range(n):
  m.append(a[i])
for i in range(n):
  m2.append((m2[-1]+m[i]))
for i in range(n+1):
  m2[i]-=i
  m2[i]%=k

ans=0
dict=collections.defaultdict(int)
for i in range(1,n+1):
  x=m2[i]
  if i<=k-1:
    dict[m2[i-1]]+=1
  else:
    dict[m2[i-1]]+=1
    dict[m2[i-k]]-=1
  ans+=dict[x]
print(ans)

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

    ans=0
    for key,group in groupby(T,lambda x:x[0]):
        G=[i for s,i in group]
        n=len(G)
        r=0
        for l in range(n):
            while(r+1<n and G[r+1]-G[l]<k):
                r+=1
            ans+=r-l
    print(ans)
resolve()

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(lambda x:int(x)-1,input().split()))
    S=[0]*(n+1)
    for i in range(n):
        S[i+1]=S[i]+A[i]
        S[i+1]%=k

    C=defaultdict(int)
    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)
resolve()

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(lambda x:int(x)-1,input().split()))
    S=[0]*(n+1)
    for i in range(n):
        S[i+1]=S[i]+A[i]
        S[i+1]%=k

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

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

A=list(map(lambda x:x%K-1,A))
sa=[0]*(N+1)
for i in range(1,N+1):
  sa[i]=(sa[i-1]+A[i-1])%K

c=Counter(sa[:K-1])

ans=0
for i in c.values():
  ans+=i*(i-1)//2
  
for i in range(K-1,N+1):
  ans+=c[sa[i]]
  c[sa[i-(K-1)]]-=1
  c[sa[i]]+=1

  
print(ans)

Solution (Python):
import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n, k = ril()
ls = ril()
acc = [0]
for x in ls:
    acc.append((acc[-1] + x - 1) % k)
counter = collections.Counter(acc[:k])
res = 0
for i in range(n + 1):
    res += counter[acc[i]] - 1
    counter[acc[i]] -= 1
    if i + k < n + 1:
        counter[acc[i + k]] += 1
print(res)

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

mods = defaultdict(int)
cnt = 0
tmp = 0
for i in range(min(k-1, n)):
	tmp = (tmp+a[i])%k
	mods[tmp] += 1
	cnt += 1

ans = 0
tmp2 = 0
for i in range(n):
	ans += mods[tmp2]
	tmp2 = (tmp2+a[i])%k
	mods[tmp2] -= 1
	if cnt < n:
		tmp = (tmp+a[cnt])%k
		mods[tmp] += 1
		cnt += 1

print(ans)

Solution (Python):
n,k=map(int,input().split())
l=list(map(int,input().split()))
if k==1:
    print(0)
    exit()
nl=[]
for i in range(n):
    nl.append((l[i]-1)%k)
r=[0]*(n+1)
for i in range(n):
    r[i+1]=(r[i]+nl[i])%k
p=[]
for i in range(n+1):
    p.append([r[i],i])
p.sort()
s=0
e=0
ans=0
f=0
while e<n+1:
    if p[s][0]!=p[e][0]:
        ans+=f*(f-1)//2
        s=e
        f=0
    else:
        if p[s][1]+k-1>=p[e][1]:
            f+=1
            e+=1
        else:
            ans+=f-1
            f-=1
            s+=1
print(ans+f*(f-1)//2)

Solution (Python):
from collections import defaultdict, deque

n, k = map(int, input().split())
a = tuple(map(int, input().split()))
acc = [0]
t = 0
for a_ in a:
    t = (t + a_ - 1) % k
    acc.append(t)

d = defaultdict(int)

ret = 0
count = 0
dq = deque()

for acc_ in acc:
    ret += d[acc_]
    d[acc_] += 1
    dq.append(acc_)
    if len(dq) >= k:
        v = dq.popleft()
        d[v] -= 1
print(ret)

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

N,K = m()

a = l()


aaa = [0 for i in range(N+1)]
aaa[1] = a[0] % K
for i in range(1,N):
    aaa[i+1] = aaa[i] + a[i]

count = 0
ddd = dict()
ddd[0] = 1
if K == 1:
    print(0)
else:
    for i in range(1,N+1):
        ppp = (aaa[i] - i)%K
        count += ddd.get(ppp,0)
        ddd[ppp] = ddd.get(ppp,0) + 1
        if i - K + 1 >= 0:
            ddd[(aaa[i-K+1] - i + K - 1)%K] -= 1
    print(count)

Solution (Python):
n,k=[int(j) for j in input().split()]
a=[int(j) for j in input().split()]
from itertools import accumulate
l=[0]+list(accumulate(a))
ll=[]
for i in range(n+1):
    ll.append((i-l[i])%k)
import collections
c=collections.Counter()
ans=0
for i in range(n+1):
    ans+=c[ll[i]]
    c[ll[i]]+=1
    if i>=k-1:
        c[ll[i-k+1]]-=1
print(ans)

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

if K == 1:
    print(0)
else:
    S, LUT, ans = [0], {0: 1}, 0
    for a in A:
        S.append(S[-1] + a)
    for i in range(1, N + 1):
        p = (S[i] - i) % K
        ans += LUT.get(p, 0)
        LUT[p] = LUT.get(p, 0) + 1
        if i - K + 1 >= 0:
            LUT[(S[i - K + 1] - i + K - 1) % K] -= 1
    print(ans)

Solution (Python):
n, k = map(int, input().split())
a = [int(ai) - 1 for ai in input().split()]
s = [0]
cur = 0
for ai in a:
    cur += ai
    cur %= k
    s.append(cur)

d = {}
ans = 0


for si in s[:k]:
     if si in d:
         d[si] += 1
     else:
        d[si] = 1
for key in d:
    val = d[key]
    if val > 1:
        ans +=  val * (val - 1) // 2


r = 0
for l in range(k, n+1):
    d[s[r]] -= 1
    if s[l] in d:
        ans += d[s[l]]
        d[s[l]] += 1
    else:
        d[s[l]] = 1
    r += 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 = [a - 1 for a in A]


S = [0] + list(accumulate(A))
S = [s % K for s in S]


ans = 0
counter = defaultdict(int)
for i, s in enumerate(S):
    ans += counter[s]  

    counter[s] += 1  
    if i - K + 1 >= 0:
        counter[S[i - K + 1]] -= 1  

print(ans)

Solution (Python):
def solve():
  from itertools import accumulate
  from sys import stdin
  
  f_i = stdin
  N, K = map(int, f_i.readline().split())
  A = map(int, f_i.readline().split())
  S = accumulate(a - 1 for a in A)
  S = (0, ) + tuple(s % K for s in S)
  
  rec = {}
  ans = 0
  for j, S_j in enumerate(S):
    if j >= K:
      rec[S[j-K]] -= 1
    if S_j in rec:
      ans += rec[S_j]
      rec[S_j] += 1
    else:
      rec[S_j] =1
  
  print(ans)

solve()

Solution (Python):

from itertools import accumulate
n, k = map(int, input().split())
a = list(map(int, input().split()))
s = [0] + list(accumulate(a))


def f(x):
    return (x + n * k) % k


ans = 0
dic = {}
for i in range(n + 1):
    if i >= k:
        prev = f(s[i - k] - (i - k))
        dic[prev] -= 1

    cur = f(s[i] - i)
    if cur in dic:
        ans += dic[cur]
        dic[cur] += 1
    else:
        dic[cur] = 1

print(ans)

Solution (Python):
def examE():
    N, K = LI()
    A = LI()
    sumA = [0]*(N+1)
    for i in range(1,N+1):
        sumA[i] = sumA[i-1]+A[i-1]
    d = defaultdict(int)
    ans = 0
    
    que = deque()
    for i,a in enumerate(sumA):
        
        if que and que[0][0] <= (i-K):
            d[que.popleft()[1]] -= 1
        cur = (a-i)%K
        ans +=d[cur]
        d[cur] +=1
        que.append((i,cur))

    print(ans)
    return

def examF():
    return

import sys,copy,bisect,itertools,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 LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examE()

Solution (Python):
N, K = map(int, input().split())
A = list(map(lambda x: int(x)-1, input().split()))
sa = [0]
for a in A:
    sa.append((sa[-1] + a) % K)
d = {0: 1}
ans = 0
for i in range(1, N+1):
    if i >= K:
        d[sa[i-K]] -= 1
    v = d.get(sa[i], 0)
    ans += v
    d[sa[i]] = v + 1
print(ans)

Solution (Python):
from collections import defaultdict, deque

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

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

cnt = defaultdict(int)
que = deque([])
ans = 0

for i, c in enumerate(cumA):
    while que and que[0][0] <= i - K:
        cnt[que.popleft()[1]] -= 1
    diff = (i - c) % K
    ans += cnt[diff]
    cnt[diff] += 1
    que.append((i, diff))
print(ans)

Solution (Python):
from collections import defaultdict
import itertools

N, K = map(int, input().split())
A = [int(c)-1 for c in input().split()]
A = [0] + A
Acum = list(itertools.accumulate(A))
Acum = [x%K for x in Acum]

counter = defaultdict(int)

ans = 0
for i,x in enumerate(Acum):
  ans += counter[x]
  counter[x] += 1
  if i>=K-1:
    counter[Acum[i-K+1]] -= 1
print(ans)

Solution (Python):
from collections import defaultdict
from itertools import accumulate
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

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


ans = 0
D = defaultdict(int)
for l in range(N+1):
    t = (A_acc[l]-l) % K
    if l>=K:
      r = (A_acc[l-K]-(l-K))
      D[r%K]-=1
    ans += D[t]
    D[t] += 1


print(ans)

Solution (Python):

from collections import defaultdict


def getlist():
	return list(map(int, input().split()))


def main():
	N, K = getlist()
	A = getlist()
	for i in range(N):
		A[i] -= 1

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

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

if __name__ == '__main__':
	main()

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] - 1) % k


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





print(ans)

Solution (Python):
from collections import defaultdict

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

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

count = defaultdict(int)
count[0] = 1

prefix = [0]*(n+1)
ans = 0

for i in range(n):
  pre = prefix[i+1] = (prefix[i] + seq[i] - 1)%k
  
  if i >= k - 1:
    count[prefix[i - k + 1]] -= 1
  ans += count[pre]
  count[pre] += 1
print(ans)

Solution (Python):


import sys
from collections import defaultdict
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()

A = [(a-1)%K for a in LIST()]


acc = [0] + list(accumulate(A))
acc = [a%K for a in acc]

cnt = defaultdict(int)
ans = 0
for i, a in enumerate(acc):
    
    ans += cnt[a]
    
    cnt[a] += 1
    
    if i - K + 1 >= 0:
        cnt[acc[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()))
    X = [0] * (N+1)
    for i, a in enumerate(A):
        X[i+1] = (X[i] + a - 1) % K
    cnt = defaultdict(int)
    ans = 0
    for i in range(N+1):
        if i >= K:
            cnt[X[i-K]] -= 1
        ans += cnt[X[i]]
        cnt[X[i]] += 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
n,k = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
s = [0]
for i in range(len(a)):
    s.append(s[-1]+a[i])
for i in range(len(s)):
    s[i] = (s[i] - i) % k

d = {0:1}
ans = 0
for j in range(1,n+1):
    if s[j] in d:
        d[s[j]] += 1
    else:
        d[s[j]] = 1
    if j >= k:
        d[s[j-k]] -= 1
    ans += d[s[j]] - 1
    
    
print(ans)

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time

def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()

input=lambda: sys.stdin.readline().rstrip()

show_flg=False


n,k=LI()
a=LI()
b=[k-1]
for i in range(n):
    b.append((b[-1]+a[i])%k)
b=[(b[i]-i)%k for i in range(n+1)]
ans=0
dc=defaultdict(int)
show(a)
show(b)
for i in range(n+1):
    if i>=k:
        dc[b[i-k]]-=1
    ans+=dc[b[i]]
    
    
    dc[b[i]]+=1

print(ans)

Solution (Python):
import sys
import itertools
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, input().rstrip('\n').split()))
    ls = [0] + list(map(lambda x: int(x) - 1, input().rstrip('\n').split()))
    ls = [i % k for i in list(itertools.accumulate(ls))]
    
    d = collections.defaultdict(int)
    t = 0
    for i, x in enumerate(ls):
        t += d[x]
        d[x] += 1
        if i >= k - 1:
            d[ls[i - k + 1]] -= 1
    print(t)


if __name__ == '__main__':
    solve()

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] - 1) % k


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



if k == 1:
    print(0)
else:
    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] - 1) % 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):
n,k=map(int,input().split())
a=list(map(int,input().split()))
a=list(map(lambda x:x-1 ,a))

s=[0]
for i in range(n):
    s.append(s[-1]+a[i])
s=list(map(lambda x:x%k,s))
from collections import defaultdict
d=defaultdict(int)
d[0]=1
ans=0

for i in range(1,n+1):
    if i>=k:
        d[s[i-k]]-=1
    ans+=d[s[i]]
    d[s[i]]+=1
print(ans)

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

if k==1:
    print(0)
    exit()
s=[0]
for i in range(n):
    s.append(s[-1]+a[i])
s=list(map(lambda x:x%k,s))
from collections import defaultdict
d=defaultdict(int)
d[0]=1
ans=0

for i in range(1,n+1):
    ans+=d[s[i]]
    d[s[i]]+=1
    if i>=k-1:
        d[s[i-k+1]]-=1
print(ans)

Solution (Python):
import sys
from collections import defaultdict
from copy import deepcopy
import itertools
input = sys.stdin.readline



N, K = map(int, input().split())
A = list(map(int, input().split()))
S = [0] + list(itertools.accumulate(A))
"""
「iからjまで」--->「0からjまで」-「0から(i - 1)まで」
に分解すれば、求める条件は
(S[j] - S[i]) % K = j - i
と書ける。これを式変形して
S[j] - j = S[i] - i mod K "with j - i < K"
とすれば、次を示せばよい：

For 1 <= j <= N, count the number of j - K < i < j
such that S[j] - j = S[i] - i mod K
"""

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

d = defaultdict(int)
d[(S[0] - 0) % K] = 1

ans = 0
for j in range(1, N + 1):
    x = (S[j] - j) % K
    ans += d[x]
    d[x] += 1
    if j - K >= -1:
        y = (S[j - K + 1] - (j - K + 1)) % K
        d[y] -= 1

print(ans)

Solution (Python):
n,k,*a=map(int, open(0).read().split())
b=[0]*-~n
for i in range(n):b[i+1]=(a[i]+b[i]-1)%k
d={k:0}
a=0
for l,r in zip([k]*min(k,n+1)+b,b):d[l]-=1;t=d.get(r,0);a+=t;d[r]=t+1
print(a)

Solution (Python):
from itertools import accumulate
from collections import Counter
n, k, *a = map(int, open(0).read().split())
a = [x % k - 1 for x in a]
a = [0] + [x % k for x in accumulate(a)]
d = Counter()
ans = 0
for l, r in zip([k] * min(k, n + 1) + a, a):
	d[l] -= 1
	ans += d[r]
	d[r] += 1
print(ans)

Solution (Python):
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n,k=MI()
    aa=LI()
    cs=[0]*(n+1)
    s=0
    for i,a in enumerate(aa,1):
        cs[i]=(cs[i-1]+a-1)%k
    
    cnt=defaultdict(int)
    ans=0
    for i,c in enumerate(cs):
        if i-k>=0:cnt[cs[i-k]]-=1
        ans+=cnt[c]
        cnt[c]+=1
    print(ans)

main()

Solution (Python):
import numpy
N,K=map(int,input().split())

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

A=list(map(int,input().split()))
S=[0]+list(numpy.cumsum(A)) 
S2=[(S[i]-i)%K for i in range(N+1)]

d = {}
ans = 0
for j in range(1,N+1):
    if j>K-1:
        if S2[j-K] in d:
            d[S2[j-K]] -= 1
        
    if S2[j-1] in d:
        d[S2[j-1]] += 1
    else:
        d[S2[j-1]] = 1
        
    if S2[j] in d:
        ans += d[S2[j]]
print(ans)

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

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

d = Counter()

A = [0] + list(accumulate(A))
A = [a % K for a in A]

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

print(ans)

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

for j in range(1,N+1):
    if j-K >= 0:
        dict1[(S[j-K]-j+K)%K] -= 1
    if (S[j]-j)%K in dict1:
        cnt += dict1[(S[j]-j)%K]
        dict1[(S[j]-j)%K] += 1
    else:
        dict1[(S[j]-j)%K] = 1
print (cnt)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,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
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_()
    ans = 0
    before = defaultdict(int)
    *cumsum,=accumulate(A)
    for i,a in enumerate(cumsum):
        cumsum[i] = a%K
    
    for i,a in enumerate(cumsum):
        if i >= K:
            before[cumsum[i-K]]-=1
        ans += before[a]
        before[a]+=1

    ans += cumsum[:K-1].count(0)
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n, k = map(int, input().split())
m = list(map(int, input().split()))
T = [0] * (n + 1)

b = 0
for i, a in enumerate(m):
    b += a - 1
    b %= k
    T[i + 1] = b

tmp = {}
count = 0

for i, b in enumerate(T):
    if i >= k:
        tmp[T[i - k]] -= 1

    if b in tmp:
        count += tmp[b]
        tmp[b] += 1
    else:
        tmp[b] = 1

print(count)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
A = LIST()

A_acc = list(accumulate(A))
S = [0] + A_acc
S = [(S[i]-i)%K for i in range(N+1)]

ans = 0
dic = defaultdict(int)

for i, x in enumerate(S):
	ans += dic[x]  
	dic[x] += 1
	if i >= K-1:  
		dic[S[i-K+1]] -= 1

print(ans)

Solution (Python):
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a=[i-1 for i in a]
    from itertools import accumulate
    import bisect
    a=[0]+list(accumulate(a))
    d=dict()
    a=[i%k for i in a]
    cnt=0
    for j,i in enumerate(a):
        if i not in d.keys():
            d[i]=[j]
        else:
            d[i].append(j)
    for l in d.values():
        for j,i in enumerate(l):
            cnt+=bisect.bisect_left(l,i+k)-j-1
    print(cnt)
main()

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

a_cs = [0] * (n + 1)
for i in range(n):
    a_cs[i + 1] = a_cs[i] + a[i]

d = defaultdict(list)
for i in range(n + 1):
    d[(a_cs[i] - i) % k].append(i)

ans = 0
for l in range(n):
    idx_1 = bisect_right(d[(a_cs[l] - l) % k], l)
    idx_2 = bisect_left(d[(a_cs[l] - l) % k], l + k)
    ans += idx_2 - idx_1

print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def solve():
    n, k = LI()
    a = LI_()
    ab = a[::1]
    a[0] = a[0] % k
    for i in range(n - 1):
        a[i + 1] = (a[i] + a[i + 1]) % k
    ans = 0
    q = deque([0])
    d = defaultdict(int)
    d[0] += 1
    for x, i in enumerate(a):
        q.append(i)
        if len(q) == k+1:
            x = q.popleft()
            d[x] -= 1
        ans += d[i]
        d[i] += 1
    print(ans)
    return



if __name__ == '__main__':
    solve()

Solution (Python):
import sys
from collections import Counter
from itertools import accumulate
read = sys.stdin.read

N, K, *A = map(int, read().split())
a = list(accumulate([0] + A))
a = [(a[i] - i) % K for i in range(N + 1)]

answer = 0
if N < K:
    for i in Counter(a).values():
        answer += i * (i - 1) // 2
else:
    dic = Counter(a[:K])
    for i in dic.values():
        answer += i * (i - 1) // 2
    here = K
    for i, x in enumerate(a[K:]):
        dic[a[i]] -= 1
        answer += dic[x]
        dic[x] += 1

print(answer)

Solution (Python):
import sys
from collections import defaultdict
from itertools import accumulate
read = sys.stdin.read

N, K, *A = map(int, read().split())
a = list(accumulate([0] + A))
a = [(a[i] - i) % K for i in range(N + 1)]

answer = 0
dic = defaultdict(int)

for i, x in enumerate(a):
    answer += dic[x]
    dic[x] += 1
    if i >= K - 1:
        dic[a[i - K + 1]] -= 1

print(answer)

Solution (Python):
import sys
from collections import Counter
from itertools import accumulate
read = sys.stdin.read

N, K, *A = map(int, read().split())
a = list(accumulate([0] + A))
a = [(a[i] - i) % K for i in range(N + 1)]


def cmb(x):
    return x * (x - 1) // 2


answer = 0
if N < K:
    for i in Counter(a).values():
        answer += cmb(i)
else:
    dic = Counter(a[:K])
    for i in dic.values():
        answer += cmb(i)
    here = K
    for i, x in enumerate(a[K:]):
        dic[a[i]] -= 1
        answer += dic[x]
        dic[x] += 1

print(answer)

Solution (Python):
from collections import defaultdict

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

S = [0] * (N + 1)
for i in range(N):
    S[i + 1] = S[i] + A[i]

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

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

a_cs = [0] * (n + 1)
for i in range(n):
    a_cs[i + 1] = a_cs[i] + a[i]

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

    
    ans += d[(a_cs[j] - j) % k]

    d[(a_cs[j] - j) % k] += 1

print(ans)