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



Sample input:
5 4
1 4 2 3 5


Sample output:
4

Submission status: Accepted

Solution code:
from collections import defaultdict
import numpy as np
n,k=map(int,input().split())
a=[0]+list(np.cumsum(list(map(int,input().split()))))

dic = defaultdict(int)
c = 0
for i in range(len(a)):
    p = (a[i] - i) % k
    c += dic[p]
    dic[p] += 1
    if i >= k - 1:
        dic[(a[i - k + 1] - (i - k + 1)) % k] -= 1
print(c)

Submission status: Accepted

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

sum_a = sum(a)%k

left = [0] * (n+1)
right = [0] * (n+1)
for i,num in enumerate(a,1):
    left[i] = (left[i-1] + num)%k
for i,num in enumerate(a[::-1],1):
    right[-i-1] = (right[-i] + num)%k

from collections import defaultdict
right_d = defaultdict(int)
right_d_over = defaultdict(int)
ans = 0
for i in range(n,-1,-1):
    ans += right_d[(sum_a - left[i])%k] - right_d_over[(sum_a - left[i])%k]
    right_d[right[i]] += 1
    if( (n-i+1) >= k ):
        right_d_over[right[i+k-1]] += 1

print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    
    cum = [0] * (n + 1)
    dic = {0:1}
    ans = 0
    for i in range(min(n,k - 1)):
        cum[i + 1] = (cum[i] + a[i])%k
        tmp = (cum[i + 1] - i - 1)%k
        if tmp in dic:
            dic[tmp] += 1
        else:
            dic[tmp] = 1

    for v in dic.values():
        ans += v * (v - 1)//2


    for i in range(max(n - k + 1,0)):
        dic[(cum[i] - i)%k] -= 1
        cum[i + k] = (cum[i + k - 1] + a[i + k - 1])%k
        tmp = (cum[i + k] - i - k)%k
        if tmp in dic:
            ans += dic[tmp]
            dic[tmp] += 1
        else:
            dic[tmp] = 1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    N, K  = [int(i) for i in input().split()]
    A  = [int(i) for i in input().split()]
    v = {0: 1}
    n = [0]
    r = 0
    t = 0
    for i, a in enumerate(A, 1):
        if i >= K:
            v[n[i - K]] -= 1
        t += a
        j = (t - i) % K
        r += v.get(j, 0)
        v[j] = v.get(j, 0) + 1
        n.append(j)

    return r


print(main())

Submission status: Accepted

Solution code:
def main():
    N, K = map(int,input().split())
    A = list(map(int, input().split()))
    s = 0
    d = {}
    d[0] = {0}
    r = 0
    l = [0] * (N + 1)
    for i, v in enumerate(A, start=1):
        if i - K >= 0:
           x = l[i - K]
           d[x].remove(i-K)
        s += v % K
        s %= K
        t = (s - i) % K
        l[i] = t
        if t in d:
            r += len(d[t])
            d[t].add(i)
        else:
            d[t] = {i}
    return r
print(main())

Submission status: Accepted

Solution code:
from collections import defaultdict
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
S = [0] * (N+1)
T = [0] * (N+1)
for i in range(N):
    S[i+1] = (S[i] + A[i])%K
    T[i+1] = (S[i+1] - (i+1))%K
rest = defaultdict(int)
for i in range(N+1):
    if i < K:
        ans += rest[T[i]]
        rest[T[i]] += 1
    else:
        rest[T[i-K]] -= 1
        ans += rest[T[i]]
        rest[T[i]] += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from collections import defaultdict

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = np.array([1] + lr())
A = (A-1) % K
N += 1
# 累積和が同じになっている箇所に注目、要素がK-1離れている組み合わせは無理
Acum = (A.cumsum() % K).tolist()
answer = 0
dic = defaultdict(int)
for i, cur in enumerate(Acum): 
    answer += dic[cur]
    dic[cur] += 1
    if i >= K-1:
        vanish = Acum[i-(K-1)]
        dic[vanish] -= 1

print(answer)
# 10

Submission status: Accepted

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

mod = [0]
for i in range(n):
    a = (l[i]-1)%k
    mod.append((mod[-1]+a)%k)
