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

Solution (Python):
from itertools import accumulate
from collections import defaultdict
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = accumulate([0]+ A)
C = [(b-i)%K for i, b in enumerate(B)]
cnt = defaultdict(int)
cnt[C[0]] = 1
res = 0
for i in range(1, N+1):
    if i >= K:
        cnt[C[i-K]] -= 1
    res += cnt[C[i]]
    cnt[C[i]] += 1
print(res)

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, A))

"""
j - i < K and
Sj - Si == j - i (mod K)
Sj - j == Si - i (mod K) この変形が肝だ…
"""

S = [0 for _ in range(N+1)]
for i in range(N):
  S[i+1] = (S[i] + A[i] - 1) % K
ans = 0
C = Counter(S[:K])
for k,v in C.items():
  ans += v * (v-1) // 2
  
for i in range(K,N+1):
  deln = S[i-K]
  C[deln] -= 1
  addn = S[i]
  if addn in C:
    ans += C[addn]
    C[addn] += 1
  else:
    C[addn] = 1
    
print(ans)

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, A))

"""
j - i < K and
Sj - Si == j - i (mod K)
Sj - j == Si - i (mod K) この変形が肝だ…
"""

S = [0 for _ in range(N+1)]
for i in range(N):
  S[i+1] = (S[i] + A[i] - 1) % K
ans = 0
C = Counter(S[:K])
for k,v in C.items():
  ans += v * (v-1) // 2
  
for i in range(K,N+1):
  deln = S[i-K]
  C[deln] -= 1
  addn = S[i]
  if addn in C:
    ans += C[addn]
    C[addn] += 1
  else:
    C[addn] = 1
    
print(ans)

Solution (Python):
from itertools import accumulate
n,k=map(int,input().split())
a=list(map(int,input().split()))
x=[0]+list(accumulate(a))
mods=dict()
for i in range(n+1):
    now=(x[i]-i)%k
    if now in mods:
        mods[now].append(i)
    else:
        mods[now]=[i]
ans=0
from bisect import bisect_left


for i in mods:
    l=len(mods[i])
    for j in range(l):
        b=bisect_left(mods[i],mods[i][j]+k)-1
        ans+=(b-j)
print(ans)

Solution (Python):
from collections import defaultdict


