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

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
for i in range(1,N):
  A[i]+=A[i-1]
A=[(A[i]-i-1)%K for i in range(N)]
A=[0]+A
from collections import Counter
if K>N:
  a=Counter(A)
  ans=0
  for v in a.values():
    ans+=v*(v-1)/2
  print(int(ans))
else:
  ans=0
  d={}
  for i in range(K):
    if A[i] in d:
      ans+=d[A[i]]
      d[A[i]]+=1
    else:
      d[A[i]]=1
  for i in range(K,N+1):
    d[A[i-K]]-=1
    if A[i] in d:
      ans+=d[A[i]]
      d[A[i]]+=1
    if A[i] not in d or d[A[i]]==0:
      d[A[i]]=1
  print(ans)

Solution (Python):

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


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

    if K == 1:
        print(0)
        return

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

    dp = [d % K for d in dp]

    ans = 0
    d = defaultdict(int)
    d[0] = 1
    for i in range(1, N + 1):
        ans += d[dp[i]]
        d[dp[i]] += 1

        if i - K + 1 >= 0:
            d[dp[i - K + 1]] -= 1

    print(ans)


def main():
    solve()


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

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

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

    indices = defaultdict(list)
    for i in range(N + 1):
        indices[csum[i]].append(i)

    ans = 0
    for vec in indices.values():
        right = 0
        for left in range(len(vec)):
            while right + 1 < len(vec) and vec[right + 1] - vec[left] < K:
                right += 1

            ans += right - left
            if left == right:
                right += 1

    print(ans)

    return


if __name__ == '__main__':
    main()

Solution (Python):
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
n,k = ma()
A = lma()
s = [0]*(n+1)
l = [0]*(n+1)
for i in range(n):
    s[i+1]=(s[i]+A[i])%k
    l[i+1]=(s[i+1]-(i+1))%k
ans = 0
co = collections.Counter(l[:min(n+1,k)])
for num,cnt in co.items():
    ans+=cnt*(cnt-1)//2
for i in range(k,n+1):
    co[l[i-k]]-=1
    ans+=co[l[i]]
    co[l[i]]+=1



print(ans)

Solution (Python):
import bisect
N,K=map(int,input().split())
A=list(map(int,input().split()))
S=[0 for i in range(N+1)]
for i in range(N):
    S[i+1]=S[i]+A[i]
    S[i+1]%=K
X=[(S[i]-i)%K for i in range(N+1)]
D=dict()
for i in range(N+1):
    if X[i] in D:
        D[X[i]].append(i)
    else:
        D[X[i]]=[i]
ans=0
for k in D:
    for i in D[k]:
        L=bisect.bisect_left(D[k],i-K+1)
        R=bisect.bisect_right(D[k],i+K-1)
        ans+=R-L-1
print(ans//2)

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

mp = defaultdict(int)

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

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))


"""
N^2なので素直に計算は無理，部分和を使いたいのでとりあえず累積和
[i+1:j]が条件を満たすとはS[j]-S[i]とj-iが合同．
移行して，S[j]-jとS[i]-iが合同
基本は個数だけ見れば良い

これだけだと，個数がKより大きい時にダメ
直近Kこの情報だけ持つ，今見てる数字が直近K個のものと何個組にできるか
"""
def main():

    mod=10**9+7
    N,K=MI()
    A=LI()
    from collections import defaultdict
    dd = defaultdict(int)
    
    S=[0]*(N+1)
    for i in range(N):
        S[i+1]=(S[i]+A[i])%K
        
    ans=0
    for i in range(min(K,N+1)):
        temp=(S[i]-i)%K
        ans+=dd[temp]
        dd[temp]+=1
        
    for i in range(K,N+1):
        temp=(S[i]-i)%K
        temp_m=(S[(i-K)]-(i-K))%K
        dd[temp_m]-=1
        ans+=dd[temp]
        dd[temp]+=1
        
    print(ans)
        
        
    

        

main()

Solution (Python):
















n,k = map(int,input().split())
A = list(map(int,input().split()))
S = [0]
for a in A:
    S.append(S[-1] + a)

from collections import defaultdict
dic = defaultdict(int)
ans = 0

for i,s in enumerate(S):
    if i >=k:
        dic[(S[i-k] - (i-k))%k]-=1
    ans += dic[(S[i]- i)%k]
    
    dic[(S[i]- i)%k] += 1
print(ans)

Solution (Python):
from collections import defaultdict

N, K = map(int, input().split())
A = list(map(lambda x: int(x) - 1, input().split()))
A_accsum = [0] * (N+1)
for i, a in enumerate(A):
    A_accsum[i+1] = (A_accsum[i]+a) % K

