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, os
import collections

MOD = 10 ** 9 + 7

def solve(input_stream):
  N, K  = read_ints(input_stream)
  numbers = [int(i) - 1 for i in input_stream.readline().strip().split()]
  cumulative_sum = [0 for i in range(N + 1)]
  mods = {}
  ans = 0
  for index, number in enumerate(numbers):
    cumulative_sum[index + 1] = (cumulative_sum[index] + number) % K
  queue = []
  
  for index in range(N+1):
    if cumulative_sum[index] not in mods:
      mods[cumulative_sum[index]] = 0
    ans += mods[cumulative_sum[index]]
    mods[cumulative_sum[index]] += 1
    queue.append(cumulative_sum[index])
    if len(queue) == K:
      target = queue.pop(0)
      mods[target] -= 1
  return [str(ans)]

  


def read_ints(input_stream):
  return [i for i in map(int, input_stream.readline().strip().split())]

def read_int(input_stream):
  return int(input_stream.readline().strip())


if __name__ == "__main__":
    outputs = solve(sys.stdin)
    for line in outputs:
      print(line)

Solution (Python):
import bisect

def solve(n, k, a):
    s = [0] * (n+1)
    for i in range(n):
        s[i+1] = s[i] + a[i]
    D = {}
    for i in range(n+1):
        p = (s[i] - i) % k
        if not p in D:
            D[p] = []
        D[p].append(i)
    res = 0
    for vs in D.values():
        m = len(vs)
        for j, vj in enumerate(vs):
            i = bisect.bisect_left(vs, vj+k) - 1
            res += i - j
    return res

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

Solution (Python):

import sys

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
A=map(lambda a: (a-1)%K, A)

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

d=dict()    

ans=0
for i in range(N+1):
    x=S[i]%K
    if i==0:
        d[x]=1
    else:
        if x in d:
            if 2<=K:    
                ans+=d[x]   
            d[x]+=1
        else:
            d[x]=1      
        if 0<=i-K+1:
            x_head=S[i-K+1]%K  
            d[x_head]-=1

print ans

Solution (Python):

import sys
from collections import defaultdict

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
A=map(lambda a: (a-1)%K, A)

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

d=dict()    

ans=0
for i in range(N+1):
    x=S[i]%K
    if i==0:
        d[x]=1
    else:
        if x in d:
            if 2<=K:    
                ans+=d[x]   
            d[x]+=1
        else:
            d[x]=1      
        if 0<=i-K+1:
            x_head=S[i-K+1]%K  
            d[x_head]-=1

print ans

Solution (Python):

import sys
from collections import defaultdict

N,K=map(int, sys.stdin.readline().split())
if K==1:
    print 0
    quit()
A=map(int, sys.stdin.readline().split())
A=map(lambda a: (a-1)%K, A)

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

d=dict()    

ans=0
for i in range(N+1):
    x=S[i]%K
    if i==0:
        d[x]=1
    else:
        if x in d:
            if 2<=K:    
                ans+=d[x]   
            d[x]+=1
        else:
            d[x]=1      
        if 0<=i-K+1:
            x_head=S[i-K+1]%K  
            d[x_head]-=1

print ans

Solution (Python):

import sys
from collections import defaultdict

N,K=map(int, sys.stdin.readline().split())
if K==1:
    print 0
    quit()
A=map(int, sys.stdin.readline().split())
A=map(lambda a: (a-1)%K, A)

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

d=dict()    

ans=0
for i in range(N+1):
    x=S[i]%K
    if i==0:
        d[x]=1
    else:
        if x in d:
            ans+=d[x]   
            d[x]+=1
        else:
            d[x]=1      
        if 0<=i-K+1:
            x_head=S[i-K+1]%K  
            d[x_head]-=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,deque
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)
    Q=deque()
    ans=0
    for s in S:
        ans+=C[s]
        C[s]+=1
        Q.append(s)
        if(len(Q)==k):
            C[Q.popleft()]-=1
    print(ans)
resolve()

Solution (Python):
from collections import defaultdict
import bisect


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

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