def main():
    N, K = list(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 = [(s - i) % K for i, s in enumerate(S)]
    counter = defaultdict(int)
    ans = 0
    for j in range(N + 1):
        if j >= K:
            counter[T[j - K]] -= 1
        ans += counter[T[j]]
        counter[T[j]] += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
a = list(map(int, input().split()))
def cumsum(a):
    """※ aを破壊する
    l[i] = sum(a[:i]) なるlを返す
    sum(a[i:j]) == l[j+1] - l[i]
    """
    c = 0
    n = len(a)
    a.insert(0, 0)
    for i in range(1, n+1):
        a[i] = a[i-1]+a[i]
    return a
a = cumsum(a)
aa = [((item - i)%k) for i,item in enumerate(a)]
ans = 0
from collections import defaultdict
c = defaultdict(int)
for i in range(min(k, len(aa))):
    c[aa[i]] += 1
for i,item in enumerate(aa):
    c[item] -= 1

    ans += c[item]
    if i+k<n+1:
        c[aa[i+k]] += 1
print(ans)

Solution (Python):
import sys
import math
import bisect
import heapq
from collections import Counter


def input():
    return sys.stdin.readline().rstrip()


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

    AS = [0]

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

    C = dict()
    C[0] = 1
    current = 0
    for j in range(1, N + 1):
        if j > K-1:
            C[AS[j - K]] -= 1
        if AS[j] in C:
            current += C[AS[j]]
            C[AS[j]] += 1
        else:
            C[AS[j]] = 1

    print(current)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

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

val_cnt = {}
val_cnt[0] = 1
val_q = deque([0])
if k == 1:
    print(0)
    exit()

ans = 0
curr_sum = 0
for i in range(n):
    curr_sum += al[i]
    curr_sum %= k
    val = (curr_sum - (i+1))%k
    val_cnt.setdefault(val,0)
    ans += val_cnt[val]
    val_cnt[val] += 1
    val_q.append(val)
    if len(val_q) >= k:
        poped = val_q.popleft()
        val_cnt[poped] -= 1

print(ans)

Solution (Python):
import sys 
import numpy as np
from collections import defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K = map(int, readline().split())
A = [0] + list(map(int,readline().split()))
S = np.cumsum(A)
dic = defaultdict(int)
ans = 0
SS = [0] * (N+1)
for i in range(1,N+1):
    rem = (S[i]-i) % K
    SS[i] = rem

for i in range(N+1):
    if i >= K:
        dic[SS[i-K]] -= 1
    ans += dic[SS[i]]
    dic[SS[i]] += 1
print(ans)

Solution (Python):
import sys

def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  

N,K = LI()
A = LI()

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

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

from collections import defaultdict



if N < K:
    d = defaultdict(int)
    for n in B:
        d[n] += 1
    ans = 0
    for n in d.keys():
        m = d[n]
        ans += m*(m-1)//2
    print(ans)
else:
    d = defaultdict(int)
    ans = 0
    for i in range(N):  
        if i == 0:
            for j in range(K):
                d[B[j]] += 1
            ans += d[B[i]]-1
        elif i <= N-K+1:
            d[B[K+i-1]] += 1
            d[B[i-1]] -= 1
            ans += d[B[i]]-1
        else:
            d[B[i-1]] -= 1
            ans += d[B[i]]-1
    print(ans)

Solution (Python):




from collections import defaultdict


def cnt_func(X):
    res = 0
    right = 0
    L = len(X)
    for i in range(L):
        while right+1 < L and X[right+1] < K+X[i]:
            right += 1
        res += right-i
    return res


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

A = list(map(int, input().split()))
A.insert(0, 0)
for i in range(1, N+1):
    A[i] += A[i-1]
B = [0 for i in range(N+1)]
for i in range(N+1):
    B[i] = (A[i]-i) % K
ans = 0
Mod = defaultdict(list)
for i in range(N+1):
    Mod[B[i]].append(i)
for X in Mod.values():
    ans += cnt_func(X)
print(ans)

Solution (Python):




from collections import defaultdict


def cnt_func(X):
    res = 0
    right = 0
    L = len(X)
    for i in range(L):
        while right+1 < L and X[right+1] < K+X[i]:
            right += 1
        res += right-i
    return res


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

A = list(map(int, input().split()))
A.insert(0, 0)
for i in range(1, N+1):
    A[i] += A[i-1]
B = [0 for i in range(N+1)]
for i in range(N+1):
    B[i] = (A[i]-i) % K
ans = 0
Mod = defaultdict(list)
for i in range(N+1):
    Mod[B[i]].append(i)
for X in Mod.values():
    ans += cnt_func(X)
print(ans)

Solution (Python):
from collections import defaultdict

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

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

ctr = defaultdict(int)
ans = 0
for j in range(N + 1):
    ans += ctr[y[j]]
    ctr[y[j]] += 1
    if j - K + 1 >= 0:
        ctr[y[j - K + 1]] -= 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, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
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 = 10 ** 9 + 7


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

D = defaultdict(int)
ans = 0
for i in range(n + 1):
    if i >= k:
        D[L[i - k]] -= 1
    ans += D[L[i]]
    D[L[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, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
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 = 10 ** 9 + 7


n, k = LI()
A = [0] + LI()
for i in range(1, n + 1):
    A[i] = (A[i] + A[i - 1] - 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):
N,K=map(int,input().split())
A=list(map(int,input().split()))
DP=dict()
if K==1:
  print(0)
  exit()
DP[0]=1
P=0
Y=[0]*(N+1)
for i in range(N):
  Y[i+1]=(Y[i]+A[i]-1)%K
  P+=DP.get(Y[i+1],0)
  DP[Y[i+1]]=DP.get(Y[i+1],0)+1
  if i>=K-2:
    DP[Y[i-K+2]]-=1
print(P)

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

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

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

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  


N, K = na()

A_array = na()

cusum = 0
mod_array = [0]
for i, a in enumerate(A_array):
    cusum = (cusum + a) % K
    mod = (cusum + K - (i+1)) % K
    mod_array.append(mod)



ans = 0
mod_queue = []
cnt_dic = defaultdict(int)
for i, v in enumerate(mod_array):
    heapq.heappush(mod_queue, (i, 1, v))

while(len(mod_queue)):
    i, q, v = heapq.heappop(mod_queue)
    if q == 1:
        ans += cnt_dic[v]
        cnt_dic[v] += 1
        if i + K <= N:
            heapq.heappush(mod_queue, (i+K-0.5, 2, v))
    else:
        cnt_dic[v] -= 1
    

print(ans)

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

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

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

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

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

Solution (Python):
from collections import Counter
def solve():
    ans = 0
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    cum = [0]*(N+1)
    for i in range(N):
        cum[i+1] = (cum[i]+A[i])%K
    for i in range(N):
        cum[i+1] = (i+1-cum[i+1])%K
    if N<K:
        c = Counter(cum)
        for v in c.values():
            ans += v*(v-1)//2
    else:
        c = Counter(cum[:K-1])
        for i in range(N):
            c[cum[i]] -= 1
            if i+K-1<=N:
                c[cum[i+K-1]] += 1
            ans += c[cum[i]]
    return ans
print(solve())

Solution (Python):



from collections import defaultdict
N, K = map(int, input().split())
*A, = map(int, input().split())

A = [0]+A
d = []
c = defaultdict(int)
x = 0
ans = 0
for i, a in enumerate(A):
    x += a - 1
    x %= K

    d.append(x)
    if i-K >= 0:
        c[d[i-K]] -= 1
    ans += c[x]
    c[x] += 1

print(ans)

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

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

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

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

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





mods = As % K
csum_mods = np.cumsum(mods)
magic_array = (csum_mods - np.arange(0, N+1)) % K

indices = defaultdict(list)
for i, m in enumerate(magic_array.tolist()):
    indices[m].append(i)

ans = 0
for ls in indices.values():
    j = 1
    for i in range(len(ls)):
        while j < len(ls):
            if ls[j] - ls[i] < K:
                j += 1
            else:
                break
        ans += j - i - 1
        
print(ans)

Solution (Python):
from collections import Counter


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

cnt = 0
C = Counter()
for r in range(N + 1):
    R = (S[r] - r) % K
    cnt += C[R]
    C[R] += 1
    l = r - (K - 1)
    if l >= 0:
        L = (S[l] - l) % K
        C[L] -= 1

print(cnt)

Solution (Python):
from collections import Counter


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]

cnt = 0
C = Counter()
for r in range(N + 1):
    R = (S[r] - r) % K
    cnt += C[R]
    C[R] += 1
    l = r - (K - 1)
    if l >= 0:
        L = (S[l] - l) % K
        C[L] -= 1

print(cnt)

Solution (Python):
from collections import defaultdict

N, K = map(int, input().split())
A = list(map(int, input().split()))
cum = [0]*(N+1)
for i in range(1,N+1):
    cum[i] = cum[i-1] + A[i-1]
ans = 0
dic = defaultdict(int)
v_by_indx = defaultdict(int)
for i in range(N+1):
    if i-K >= 0:
        dic[v_by_indx[i-K]] -= 1
    diff = (cum[i]-i)%K
    ans += dic[diff]
    dic[diff] += 1
    v_by_indx[i] = diff
print(ans)

Solution (Python):
from collections import defaultdict

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

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

d = defaultdict(int)
l, r = 0, 0
ans = 0
while r <= N:
    a = Acc[r]
    ans += d[a]
    d[a] += 1
    r += 1
    if r - l >= K:
        d[Acc[l]] -= 1
        l += 1
print(ans)

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


def solve():

    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    S = [0 for _ in range(N + 1)]

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

    d = dict()
    for i in range(N + 1):
        k = S[i] % K
        if k in d:
            d[k].append(i)
        else:
            d[k] = [i]

    

    ans = 0
    for k, v in d.items():
        if len(v) <= 1:
            continue
        else:
            for i in range(len(v)):
                s = v[i] + K - 1
                si = bisect.bisect_right(v, s)
                ans += (si - i) - 1
                

    print(ans)


if __name__ == '__main__':
    solve()

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

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

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

ans = 0
counter = defaultdict(int)
queue = []
for i,s in enumerate(S):
  t = (s-i) % K

  ans += counter[t]
  counter[t] += 1

  queue.append(t)
  if len(queue) >= K:
    counter[queue[0]] -= 1
    queue.pop(0)

print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,k = LI()
    aa = LI()

    c = collections.defaultdict(int)
    c[0] = 1
    t = [0]
    r = 0
    for i in range(n):
        a = aa[i]
        tt = (t[-1] + a - 1) % k
        t.append(tt)
        if i >= k-1:
            
            c[t[i-k+1]] -= 1
        r += c[tt]
        c[tt] += 1
        

    return r

print(main())

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]
mp={0:1}
ans=0
for t in range(n):
  i=a[t]
  
  if t>=k-1:
    mp[dp[-k]]-=1  
    
  num=(dp[-1]+i-1)%k
  if num in mp.keys():
    ans += mp[num]
    mp[num] += 1
  else:
    mp[num] = 1
  dp.append(num)

print(ans)

Solution (Python):
from collections import Counter

N, K = map(int, input().split())
*A, = map(int, input().split())
MOD = 10**9+7
S = [0]*(N+1)
c = Counter()
c[0] = 1
ans = 0

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

print(ans)

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

Solution (Python):
N,K=map(int,input().split())
A=list(map(lambda x:int(x)%K,input().split()))
cum=[0]*(N+1)
for i in range(N):
    cum[i+1]=(cum[i]+A[i])

x=[(cum[i]-i)%K for i in range(N+1)]
dic={}
ans=0
for i in range(N+1):
    if i>=K:
        dic[x[i-K]]-=1
    ans+=dic.get(x[i],0)
    if not x[i] in dic:
        dic[x[i]]=1
    else:
        dic[x[i]]+=1
print(ans)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

rui=ruiseki(a)



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

Solution (Python):
from collections import defaultdict

n, k = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
shukei = defaultdict(int)



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


ans = 0
if k > n + 1:
    for i in range(n + 1):
        shukei[T[i]] += 1
    for key, num in shukei.items():
        ans += num * (num - 1) // 2
else:
    shukei = defaultdict(int)
    for i in range(k):
        shukei[T[i]] += 1
    for key, num in shukei.items():
        ans += num * (num - 1) // 2
    for i in range(k, n + 1):
        j = i - k
        shukei[T[j]] -= 1
        temp = T[i]
        num = shukei[temp]
        ans += num
        shukei[temp] += 1
print(ans)

Solution (Python):
from collections import defaultdict as dd
N, K = map(int, input().split())
a = list(map(int, input().split()))
b = [val-1 for val in a]
c = [0]*(N+1)
for i,val in enumerate(a):
    c[i+1] = (c[i] + val-1)%K

dic = dd(int)
K2 = min(N,K-1)
right = K2
for k,val in enumerate(c[1:K2+1]):
    dic[val] += 1
res = 0

prev = 0
for val in c[1:]:
    tgt = prev
    res += dic[tgt]
    if right!=N:
        right += 1
        dic[c[right]] += 1
    dic[val] = max(0,dic[val]-1)
    prev = val
print(res)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = list(map(int, readline().split()))
    a = [0] + list(map(int, readline().split()))
    from collections import Counter
    b = [0] * (n + 1)

    cur = 0
    for i, x in enumerate(a):
        cur += x
        b[i] = (cur - i) % k

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

    print(ans)


if __name__ == '__main__':
    main()

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

n,k = map(int,readline().split())
if k == 1:
  print(0)
  exit()
  
a = [0]+[int(i) for i in readline().split()]
for i in range(1,n+1):
  a[i] = a[i-1]+a[i]
  
a = [(ai-i)%k for i,ai in enumerate(a)]

from collections import Counter,deque
c = Counter({a[0]:1})
d = deque([a[0]])
ans = 0
cnt = 1
for j,aj in enumerate(a[1:]):
  ans += c[aj]
  d.append(aj)
  c.update({aj:1})
  cnt += 1
  if cnt >= k:
    p = d.popleft()
    c.update({p:-1})
  
print(ans)

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

n,k = map(int,readline().split())
if k == 1:
  print(0)
  exit()
  
a = [0]+[int(i) for i in readline().split()]
for i in range(1,n+1):
  a[i] = a[i-1]+a[i]
  
a = [(ai-i)%k for i,ai in enumerate(a)]

from collections import Counter,deque
c = Counter({a[0]:1})
d = deque([a[0]])
ans = 0
cnt = 1
for j,aj in enumerate(a[1:]):
  ans += c[aj]
  d.append(aj)
  c.update({aj:1})
  cnt += 1
  if cnt >= k:
    p = d.popleft()
    c.update({p:-1})
  
print(ans)

Solution (Python):
import bisect
import collections
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.insert(0,0)
cuml=[0]*(N+1)
cuml[0]=A[0]
l=[]
cuml2=[]
l2=[]
buf=[]
ans=0
for i in range(N):
    cuml[i+1]=cuml[i]+A[i+1]

for i in range(N+1):
    cuml2.append([(cuml[i]-i)%K,i])
    cuml[i]=(cuml[i]-i)%K

cuml2.sort(key=lambda x:x[0])
piv=cuml2[0][0]
buf=[]
for i in range(N+1):
    if piv!=cuml2[i][0]:
        l2.append(buf)
        piv=cuml2[i][0]
        buf=[]
    buf.append(cuml2[i][1])
l2.append(buf)

cnt=0
for i in range(len(l2)):
    for j in range(len(l2[i])):
        num=l2[i][j]
        id=bisect.bisect_left(l2[i], num + K)
        
        cnt=cnt+(id-j-1)
print(cnt)

Solution (Python):
from collections import Counter
n, k = map(int, input().split())
a = [x - 1 for x in map(int, input().split())]

sa = [0 for _ in range(n+1)]
for i in range(n):
    sa[i+1] = (sa[i] + a[i]) % k


if n < k:
    cnt = Counter(sa)
    ans = 0
    for x in cnt.values():
        ans += x * (x - 1) // 2
    print(ans)

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

Solution (Python):
from itertools import accumulate
from collections import Counter
N,K,*A = map(int, open(0).read().split())
A = [a-1 for a in A]
B = [0]+[b%K for b in accumulate(A)]
if K>N:
  Cnt = Counter(B)
  ans = sum(v*(v-1)//2 for v in Cnt.values())
else:
  Cnt = Counter(B[:K])
  ans = sum(v*(v-1)//2 for v in Cnt.values())
  for i in range(N+1-K):
    Cnt[B[i]] -= 1
    ans += Cnt[B[i+K]]
    Cnt[B[i+K]] += 1
print(ans)

Solution (Python):

from collections import Counter
import sys

buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def slv(N, K, A):
    B = [0]
    for i, a in enumerate(A, start=0):
        B.append((B[-1] + a) % K)

    for i in range(len(B)):
        B[i] = (B[i] - i) % K

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

    return ans


def main():
    N, K = read_int_n()
    A = read_int_n()
    print(slv(N, K, A))


if __name__ == '__main__':
    main()

Solution (Python):

import sys

buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret

from collections import Counter

def slv(N, K, A):
    B = [0]
    for i, a in enumerate(A, start=0):
        B.append((B[-1] + a) % K)

    for i in range(len(B)):
        B[i] = (B[i] - i) % K

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

    return ans



def main():
    N, K = read_int_n()
    A = read_int_n()
    print(slv(N, K, A))


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import accumulate
from collections import Counter
N,K,*A = map(int, open(0).read().split())
A = [a-1 for a in A]
B = [b%K for b in accumulate(A)]
if K>N:
  Cnt = Counter(B)
  ans = Cnt[0]+sum(v*(v-1)//2 for v in Cnt.values())
else:
  Cnt = Counter(B[:K])
  ans = Cnt[0]+sum(v*(v-1)//2 for v in Cnt.values())
  if B[K-1]==0:
    ans -= 1
  for i in range(N-K):
    Cnt[B[i]] -= 1
    ans += Cnt[B[i+K]]
    Cnt[B[i+K]] += 1
print(ans)

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

sa = dict()
ans = 0
l = 0
for i in range(n+1):
    saadd = (i-a2[i]) % k
    try:
        sa[saadd] += 1
    except:
        sa[saadd] = 1
    l += 1
    if l < k:
        continue
    nowidx = i-k+1
    now = (nowidx-a2[nowidx])% k
    try:
        ans += sa[now]-1
    except:
        pass
    sa[now] -= 1
    l -= 1




for val,cnt in sa.items():
    ans += cnt*(cnt-1)//2


print(ans)

Solution (Python):



from collections import defaultdict
from itertools import accumulate
from collections import deque

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]


d = defaultdict(int)
queue = deque()

ans = 0
for idx, s in enumerate(s):
    queue.append(s)
    if idx >= K:
        s_prev = queue.popleft()
        d[s_prev] -= 1

    ans += d[s]
    d[s] += 1
    

print(ans)