count = defaultdict(lambda: 0)
piv = A_accsum[0]
count[piv] += 1
ans = 0
for i in range(1, min(K, N+1)):
    a = A_accsum[i]
    count[a] += 1
for i in range(K, N + 1):
    a = A_accsum[i]
    piv = A_accsum[i-K]
    count[piv] -= 1
    ans += count[piv]
    count[a] += 1
for i in range(max(0, N - K+1), N+1):
    piv = A_accsum[i]
    count[piv] -= 1
    ans += count[piv]
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations,product

from heapq import heapify,heappop,heappush

from functools import reduce,lru_cache

from decimal import Decimal
from argparse import ArgumentParser

args=ArgumentParser()
args.add_argument('-loc', '--local', type=bool,default=False)
LOCAL=args.parse_args().local

def input(): 
    x=sys.stdin.readline(); 
    if x[-1]=="\n": 
        return x.rstrip() 
    return x
    
def printe(*x):_=print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): 
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    

    
    N, K = map(int, input().split())
    A = tuple(map(int, input().split())) 
    
    
    acc=[0]*(N+1)
    cur=0
    if K==1:
        print(0)
        return 

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

    j=1
    d=Counter()
    d[0]=1
    ans=0
    for i in range(N):
        d[acc[i]]-=1
        while j-i<K and j<N+1:
            d[acc[j]]+=1
            j+=1
        ans+=d[acc[i]]

    print(ans)
        
        



if __name__ == "__main__":
    main()

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

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
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 main():
    N, K = LI()
    A = LI()
    cumsum = [0] * (N+1)
    c = collections.defaultdict(list)
    memo = [0] * (N+1)
    c[0].append(0)
    for i in range(N):
        
        cumsum[i+1] = (cumsum[i] % K + A[i]) % K
        val = (cumsum[i+1] - (i+1)) % K
        memo[i+1] = val
        c[val].append(i+1)
    
    
    
    ans = 0
    for i in range(N+1):
        val = memo[i]
        l_ix = bisect.bisect_right(c[val], i)
        r_ix = bisect.bisect_right(c[val], i + (K-1))
        
        ans += r_ix - l_ix
    
    
    
    print(ans)
main()

Solution (Python):
N,K=map(int,input().split())
L=list(map(int,input().split()))
R=list()
if K>=N:
  sums=0
  c=dict()
  for i in range(N):
    sums+=L[i]
    sums%=K
    a=(sums-i-1)%K
    if a in c:
      c[a]+=1
    else:
      c[a]=1
  ans=0
  for i in c:
    ans+=(c[i]-1)*c[i]//2
  if 0 in c:
    print(ans+c[0])
  else:
    print(ans)
else:
  ans=0
  c=[0]*K
  sums=0
  for i in range(N):
    sums+=L[i]
    sums%=K
    a=(sums-i-1)%K
    R.append(a)
  for i in range(K-1):
    c[R[i]]+=1
  ans+=c[0]
  c[R[K-1]]+=1
  for i in range(N):
    if i<N-K:
      ans+=c[R[i]]-1
      c[R[i]]-=1
      c[R[i+K]]+=1
    else:
      ans+=c[R[i]]-1
      c[R[i]]-=1
  print(ans)

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



import sys
import itertools

import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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

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

mp = defaultdict(int)
ans = 0
for j in range(N + 1):
    if j >= K:
        mp[acc[j - K]] -= 1
    ans += mp[acc[j]]
    mp[acc[j]] += 1
print(ans)

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



import sys
import itertools

import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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

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

mp = defaultdict(int)
ans = 0
for j in range(N + 1):
    if j >= K:
        mp[acc[j - K]] -= 1
    ans += mp[acc[j]]
    mp[acc[j]] += 1
print(ans)

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



import sys
import itertools

import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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

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

mp = defaultdict(int)
ans = 0
q = deque([])
for j in range(N + 1):
    ans += mp[acc[j]]
    mp[acc[j]] += 1
    q.append(acc[j])
    if len(q) == K:
        mp[q[0]] -= 1
        q.popleft()
print(ans)

Solution (Python):
n,k = map(int,input().split())
A = list(map(int,input().split()))
c = 0
from collections import Counter
d = Counter()
d[0] = 1
ans = 0
r = [0]*(n+1)
for i,x in enumerate(A):
    if i>=k-1:
        d[r[i-(k-1)]]-=1
    c = (c+x-1)%k
    ans += d[c]
    d[c] += 1
    r[i+1] = c
print(ans)