dic = defaultdict(int)
ans = 0
for i in range(n+1):
    if i < k:
        ans += dic[mod[i]]
        dic[mod[i]] += 1
    else:
        dic[mod[i-k]] -= 1
        ans += dic[mod[i]]
        dic[mod[i]] += 1
    
print(ans)

Submission status: Accepted

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

mod = [0]
for i in range(n):
    a = (l[i]-1)%k
    mod.append((mod[-1]+a)%k)
dic = {0:1}
ans = 0
for i in range(1,n+1):
    if i < k:
        if mod[i] in dic:
            ans += dic[mod[i]]
            dic[mod[i]] += 1
        else:
            dic[mod[i]] = 1
    else:
        dic[mod[i-k]] -= 1
        if mod[i] in dic:
            ans += dic[mod[i]]
            dic[mod[i]] += 1
        else:
            dic[mod[i]] = 1
    
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
l = list(map(int,input().split()))
mo = [0]
mod = [0]
for i in range(n):
    a = l[i]%k
    mo.append((a+mo[-1])%k)
    mod.append((mo[-1]-(i+1))%k)
dic = {0:1}
le = 1
ans = 0
for i in range(1,n+1):
    if le < k:
        if mod[i] in dic:
            ans += dic[mod[i]]
            dic[mod[i]] += 1
        else:
            dic[mod[i]] = 1
        le += 1
    else:
        dic[mod[i-k]] -= 1
        if mod[i] in dic:
            ans += dic[mod[i]]
            dic[mod[i]] += 1
        else:
            dic[mod[i]] = 1
    
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import defaultdict

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

acc = [0] + list(accumulate(a))
sm = [(e - i) % k for i, e in enumerate(acc)]

d = defaultdict(int)
ans = 0
for r in range(1, n + 1):
    if r - k >= 0:
        e = sm[r - k]
        d[e] -= 1

    e = sm[r - 1]
    d[e] += 1

    e = sm[r]
    ans += d[e]

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect

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

s = 0
S = [0]
for i, a in enumerate(A):
    s += a
    S.append(s % K)

cnt = 0
dic = {}

for i, s in enumerate(S):
    x = (s - i) % K

    if x in dic:
        cnt += dic[x]
        dic[x] += 1
    else:
        dic[x] = 1

    K_prev = i - K + 1

    if K_prev >= 0:
        y = (S[K_prev] - (K_prev)) % K
        dic[y] -= 1


print(cnt)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = [0]+list(map(int,input().split()))
for i in range(n):
    a[i+1] += a[i]
cnt = {}
ans = 0
for i in range(n+1):
    left = i-k
    if left >= 0:
        ldiff = (a[left] - left)%k
        cnt[ldiff]-=1
    diff = (a[i]-i)%k
    if diff not in cnt:cnt[diff] = 0
    ans += cnt[diff]
    cnt[diff] +=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate 
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
S=list(accumulate(A))
S.insert(0,0)