T = [0] * (n + 1)
for i in range(1, n + 1):
    T[i] = (S[i] - i) % k



size = defaultdict(list)
for i in range(0, n + 1):
    size[T[i]].append(i)


ans = 0
for i in range(0, n + 1):
    
    
    
    index_i = bisect.bisect_left(size[T[i]], i)
    index_j = bisect.bisect_left(size[T[i]], i + k) - 1
    
    ans += (index_j - index_i)

print(ans)

Solution (Python):
n,k,*a=map(int, open(0).read().split())
b=[0]
for t in a:b+=(t-1+b[-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):
n,k,*a=map(int,open(0).read().split())
a=[0]+a
for i in range(n):a[i+1]=(a[i+1]-1+a[i])%k
d={}
c=0
for i,b in enumerate(a):
  v=d.get(b,0)
  c+=v
  d[b]=v+1
  j=i-k+1
  if j>=0:d[a[j]]=d.get(a[j],0)-1
print(c)

Solution (Python):
n,k,*a=map(int,open(0).read().split())
a=[0]+a
for i in range(n):a[i+1]=(a[i+1]-1+a[i])%k
d={}
c=0
for i,b in enumerate(a):
  v=d.get(b,0)
  c+=v
  d[b]=v+1
  j=i-k+1
  if j>=0:d[a[j]]=d.get(a[j],0)-1
print(c)

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

Solution (Python):
import collections

n,k=map(int,input().split())
a=list(map(int,input().split()))
sa = [0]
for i in range(n):
    sa.append(sa[i]+a[i])
    sa[i+1] -= 1
    sa[i+1] %= k
cd = collections.defaultdict(lambda:0)
res = 0
for i in range(n+1):
    cd[sa[i]] += 1
    if i >= k:
        cd[sa[i-k]] -= 1
    res += cd[sa[i]] - 1
print(res)

Solution (Python):
import numpy as np
from queue import Queue
n,k = map(int,input().split())
A = [a-1 for a in list(map(int,input().split()))]
A = np.cumsum(+np.array([0]+A))%k

dic = {}
ans = 0
Q = Queue()
for a in A:
    Q.put(a)
    if a in dic:
        ans += dic[a]
        dic[a] += 1
    else:
        dic[a] = 1
    if Q.qsize() == k:
        q = Q.get()
        dic[q] -= 1
    
print(ans)

Solution (Python):
from collections import defaultdict

n, k = map(int, input().split())
A = list(map(int, input().split()))
delta_count = defaultdict(int)
sum = [0]
delta_count[0] += 1
for i in range(n):
    sum.append(sum[i] + A[i])
ans = 0
for i in range(1, min(n + 1, k)):
    x = (sum[i] - i) % k
    ans += delta_count[x]
    delta_count[x] += 1
for i in range(min(n + 1, k), n + 1):
    delta_count[(sum[i - k] - i - k) % k] -= 1
    x = (sum[i] - i) % k
    ans += delta_count[x]
    delta_count[x] += 1
print(ans)

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

d = defaultdict(int)
ans = 0
q = Queue()

for j in range(n+1):
    ans += d[s[j]]
    d[s[j]] += 1
    q.put(s[j])
    if q.qsize() == k:
        d[q.get()] -= 1

print(ans)

Solution (Python):
from collections import defaultdict


n, k = map(int, input().split())
A = list(map(int, input().split()))
delta_count = defaultdict(int)
cumA = [0]
total = 0
for a in A:
    total += a
    total %= k
    cumA.append(total)

for i in range(1, min(n+1, k)):
    num = cumA[i]
    delta = (num - i) % k
    delta_count[delta] += 1

ans = delta_count[0]
left = 1
right = min(k-1, n)

while left <= n-1:
    popleft = (cumA[left] - left) % k
    delta_count[popleft] -= 1
    if right <= n-1:
        right += 1
        num = cumA[right]
        append = (num - right) % k
        delta_count[append] += 1

    desire = (cumA[left] - left) % k
    ans += delta_count[desire]
    left += 1

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque, Counter, defaultdict
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
import bisect
from logging import getLogger, StreamHandler, DEBUG, WARNING
logger = getLogger(__name__)
handler = StreamHandler()
handler.setLevel(DEBUG)
logger.setLevel(DEBUG)


logger.addHandler(handler)
def main():
    n, k = getList()
    nums = getList()
    acc = [0]
    tmp = 0
    for num in nums:
        tmp += num - 1
        tmp %= k
        acc.append(tmp)
    ans = 0
    df = {}
    for i in range(n + 1):
        if not acc[i] in df:
            df[acc[i]] = 1
        else:
            df[acc[i]] += 1
        ans += (df[acc[i]] - 1)
        if i >= k-1:
            df[acc[i-k+1]] -= 1



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

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

n += 1
ans = 0
m = dict()
temp = 0
b = []
for i in range(min(n, k)):
    temp = (temp + a[i]) % k
    c = (temp - (i % k) + k) % k
    b.append(c)
    if c in m.keys():
        ans += m[c]
        m[c] += 1
    else:
        m[c] = 1

for i in range(k, n):
    x = i % k
    m[b[x]] -= 1
    temp = (temp + a[i]) % k
    c = (temp - (i % k) + k) % k
    b[x] = c
    if c in m.keys():
        ans += m[c]
        m[c] += 1
    else:
        m[c] = 1

print(ans)

Solution (Python):
import sys
import itertools
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, readline().split()))
    a = list(map(lambda x: int(x) - 1, readline().split()))
    a = [0] + [i % k for i in list(itertools.accumulate(a))]
    d = collections.defaultdict(int)
    cnt = 0
    for i in range(n + 1):
        cnt += d[a[i]]
        d[a[i]] += 1
        if i >= k - 1:
            d[a[i-k+1]] -= 1
    print(cnt)