Solution (Python):

from itertools import accumulate
from collections import defaultdict, deque
def resolve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A = accumulate([a % K for a in A])
    A = [0] + list(A)

    
    
    
    
    

    cnt = defaultdict(int)
    q = deque()
    ans = 0
    for r in range(N + 1):
        t = (A[r] - r) % K
        ans += cnt[t]
        cnt[t] += 1

        q.append(t)
        if len(q) == K:
            left = q.popleft()
            cnt[left] -= 1

    print(ans)


if __name__ == "__main__":
    resolve()

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N,MOD = IL()
A = IL()

if MOD == 0:
  print(0)
  exit()

def ACC1(l):
  N = len(l)
  ret = [0]*(N+1)
  for i in range(N):
    ret[i+1] = ret[i]+l[i]
  return ret

ACC = ACC1(A)

dic = DD(list)
for i in range(N+1):
  dic[(ACC[i]-i)%MOD].append(i)
ans = 0
for k in dic:
  l = len(dic[k])
  for i in range(l):
    p = bisect.bisect(dic[k],dic[k][i]+MOD-1)
    ans += p-i-1

print(ans)

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

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

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

    c = 0
    d = collections.Counter()
    d[0] = 1
    ans = 0
    r = [0] * (N+1)
    for i,x in enumerate(A):
        if i >= K-1:
            d[r[i-(K-1)]] -= 1
        c = (c + x - 1) % K
        ans += d[c]
        d[c] += 1
        r[i+1] = c

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007
INF = float("inf")

def main():
    N, K = LI()
    A = LI()
    S = list(itertools.accumulate(A))
    keep = defaultdict(int)
    keep[0] += 1
    ans = 0

    for i in range(1, N+1):
        v = (S[i-1] - i) % K
        if i == K:
            keep[0] -= 1
        if i - K > 0:
            w = (S[i-K-1] - (i - K)) % K
            keep[w] -= 1
        ans += keep[v]
        keep[v] += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
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]
    s[i] = (s[i] - i) % k
s[n] = (s[n] - n) % k

count = dict()
for i in range(min(k-1, n+1)):
    if not s[i] in count:
        count[s[i]] = 0
    count[s[i]] += 1

ans = 0
for i in range(k-1, n+1):
    if not s[i] in count:
        count[s[i]] = 0
    count[s[i]] += 1
    count[s[i-k+1]] -= 1
    ans += count[s[i-k+1]]

for i in count.values():
    ans += i * (i - 1) // 2

print(ans)

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

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

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

ans = 0
dic = {}
for i, b in enumerate(B):
    if b in dic:
        dic[b].append(i)
    else:
        dic[b] = deque()
        dic[b].append(i)
    
    while len(dic[b]) > 0 and dic[b][0] <= i - K:
        dic[b].popleft()
    ans += len(dic[b])-1
    

print(ans)

Solution (Python):
import math
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

class Accumulation:
    def __init__(self,X,accumfunc,init_val=0):
        self.X = X
        self.accumfunc = accumfunc

        N = len(X)
        v1 = [0] * (N+1)
        v1[0] = init_val

        for i in range(N):
            v1[i+1] = accumfunc(v1[i],X[i])

        self.v1 = v1
    
    
    def query(self,l,r):
        return self.v1[r+1] - self.v1[l]
    
    def get_array(self):
        return self.v1

class Counter:
    def __init__(self):
        self.dict = {}

    def add(self,x):
        if x in self.dict: self.dict[x] += 1
        else: self.dict[x] = 1

    def decrement(self,x):
        self.dict[x] -= 1

    def get_dict(self):
        return self.dict



INF=10**20
def main():
    N,K=mi()
    A=list(mi())

    def madd(x,y): return (x+y) % K
    V = Accumulation(A,madd)

    v = V.get_array()
    u = [-1] * (N+1)

    for i in range(N+1):  
        u[i] = v[i] - i
        u[i] %= K  
    
    
    if K <= N:
        s = u[:K]
        counter = Counter()
        for i in range(K):
            _s = s[i]
            counter.add(_s)

        ans = 0
        current_count = counter.get_dict()
        ans += (current_count[u[0]] - 1)
    
        for i in range(1,N+1):
            

            old = u[i-1]
            counter.decrement(old)

            if i+K-1 < len(u):
                new = u[i+K-1] 
                counter.add(new)

            current_count = counter.get_dict()
            ans += (current_count[u[i]] - 1)
            
        
        print(ans)


    else:
        counter = Counter()
        for i in range(N+1):
            counter.add(u[i])
        
        u = counter.get_dict()
        ans = 0
        for c in u.values():
            if c <= 0: continue
            ans += c*(c-1)//2
        
        print(ans)
            
    