L=[ (s-i)%k  for i,s in enumerate(S)]
def f(l):
    return sum([x*(x-1)//2 for x in l])

from collections import Counter

ans=0
d = Counter(L[1:k])
for i in range(n):
    ans += d[L[i]]
    #print(L[i+1:i+k],d)
    d[L[i+1]] -= 1
    if i+k <= n:
        d[L[i+k]] += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict

n,k = map(int,input().split())
a = list(map(int,input().split()))
cum_sum = [0]*(n+1)#累積和 - i （要素すう）modk
for i in range(n):
  cum_sum[i+1] = (cum_sum[i]+a[i]-1) % k#cum_sum[i]-iが一定
D = defaultdict(int)

count = 0
for i in range(n+1):
  count += D[cum_sum[i]] #key が場所、val がcum_sumの値
  D[cum_sum[i]] += 1
  if i-k+1 >= 0:#区間の長さがあまりよりも小さいなら
    D[cum_sum[i-k+1]] -=1
print(count)

Submission status: Accepted

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

d = [0]
for i in a:
    a_i = (d[-1] + i) % k
    d.append(a_i)

ans = 0
counter = defaultdict(int)
for i, s in enumerate(d):
    ans += counter[(s-i) % k]
    counter[(s-i) % k] += 1
    if i - k + 1 >= 0:
        counter[(d[i - k + 1]-i+k-1) % k] -= 1

print(ans)

Submission status: Accepted

Solution code:
N, K = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
s = [0] * (N+1)

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

d = {}
ans = 0
for i in range(N+1):
    if s[i] not in d:
        d[s[i]] = 0
    if i >= K:
        d[s[i-K]] -= 1
    ans += d[s[i]]
    d[s[i]] += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

D = defaultdict(int)

count = 0

for i in range(N+1):
    count += D[S[i]]
    D[S[i]] += 1
    if i-K+1 >= 0:
        D[S[i-K+1]] -= 1

print(count)

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import deque
from collections import defaultdict

def func(x):
    return x - 1

def main():
    N, K = map(int, input().split())
    A = list(map(func, map(int, input().split())))
    B = [0] + list(accumulate(A))
    for i in range(N+1):
        B[i] %= K

    Q = deque()
    d = defaultdict(int)
    ans = 0
    for i in range(N+1):
        ans += d[B[i]]
        d[B[i]] += 1
        Q.append(B[i])
        if len(Q) == K:
            a = Q.popleft()
            d[a] -= 1

    print(ans)


    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import numpy as np
N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
A = np.array(A)
A %= K
A = A.cumsum()
tmp = np.arange(N + 1)

B = (A - tmp) % K

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

if N > K:
    for i in range(K, N + 1):
        x = B[i]
        y = B[i - K]
        d[y] -= 1
        ans += d[x]
        d[x] += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import *
import copy
N,K=map(int,input().split())
A=list(map(int,input().split()))

lst=[0]
for i in range(0,N):
    lst.append((A[i]%K+lst[i])%K)
for i in range(len(lst)):
    lst[i]-=i
    lst[i]%=K

dic={}
count=0
for i in range(0,len(lst)):
    if lst[i] in dic:
        count+=dic[lst[i]]
        dic[lst[i]]+=1
    else:
        dic.update({lst[i]:1})
    a=i-K+1
    if a>=0:
        dic[lst[a]]-=1
print(count)

Submission status: Accepted

Solution code:
def main():
    from itertools import accumulate
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    A=list(accumulate(A))
    A=[[(A[i]-i-1)%K,i+1] for i in range(0,N)]
    A.append([0,0])
    A.sort()
    s=1
    start=0
    count=0
    for i in range(0,N):
        if A[i][0]==A[i+1][0]:
            s+=1
        else:
            X=[A[i][1] for i in range(start,start+s)]
            a=0
            b=0
            subcount=0
            while len(X)-1>=a and len(X)-1>=b:
                if K-1>=X[b]-X[a]:
                    b+=1
                else:
                    subcount+=len(X)-b
                    a+=1
            count+=len(X)*(len(X)-1)//2-subcount
            start+=s
            s=1
    X=[A[i][1] for i in range(start,start+s)]
    a=0
    b=0
    subcount=0
    while len(X)-1>=a and len(X)-1>=b:
        if K-1>=X[b]-X[a]:
            b+=1
        else:
            subcount+=len(X)-b
            a+=1
    count+=len(X)*(len(X)-1)//2-subcount
    print(count)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
s = [0]*(N+1)
a = set()
for i in range(N):
    s[i+1] = s[i]+A[i]

s = [(s[i]-i) % K for i in range(N+1)]
for i in range(N+1):
    ans += table[s[i]]  # i番目まで取る組み合わせの数
    table[s[i]] += 1
    if i >= K-1:
        # Kで割ったあまりがKを超えることはないので、期限切れのものを引く
        table[s[i-K+1]] -= 1

print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=[0]*(N+1)
for i in range(N):
    B[i+1]=(B[i]+A[i]-1)%K
r=0
from collections import defaultdict
d=defaultdict(int)
for i in range(N+1):
    r+=d[B[i]]
    d[B[i]]+=1
    if K-1<=i:
        d[B[i-K+1]]-=1
print(r)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,K=MI()
    A=LI()
    for i in range(N):
        A[i]-=1
    *cumsum, = accumulate(A)
    for i in range(N):
        cumsum[i]%=K

    cnt = defaultdict(int)
    ans = 0
    for i,c in enumerate(cumsum):
        if i>=K:
            cnt[cumsum[i-K]]-=1
        if c==0 and i<K-1:
            ans += 1
        ans += cnt[c]
        cnt[c]+=1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import bisect
import heapq
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**15

def main():
    n, k = getlist()
    nums = getlist()
    acc = {0: [0]}
    tmp = 0
    for i, num in enumerate(nums):
        tmp += num
        tmp %= k
        tgt = ((tmp - i -1  + k) % k)
        if tgt not in acc:
            acc[tgt] = [i+1]
        else:
            acc[tgt].append(i+1)
        # acc.append(tmp-i-1)

    # cnt = Counter(acc)
    ans = 0
    for v in acc.values():
        for j, cur in enumerate(v):
            ins = bisect.bisect_left(v, cur+k)
            # print(ins, j)
            ans += ins - j - 1
        # ans += ((v-1) * v) // 2
    # print(acc)
    print(ans)

if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict
N, K = map(int, input().split())
A = [(int(c)%K)-1 for c in input().split()]
B = [0]
for c in A:
  B += [B[-1]+c]
dic = defaultdict(int)
ldic = defaultdict(int)
for i in range(min(K,N+1)):
  c = B[i]
  dic[c%K] += 1
ans = 0
#print(dic)
for i in range(1,N+1):
  x = B[i-1]
  ldic[x%K] += 1
  ans += dic[x%K]-ldic[x%K]
  if K+i-1<=N:
    dic[B[K+i-1]%K] += 1
  """
  print('###############')
  print(i,x, ans)
  print(dic)
  print(ldic)
  """
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N, K = map(int, input().split())
A = [(int(c)%K)-1 for c in input().split()]
B = [0]
for c in A:
  B += [B[-1]+c]
dic = defaultdict(int)
ldic = defaultdict(int)
for i in range(min(K,N+1)):
  c = B[i]
  dic[c%K] += 1
ans = 0
#print(dic)
for i in range(1,N+1):
  x = B[i-1]
  ldic[x%K] += 1
  ans += dic[x%K]-ldic[x%K]
  if K+i-1<=N:
    dic[B[K+i-1]%K] += 1
  """
  print('###############')
  print(i,x, ans)
  print(dic)
  print(ldic)
  """
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
l = list(map(int, input().split()))

l = [c-1 for c in l]
 
l = [0] + l
from itertools import accumulate
cum =list(accumulate(l))
cum = [c%k for c in cum]

from collections import deque
ans = 0
d = {}
q = deque()
for i in range(n+1):
  if cum[i] not in d:
    d[cum[i]] = 1
  else:
    ans += d[cum[i]]
    d[cum[i]] += 1
  q.append(cum[i])
  if len(q) == k:
    rem = q.popleft()
    d[rem] -= 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque

N, K=map(int, input().split())
A=list(map(int, input().split()))
for i in range(N):
    A[i]-=1
s=[0 for _ in range(N+1)]
for i in range(N):
    s[i+1]=(s[i]+A[i])%K
d=defaultdict(int)
ans=0
q=deque()
for j in range(N+1):
    ans+=d[s[j]]
    d[s[j]]+=1
    q.append(s[j])
    if len(q)==K:
        d[q[0]]-=1
        q.popleft()
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from collections import defaultdict

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = np.array([0] + lr())
A = (A-1) % K
Acum = A.cumsum() % K
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)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from collections import defaultdict

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = np.array([1] + lr())
A = (A-1) % K
Acum = A.cumsum() % K
counter = defaultdict(int)
answer = 0
for i in range(len(Acum)):
    x = Acum[i]
    answer += counter[x]
    counter[x] += 1
    if i >= K-1:
        counter[Acum[i-(K-1)]] -= 1

print(answer)
# 27

Submission status: Accepted

Solution code:
import sys
import numpy as np
from collections import defaultdict

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = np.array([1] + lr())
A = (A-1) % K
N += 1
Acum = A.cumsum() % K
d = defaultdict(int)
answer = 0
for i, x in enumerate(Acum):
    answer += d[x]
    d[x] += 1
    if i >= K-1:
        d[Acum[i-(K-1)]] -= 1

print(answer)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from collections import defaultdict

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = np.array([1] + lr())
A = (A-1) % K
N += 1
Acum = (A.cumsum() % K).tolist()
d = defaultdict(int)
answer = 0
for i, x in enumerate(Acum):
    answer += d[x]
    d[x] += 1
    if i >= K-1:
        d[Acum[i-(K-1)]] -= 1

print(answer)

Submission status: Accepted

Solution code:
#01:15
n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(n):
  a[i] -= 1
  a[i] %= k
b = [0]
for i in range(n):
  b.append((b[-1]+a[i]) % k)
ans = 0
now = {}
for i in range(n+1):
  tmp = b[i]
  if tmp in now:
    ans += now[tmp]
    now[tmp] += 1
  else:
    now[tmp] = 1
  if i - k + 1 >= 0:
    now[b[i-k+1]] -= 1
print(ans)

Submission status: Accepted

Solution code:
#解説解答
n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(n):
  a[i] -= 1
  a[i] %= k
#print(a)
b = [0]
for i in range(n):
  b.append((b[-1]+a[i])%k)
#print(b)

ans = 0
now = {}
for i in range(n+1):
  if b[i] in now:
    ans += now[b[i]]
    now[b[i]] += 1
  else:
    now[b[i]] = 1
  if i - k + 1 >= 0:
    now[b[i-k+1]] -= 1
  #print(now,i,ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    acca = [0]
    for _a in a:
        acca.append(acca[-1] + _a)
    
    ans = 0
    cnt = defaultdict(lambda : 0)
    for i, ac in enumerate(acca):
        ans += cnt[(ac - i) % k]
        cnt[(ac - i) % k] += 1
        if i >= k - 1:
            cnt[(acca[i - k + 1] - (i - k + 1)) % k] -= 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque


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

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

queue = deque()
mp = {}

ans = 0
for j in range(n+1):
    rem = s[j]
    queue.append(rem)
    if rem in mp:
        ans += mp[rem]
        mp[rem] += 1
    else:
        mp[rem] = 1
    
    if len(queue) == k:
        mp[queue.popleft()] -= 1

print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
a=list(map(int,input().split()))
A=[0]
for i in range(N):
    A.append((A[-1]+a[i]-1))
for i in range(len(A)):
    A[i]%=K
#print(A)

D={}
D[0]=1
ans=0

for i in range(1,N+1):
    if A[i] in D:
        ans+=D[A[i]]
        D[A[i]]+=1
    else:
        D[A[i]]=1
    if i-K+1>=0:
        D[A[i-K+1]]-=1
#print(D)
if K==1:
    print(0)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import itertools


# read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

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

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

cnt = defaultdict(int)
ans = 0
for i, a in enumerate(A):
    x = (a - i) % K
    #print("i", i, "a", a, "x", x, "cnt", cnt)

    ans += cnt[x]
    cnt[x] += 1

    if i >= K-1:
        y = (A[i-K+1] - (i-K+1)) % K
        cnt[y] -= 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

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

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [(int(a) % K) - 1 for a in input().split()]
    sum_A = [0 for _ in range(N + 1)]

    count = 0
    modK = dict()
    modK[0] = [0]
    for i in range(N):
        sum_A[i + 1] = (sum_A[i] + A[i]) % K
        if sum_A[i+1] not in modK: modK[sum_A[i+1]] = [i + 1]
        else: modK[sum_A[i+1]].append(i+1)
    
    for key in modK: 
        lenK = len(modK[key])
        for i, a in enumerate(modK[key]):
            count += bisect_left(modK[key], a + K, i, lenK) - i - 1

    print(count)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

import copy
B = copy.deepcopy(A)
for i in range(N):
    B[i] -= 1

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

from collections import defaultdict
D = defaultdict(list)
for i in range(N+1):
    D[C[i]].append(i)

ans = 0
#print(B)
#print(C)
#print(D)
for i in D:
    E = D[i]
    #print(ans)
    if len(E)>=2:
        left = 0
        right = 1
        count = 0
        flag = 0
        while left != len(E)-1 :
            if E[right]-E[left] < K:
                if right == len(E)-1:
                    if flag == 0:
                        count += 1
                        flag = 1
                    ans += count
                    left += 1
                    count -= 1
                else:
                    count += 1
                    right += 1
            else:
                ans += count
                count -= 1
                left += 1
print(ans)

Submission status: Accepted

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


from bisect import bisect_right as br
def main():
    dic = {}
    for i in range(1,N + 1):
        A[ i ] += A[ i - 1 ]
    for j in range(N + 1):
        if (A[j] - j)%K in dic:
            dic[(A[j] - j)%K].append(j)
        else:
            dic[(A[j] - j)%K] = [j]

    ans = 0
    
    for i in range(1,N + 1):
        tmp = dic[(A[i] - i)%K]
        left = br(tmp,i - K)
        right = br(tmp,i) - 1
        ans += right - left
    print(ans)
    return 

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def shaku(K,lists):
    ans=0
    SUMS=0
    index=0
    for  l  in range(len(lists)):
        while index < l or index< len(lists) and SUMS +lists[index] < K:
            SUMS += lists[index]
            index+= 1
        ans += index-l
        SUMS -= lists[l]

    return ans


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

uselist=[0 for i in range(n+1)]
for i in range(n):
    uselist[i+1]=(uselist[i]+lists[i])
anslist=[0 for i in range(n+1)]
for j in range(1,n+1):
    anslist[j]=(uselist[j]-j)%k
dic={}
for i in range(n+1):
    if anslist[i] in  dic.keys():
        dic[anslist[i]].append(i+1)
    else:
        dic[anslist[i]]=[1+i]
#answerに答えを格納することにする
answer=0
for lis in dic.values(): 
    sublis=[lis[0]]
    for a in range(1,len(lis)):
        sublis.append(lis[a]-lis[a-1])
    P=shaku(k,sublis)

    for some in lis:
      if some<k:
        answer-=1
    answer+=P
print(answer)

Submission status: Accepted

Solution code:
from collections import Counter

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

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

ans = 0
cnt = Counter()
for i in range(N+1):
    ans += cnt[Ss[i]]
    cnt[Ss[i]] += 1
    if i >= K-1:
        cnt[Ss[i-K+1]] -= 1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import accumulate
n,k=map(int, input().split()) 
A=list(map(int, input().split()))
S=[0]+list(accumulate(A))
R=[(S[i]-i)%k for i in range(n+1)]

r_dict={}
ans=0
for i in range(n+1):
    if R[i] in r_dict:
        ans+=r_dict[R[i]]
        r_dict[R[i]]+=1
    else:
        r_dict[R[i]]=1
    if i-k+1>=0:
        r_dict[R[i-k+1]]-=1
    
print(ans)

Submission status: Accepted

Solution code:
def bfs(n,e,fordfs,D):
    #点の数、スタートの点、有向グラフ
    W = [-1]*(n-1)
    #各点の状態量、最短距離とか,見たかどうかとか
    used = defaultdict(bool)
    que = deque()
    que.append(e)
    while que:
        now = que.popleft()
        i = 1
        for ne in fordfs[now]:
            l = min(now,ne); r = max(now,ne)
            if W[D[(l,r)]] == -1:
                while(True):
                    if not used[(now,i)]:
                        used[(now, i)] = True
                        used[(ne, i)] = True
                        break
                    i +=1
                que.append(ne)
                W[D[(l,r)]] = i
    return W
def examD():
    N = I()
    V = [[]for _ in range(N)]
    d = defaultdict(int)
    for i in range(N-1):
        a, b = LI()
        V[a-1].append(b-1)
        V[b-1].append(a-1)
        d[(a-1,b-1)] = i
    ans = bfs(N,0,V,d)
    print(max(ans))
    for v in ans:
        print(v)
    return

def examE():
    N, K = LI()
    A = LI()
    d = defaultdict(list)
    cumA = 0
    d[cumA].append(0)
    for i in range(N):
        cumA +=A[i]-1
        cumA %=K
        d[cumA].append(i+1)
#    print(d)
    ans = 0
    for l in d.values():
        for i in range(len(l)):
            left = i; r = len(l)
            while(r-left>1):
                now = (left+r)//2
                if l[now]-l[i]>=K:
                    r = now
                else:
                    left = now
            ans += left-i
    print(ans)
    return

def examF():
    N, M = LI()
    S = SI()
    ans = []
    cur = N
    while(cur>0):
        k = min(M,cur)
        while(S[cur-k]=="1"):
            k -=1
            if k==0:
                print("-1")
                return
        ans.append(k)
        cur -=k
    for v in ans[::-1]:
        print(v)
    return


import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()