if __name__ == '__main__':
    solve()

Solution (Python):
from collections import defaultdict as dd
from itertools import accumulate
N, K = map(int, input().split())
As = [0] + list(map(int, input().split()))
S = list(accumulate(As))

ans = 0
counts = dd(int)
counts[0] = 1
for j in range(1, N+1):
    if j >= K:
        counts[(S[j-K] - (j-K)) % K] -= 1
    t = (S[j] - j) % K
    ans += counts[t]
    counts[t] += 1
print(ans)

Solution (Python):
from collections import defaultdict as dd
N, K = map(int, input().split())
A = list(map(int, input().split()))
S = [0]*(N+1)

for i in range(1, N + 1):
    S[i] = S[i - 1] + A[i - 1] - 1
    S[i] %= K
        
B = dd(int)  
cnt = 0
for j in range(1, N + 1):
    B[S[j - 1]] += 1
    if j - K >= 0:
        B[S[j - K]] -= 1
    cnt += B[S[j]]

print(cnt)

Solution (Python):
from collections import deque, defaultdict

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

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

ret = 0
d = defaultdict(deque)
for i in range(N+1):
    pair = Si_m_i[i]
    temp = d[pair]
    while temp and i-temp[0] >= K:
        temp.popleft()
    ret += len(temp)
    d[Si_m_i[i]].append(i)

print(ret)

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()))
S_=list(map(lambda t: (t[1]-t[0])%K,enumerate(accumulate([0]+A))))
count=0
C=defaultdict(int)
for t in range(1,N+1):
  C[S_[t-1]]+=1
  if t-K>=0:
    C[S_[t-K]]-=1
  count+=C[S_[t]]
print(count)

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

def solve(N, K, A):
    if K == 1:
        return 0
    
    S = [0 for _ in range(N+1)]
    for i in range(N):
        S[i+1] = S[i] + A[i]
    
    count_sum = 0
    count = dict()
    for j in range(1, N+1):
        j_mod_k = (S[j] - j) % K  
        if j == 1:
            for i in range(max(0, j-K+1), j):
                
                
                
                i_mod_k = (S[i] - i) % K
                if i_mod_k in count:
                    count[i_mod_k] += 1
                else:
                    count[i_mod_k] = 1
        else:
            if max(0, j-K+1) != max(0, (j-1)-K+1):
                i = max(0, (j-1)-K+1)
                i_mod_k = (S[i] - i) % K
                if i_mod_k in count:
                    if count[i_mod_k] == 1:
                        count.pop(i_mod_k)
                    else:
                        count[i_mod_k] -= 1
            i = j-1
            i_mod_k = (S[i] - i) % K
            if i_mod_k in count:
                count[i_mod_k] += 1
            else:
                count[i_mod_k] = 1
        if j_mod_k in count:
            count_sum += count[j_mod_k]
    return count_sum