if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict
n, k = map(int, input().split())
a = list(map(int, input().split()))
d = defaultdict(int)
sa = [0] * (n + 1)




for i in range(n):
    sa[i + 1] = sa[i] + a[i]
    sa[i + 1] %= k
ans = 0
for i in range(n + 1):
    v = sa[i] - i
    v %= k
    ans += d[v]
    d[v] += 1
    if 0 <= i - k + 1:
        vv = sa[i - k + 1] - (i - k + 1)
        vv %= k
        d[vv] -= 1
print(ans)

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

Solution (Python):
from collections import defaultdict
from bisect import bisect_right

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

dd = defaultdict(list)
dd[0].append(0)
total = 0
for i, num in enumerate(alst, start = 1):
    total += num
    total %= k
    app = total - i
    app %= k
    dd[app].append(i)
ans = 0
for _, lst in dd.items():
    for i, num in enumerate(lst):
        num2 = num + k - 1
        pos = bisect_right(lst, num2)
        ans += pos - i - 1
print(ans)

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect

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

s = list(itertools.accumulate(a))


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



d = defaultdict(int)

count = 0
for j in range(1,N+1):
    d[s[j-1]] += 1
    if j-K >= 0:
        d[s[j-K]] -= 1
    
    count += d[s[j]]


print(count)

Solution (Python):
'''
研究室PCでの解答
'''
import math

import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline

mod = 10**9+7
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n,k = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]

    memo = deque()
    memo.append(0)
    d = defaultdict(int)
    ans = 0
    nv = 0
    d[0] += 1
    for i,ai in enumerate(a):
        nv += ai-1
        nv %= k
        memo.append(nv)
        if i >= k-1:
            pi = memo.popleft()
            d[pi] -= 1
        ans += d[nv]
        d[nv] += 1

    print(ans)

    return None

if __name__ == '__main__':
    main()

Solution (Python):
'''
研究室PCでの解答
'''
import math

import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n,k = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]

    memo = deque()
    memo.append(0)
    d = defaultdict(int)
    ans = 0
    nv = 0
    d[0] += 1
    for i,ai in enumerate(a):
        nv += ai-1
        nv %= k
        memo.append(nv)
        if i >= k-1:
            pi = memo.popleft()
            d[pi] -= 1
        ans += d[nv]
        d[nv] += 1

    print(ans)

    return None

if __name__ == '__main__':
    main()

Solution (Python):
import sys

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

values = dict()
valuelist = [0]*(n+1)
values[0] = 1
s = 0
ans = 0
if k == 1:
  print(0)
  sys.exit()

for i in range(n):
  s += a[i]-1
  s %= k
  if s in values:
    ans += values[s]
    values[s] += 1
  else:
    values[s] = 1
  
  valuelist[i+1] = s
  if i >= k-2:
    values[valuelist[i-k+2]] -= 1

print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






N, K = getNM()
A = getList()
A = [(i % K) - 1 for i in A]

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

num = defaultdict(list)
for i in range(N + 1):
    num[A[i]].append(i)

cnt = 0
for key, opt in num.items():
    for i in range(len(opt)):
        index = bisect_right(opt, opt[i] + K - 1)
        cnt += index - i - 1
print(cnt)

Solution (Python):

from collections import defaultdict

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

cs = [0] * (N + 1)
for i in range(N):
    cs[i + 1] = cs[i] + X[i]

y = [(cs[i] - i) % K for i in range(N + 1)]
ctr = defaultdict(int)
ans = 0
for i in range(N + 1):
    ans += ctr[y[i]]
    ctr[y[i]] += 1
    if i - K + 1 >= 0:
        ctr[y[i - K + 1]] -= 1

print(ans)

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

Solution (Python):
import sys
input = sys.stdin.readline
from itertools import accumulate
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 = dict()
cnt[C[0]] = 1
res = 0
for i in range(1, N+1):
    if i >= K:
        cnt[C[i-K]] = cnt.get(C[i-K],0) - 1
    res += cnt.get(C[i], 0)
    cnt[C[i]] = cnt.get(C[i],0) + 1
print(res)

Solution (Python):
from itertools import accumulate
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 = dict()
cnt[C[0]] = 1
res = 0
for i in range(1, N+1):
    if i >= K:
        cnt[C[i-K]] = cnt.get(C[i-K],0) - 1
    res += cnt.get(C[i], 0)
    cnt[C[i]] = cnt.get(C[i],0) + 1
print(res)