if __name__ == '__main__':
    inputs = read()
    print('%d' % solve(*inputs))

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

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

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

from collections import defaultdict
cnt = defaultdict(int)

left = 0
right = k-1
if right > n:
    right = n

for i in range(right+1):
    cnt[s[i]] += 1

ans = 0
while left < right:
    ans += cnt[s[left]]-1
    if right == n:
        cnt[s[left]] -= 1
        left += 1
    else:
        cnt[s[left]] -= 1 
        left += 1
        right += 1
        cnt[s[right]] += 1 

print(ans)

Solution (Python):
from collections import defaultdict

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

N, K = gets()
A = gets()

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

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

print(ans)

Solution (Python):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines














from collections import defaultdict

from itertools import accumulate










def main():
	n,k=map(int,input().split())
	A=list(map(int,input().split()))
	S=[0]+list(accumulate(A))
	for i in range(n+1):
		S[i]-=i
		S[i]%=k
	
	dct=defaultdict(int)
	
	ans=0
	for j in range(n+1):
		dct[S[j]]+=1
		if j>=k:
			dct[S[j-k]]-=1
		ans+=dct[S[j]]-1
	print(ans)
	
if __name__ == "__main__":
		main()

Solution (Python):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines














from collections import defaultdict

from itertools import accumulate










def main():
	n,k=map(int,input().split())
	A=list(map(int,input().split()))
	S=[0]+list(accumulate(A))
	for i in range(n+1):
		S[i]-=i
		S[i]%=k
	
	dct=defaultdict(int)
	
	ans=0
	for j in range(n+1):
		dct[S[j]]+=1
		if j>=k:
			dct[S[j-k]]-=1
		ans+=dct[S[j]]-1
	print(ans)
	
if __name__ == "__main__":
		main()

Solution (Python):

from collections import deque
from collections import defaultdict


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

Solution (Python):
import math
import sys
import bisect
import array

m=10**9 + 7 
sys.setrecursionlimit(1000010)
(N,K) = map(int,input().split())
A = list( map(int,input().split())) 

B = list( map(lambda x: x % K, A))
C = [0]
x = 0
i = 0 
for b in B:
    x = (x + b ) % K 
    C.append((x-i-1) % K) 
    i += 1 
    


E={}


ans=0
for i in range(N+1):
    if C[i] in E:
        ans += E[C[i]]
        E[C[i]] = E[C[i]] + 1
    else:
        E[C[i]] = 1
    if i >= K-1:
        E[C[i-K+1]] = E[C[i-K+1]] - 1
        if E[C[i-K+1]] == 0:
             E.pop(C[i-K+1])

print(ans)
exit(0)

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

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

for i in range(2,len(a) + 1):
    acc_a[i] = (a[i - 1] + acc_a[i-1]) % k
ans = 0
count = {}
q = deque()
for i in acc_a:
    if i not in count:
        count[i] = 0
    ans += count[i]
    count[i] += 1
    q.append(i)
    if len(q) == k:
        count[q.popleft()] -= 1
print(ans)

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

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

for i in range(2,len(a) + 1):
    acc_a[i] = (a[i - 1] + acc_a[i-1]) % k
ans = 0
count = {}
q = deque()
for i in acc_a:
    if i not in count:
        count[i] = 0
    ans += count[i]
    count[i] += 1
    q.append(i)
    if len(q) == k:
        count[q.popleft()] -= 1
print(ans)

Solution (Python):
from collections import Counter

N, K = map(int, input().split())
A = list(map(lambda s: int(s) % K, input().split()))

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

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

    if i >= K:
        counts[cumAm1[i - K]] -= 1

    cur = cumAm1[i]
    ans += counts[cur]

    counts[cur] += 1

print(ans)

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

Solution (Python):

import queue
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] - 1) % K

v_set = set(S)
mp = {v: 0 for v in v_set}
ans = 0
q = queue.Queue()
for i in range(N + 1):
    ans += mp[S[i]]
    mp[S[i]] += 1
    
    q.put(S[i])
    if q.qsize() == K:
        mp[q.get()] -= 1

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np
from collections import defaultdict

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

A = [0] + [int(i)-1 for i in input().split()]


Acum = np.cumsum(A)
Acum = [i%K for i in Acum]

answer = 0
counter = defaultdict(int)




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

print(answer)

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np
from collections import defaultdict

N,K = map(int,input().split())
A = [0] + [int(i)-1 for i in input().split()]
Acum = np.cumsum(A)
Acum = [i%K for i in Acum]

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

Solution (Python):
from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


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


if __name__ == '__main__':
    main()

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

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
S := aの累積和
(Sj - Si) % k = j - i
ある整数mに対して
Sj - Si = m*k + j - i
Sj - j = m*k + Si - i
(Sj - j) - (Si - i) Ξ 0 (mod k)
(Sj - j) Ξ (Si - i) (mod k)
"""
n,k = LI()
a = LI()
s = [0] + list(accumulate(a))
ans = 0
d = defaultdict(int)
for j in range(n+1):
    t = (s[j] - j) % k
    if j >= k:
        x = (s[j-k] - (j-k)) % k
        d[x] -= 1
    ans += d[t]
    d[t] += 1
print(ans)

Solution (Python):
from collections import defaultdict
N,K=map(int, input().split())
A=list(map(int,input().split()))
"""count=0
for l in range(N):
    if A[l]%K==1:
        count+=1
for l in range(N-1):
    sum=A[l]
    for r in range(l+1,N):
        sum+=A[r]
        if sum%K==r-l+1:
            count+=1
print(count)"""
cum=[0]*(N+1)
for i in range(N):
    cum[i+1]=(cum[i]+A[i]-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 itertools
from collections import defaultdict

N ,K = map(int, input().split())
A = list(map(int, input().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)

Solution (Python):
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)

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+1]+a[i]-1)%k
from collections import defaultdict
d=defaultdict(int)
x=0
d[0]=1
for i in range(1,n+1):
  if i-k>=0:d[a[i-k]]-=1
  x+=d[a[i]]
  d[a[i]]+=1
print(x)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
from collections import deque,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])%k

    ans=0
    C=defaultdict(int)
    Q=deque()
    for s in S:
        ans+=C[s]
        C[s]+=1
        Q.append(s)
        if(len(Q)==k):
            C[Q.popleft()]-=1
    print(ans)
resolve()

Solution (Python):
import sys
from collections import defaultdict


		
def main():
	n, k = map(int, input().split())
	aal = list(map(int, input().split()))
	
	sss = [0]*(n+1)
	si=0
	for i, a in enumerate(aal):
		si+=a-1
		sss[i+1]=si%k
	
	count=0
	mkl_dict=defaultdict(lambda :0)
	for j in range(n+1):
		sj=sss[j]
		if j-k >= 0:
			mkl_dict[sss[j-k]]-=1
		count += mkl_dict[sj]
		mkl_dict[sj] += 1
			
	print(count)
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
import sys
from collections import defaultdict


		
def main():
	n, k = map(int, input().split())
	aal = list(map(int, input().split()))
	
	sss = [0]*(n+1)
	si=0
	for i, a in enumerate(aal):
		si+=a-1
		sss[i+1]=si%k
	
	count=0
	mkl_dict=defaultdict(lambda :0)
	for j in range(n+1):
		sj=sss[j]
		if j-k >= 0:
			mkl_dict[sss[j-k]]-=1
		count += mkl_dict[sj]
		mkl_dict[sj] += 1
			
	print(count)
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
from itertools import accumulate
from collections import defaultdict
N, K = map(int, input().split())
A = [0] + [a-1 for a in map(int, input().split())]
A_cum = list(accumulate(A))
A_cum = [a%K for a in A_cum]

ans = 0
dd = defaultdict(int)
q = []
for j in range(N+1):  
  ans += dd[A_cum[j]]
  dd[A_cum[j]] += 1
  q.append(A_cum[j])
  if len(q) == K:
    dd[q[0]] -= 1
    q.pop(0)
print(ans)

Solution (Python):
import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N, K = map(int, input().split())
A = list(map(int, input().split()))
res = 0
cs = [0] * (N + 1)
d = dd(list)
d[0].append(0)
for i in range(N):
  cs[i + 1] = cs[i] + A[i] - 1
  cs[i + 1] %= K
  d[cs[i + 1]].append(i + 1)
for i in range(N):
  x = bl(d[cs[i]], i) + 1
  y = bl(d[cs[i]], i + K)
  res += y - x
  
  
print(res)

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

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

S = [0] + [a % K for a in accumulate(a - 1 for a in A)]

C = Counter()
ans = 0
for i, s in enumerate(S):
    ans += C[s]
    C[s] += 1
    if i - K + 1 >= 0:
        C[S[i - K + 1]] -= 1

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
from itertools import count
from collections import defaultdict
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok



def main():
    N, K = mis()
    A = [0] + lmis()
    for i in range(1, len(A)):
        A[i] = ((A[i] - 1) + A[i-1]) % K
    
    C = defaultdict(int)
    ans = 0
    for i in range(len(A)):
        if i >= K:
            C[A[i-K]] -= 1
        a = A[i]
        ans += C[a]
        C[a] += 1
    print(ans)

main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    B=[0]*(N+1)
    for i in range(N):
        B[i+1]=(A[i]+B[i]-1)%K
    ans=0
    d={}
    for i in range(1,N+1):
        if i-K<0:
            if B[i-1] in d:
                d[B[i-1]]+=1
            else:
                d[B[i-1]]=1
        else:
            if B[i-1] in d:
                d[B[i-1]]+=1
            else:
                d[B[i-1]]=1
            d[B[i-K]]-=1
        if B[i] in d:
            ans+=d[B[i]]
    print(ans)
    

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict

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 = [x % k for x in s]
d = defaultdict(int)
ans = 0

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

print(ans)

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

    N, K = [int(i) for i in input().split()]
    
    A = [0] + [int(i) - 1 for i in input().split()]

    acc = list(accumulate(A))
    acc = [x % K for x in acc]  

    
    
    counter = defaultdict(int)  
    ans = 0
    for j, x in enumerate(acc):
        ans += counter[x]
        
        counter[x] += 1
        
        
        if j - K + 1 >= 0:
            counter[acc[j - K + 1]] -= 1
    return ans

print(e_rem_of_sum_is_num())

Solution (Python):
import itertools
from collections import defaultdict

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

A = list(map(int, input().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)

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):
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
input = sys.stdin.readline
n, k = map(int,input().split())
A = list(map(int,input().split()))

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



D = {}
S = [0] + S
ans = 0
for i in range(len(S)):
    key = (S[i] - i) % k

    if i >= k:
        j = i-k
        key1 = (S[j] - j) % k
        D[key1] -= 1
        try:
            ans += D[key1]
            
        except:
            ans += 0

    try:
        D[key] += 1
    except:
        D[key] = 1

for j in range(max(0, len(S)-k), len(S)):
    key1 = (S[j] - j) % k
    D[key1] -= 1
    try:
        ans += D[key1]
        
    except:
        ans += 0

print(ans)

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

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

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

memo = {}
cnt = 0
ans = 0
for i in range(n+1):
    if ruiseki[i] in memo:
        ans += memo[ruiseki[i]]

    if ruiseki[i] in memo:
        memo[ruiseki[i]] += 1
    else:
        memo[ruiseki[i]] = 1

    if cnt < k - 1:
        cnt += 1
    else:
        memo[ruiseki[i-cnt]] -= 1 

print(ans)