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:
import sys
import math
import heapq
import bisect
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

# j - i == S[j] - S[i] # MOD K
# S[i] - i == S[j] - j

N,K=LI()
As=LI()

Cum=[0]*(N+1)
for i in range(N):
    Cum[i+1] = Cum[i] + As[i]

REM2IDX = {}
for i in range(0,N+1):
    rem = (Cum[i] - i) % K
    if not rem in REM2IDX: REM2IDX[rem] = []
    REM2IDX[rem].append(i)

res = 0
for i in range(0,N+1):
    rem = (Cum[i] - i) % K
    cnt = len(REM2IDX[rem])
    l = bisect.bisect_right(REM2IDX[rem], i)
    r = bisect.bisect_right(REM2IDX[rem], i+K-1)
    res += (r-l)

print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict

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]

f = lambda n: (S[n] - n) % k
C = defaultdict(int)
ans = 0
for i in range(n):
    C[f(i)] += 1
    j = i - k + 1
    if 0 <= j:
        C[f(j)] -= 1
    ans += C[f(i+1)]
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
from collections import Counter
INF = float("inf")


def solve(N: int, K: int, A: "List[int]"):

    ans = 0

    # 累積和
    acc = [0]+list(accumulate(A))

    cnt = Counter()
    # 各jについて
    for j in range(1, N+1):
        # 区間に加える
        if j-1 >= 0:
            cnt[(acc[j-1]-(j-1)) % K] += 1

        # 区間から除く
        if j-K >= 0:
            cnt[(acc[j-K]-(j-K)) % K] -= 1

        # カウントする
        ans += cnt[(acc[j]-j) % K]
    print(ans)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,K=map(int,input().split())
A = list(map(int,input().split()))
for i in range(n):
    A[i]-=1
B=[0]+A[:]
for i in range(n):
    B[i+1]=(B[i+1]+B[i])%K
C=collections.Counter(B[:K])
for ci in C.values():
    ans+=ci*(ci-1)//2
for i in range(K,n+1):
    # print(ans)
    C[B[i-K]]-=1
    ans+=C[B[i]]
    C[B[i]]+=1
# print(B)
# print(C)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import accumulate


def solve():
    N, K, *A = map(int, open(0).read().split())
    
    Acumsum = [0] + list(accumulate(A))
    si = [(Acumsum[i] - i) % K for i in range(N + 1)]
    counter = defaultdict(int)
    
    ans = 0
    for j in range(N):
        counter[si[j]] += 1
        if 0 <= j - K + 1:
            counter[si[j - K + 1]] -= 1
        ans += counter[si[j + 1]]
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
from collections import defaultdict
input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))
a = [i-1 for i in a]
suma = [0]+list(accumulate(a))
suma = [i%k for i in suma]
rem = defaultdict(int)
ans = 0
if k > n:
    for i in range(n+1):
        x = suma[i]
        rem[x] += 1
    for s in rem.values():
        ans += s*(s-1)//2
    print(ans)
    exit()
for i in range(k):
    x = suma[i]
    rem[x] += 1
for s in rem.values():
    ans += s*(s-1)//2
for i in range(n-k+1):
    rem[suma[i]%k] -= 1
    rem[suma[i+k]%k] += 1
    ans += rem[suma[i+k]] -1
print(ans)

Submission status: Accepted

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





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



        


if __name__ == '__main__':
    main()
1

Submission status: Accepted

Solution code:
from itertools import *
from collections import defaultdict
def ints():
  return [int(x) for x in input().split()]
def readi():
  return int(input())

N, K = ints()
A = ints()
S = [0] + list(accumulate(A))

def f(i):
  return (S[i]-i)%K

s = 0
memo = defaultdict(int)
for j in range(1, N+1):
  fj = f(j)

  if j-K>=0:
    memo[f(j-K)] -= 1
  memo[f(j-1)] += 1

  s += memo[fj]
print(s)

Submission status: Accepted

Solution code:
from collections import defaultdict
n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(n):
    a[i] -= 1
    a[i] %= k

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

ans = 0
dic = defaultdict(int)
dic[0] = 1
for i in range(1,n+1):
    if i >= k:
        dic[S[i-k]] -= 1
    ans += max(0,dic[S[i]])
    dic[(S[i])] += 1

print(ans)

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

S = [0]*(N+1)
for i in range(N):
    S[i+1] = (S[i] + A[i]) % K
    
for i in range(N+1):
    S[i] = (S[i] - i) % K
    
dic = {}
for i in range(min(K, N+1)):
    if S[i] in dic:
        dic[S[i]] += 1
    else:
        dic[S[i]] = 1
        

ans = 0
for key in dic:
    ans += dic[key]*(dic[key]-1)//2
    
if K < N+1:
    for i in range(K, N+1):
        dic[S[i-K]] -= 1
        if S[i] in dic:
            ans += dic[S[i]]
            dic[S[i]] += 1
        else:
            dic[S[i]] = 1
            
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
a = inl()
h =defaultdict(int)
b = [0]*(n+1)
s = [0]*(n+1)
for i in range(n):
    s[i+1] = s[i]+a[i]
    b[i+1] = (s[i+1]-i-1)%k
ddprint(s)
ddprint(b)
acc = 0
for i in range(n+1):
    if i>=k:
        h[b[i-k]] -= 1
    acc += h[b[i]]
    h[b[i]] += 1
    #ddprint("i {} acc {} h {}".format(i,acc,h))
print(acc)

Submission status: Accepted

Solution code:
def main():
   n,k = map(int,input().split())
   a = list(map(int,input().split()))


   if k == 1:
      res = 0
      print(res)
   elif k == 2:
      res = 0
      for e in a:
         if e%k == 1:
            res += 1
      print(res)
   else:
      for i in range(n):
         a[i] = (a[i]-1)%k
      b = [0]
      d = {}
      d[0] = 1

      res = 0
      p = 0

      for i,e in enumerate(a):
         p = (p+e)%k
         if p in d:
            res += d[p]
            d[p] += 1
         else:
            d[p] = 1
         b.append(p)
         if i >= k-2:
            d[b[i-(k-2)]] -= 1
      print(res)

if __name__ == '__main__':
      main()

Submission status: Accepted

Solution code:
from collections import Counter


N, K = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * (N + 1)

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

C = Counter()
ans = 0
for j in range(1, N + 1):
    C[S[j - 1]] += 1
    if (j - K) >= 0:
        C[S[j - K]] -= 1

    ans += C[S[j]]


print(ans)

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
A = list(map(int, input().split()))
S = [0]*(N+1)
S2 = [0]*(N+1)
dict = {}#最新K件の度数分布の管理

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

ans =0
for i in range(N+1):
    if dict.get(S2[i],0):
        ans += dict[S2[i]]
    dict[S2[i]]=dict.get(S2[i],0)+1
    if i >=K-1:
        dict[S2[i-(K-1)]]-=1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
write = sys.stdout.write
# template


def solve():
    n,k=map(int, readline().split())
    a = list(map(int, readline().split()))
    b=[0]*(n+1)

    for i in range(n):
        b[i+1]=b[i]+a[i]-1
        b[i+1]%=k
    count=0
    from collections import defaultdict
    dp=defaultdict(list)
    for i in range(n+1):
        dp[b[i]].append(i)
    #print(dp,b)
    for item in dp:
        #print(count)
        if len(dp[item])<2:
            continue
        l=0
        r=1
        li=dp[item]
        while(l<len(li)):
            if l==r:
                r+=1
                continue
            if r<len(li) and li[r]-li[l]<k:
                r+=1
            else:
                count+=r-l-1
                l+=1
    print(count)

        
'''
    for i in range(k):
        if dp[i]<2:
            continue
        count+=dp[i]*(dp[i]-1)//2
'''
    


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N, K = [int(n) for n in input().split()]

A = [int(n) for n in input().split()]

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

check = {0: [0,1,[0]]}

s = 0
for i in range(1,N+1):
    s = (s + A[i-1]) % K
    if s in check:
        j = check[s][0]
        l = check[s][1]
        while j < l and i - check[s][2][j] >= K:
            j += 1
        check[s][0] = j
        count += l - j
        check[s][2].append(i)
        check[s][1] = l + 1
    else:
        check[s] = [0,1,[i]]

print(count)

Submission status: Accepted

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

ans = 0
accum = [0]
d = {0 : 1}

for i, a in enumerate(A):
  accum.append((accum[-1] + a - 1)%K)
  if i >= K - 1:
    d[accum[i-K+1]] -= 1
  
  if accum[-1] in d:
    ans += d[accum[-1]]
    d[accum[-1]] += 1
  
  else:
    d[accum[-1]] = 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N,K = II()
A = [0] + III()

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

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

print(ans)

Submission status: Accepted

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

# (sums[j] - sums[i]) % K = j - i
# (sums[j] - j) % K  = (sums[i] - i) % K
# 1, 4, 2, 3, 5
# 0, 1, 5, 7, 10, 15
# 0, 0, 3, 0, 2, 2

sums = [0]
for x in nums:
  sums.append(sums[-1] + x)

a = [(sums[i] - i) % k for i in range(len(sums))]

res = 0
memo = {}
i = 0 
for j in range(len(a)):
  memo[a[j]] = memo.get(a[j], 0) + 1
  if j - i + 1 > k:
    memo[a[i]] -= 1
    i += 1
  res += memo[a[j]] - 1
print(res)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = []
d = {}
A = list(map(int,input().split()))
ans = 0
sum =0
for i in range(1,N+1):
    sum += A[i-1] % K
    s = (sum - i) % K
    if i > K:
        x = S.pop(0)
        d[x] -= 1
    elif i < K:
        if s == 0:
            ans += 1
    if s not in d:
        d[s] = 0
    ans += d[s]
    d[s] += 1
    S.append(s)
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import defaultdict
N,K = map(int, input().split())
Xs = list(accumulate([0] + [int(x) for x in input().split()]))
Xs = [(x-i)%K for i, x in enumerate(Xs)]
d,r=defaultdict(int),0
for i, x in enumerate(Xs):
    d[x]+=1
    if i >= K:
        d[Xs[i-K]] -= 1
    r += d[x]-1
print(r)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys, os
import collections

MOD = 10 ** 9 + 7

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

  


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

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


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

Submission status: Accepted

Solution code:
import bisect

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys

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

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

d=dict()    #要素：要素の数を持つ

ans=0
for i in range(N+1):
    x=S[i]%K
    if i==0:
        d[x]=1
    else:
        if x in d:
            if 2<=K:    #K=1の時は自分の値も見てはいけない
                ans+=d[x]   #自分より前に同じ出現した、自分と同じ要素の数を答えに追加
            d[x]+=1
        else:
            d[x]=1      
        if 0<=i-K+1:
            x_head=S[i-K+1]%K  #長さK-1の範囲で配列Sを見るため、１つ進んだら一番先頭の要素を辞書から削除する
            d[x_head]-=1

print ans

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

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

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

d=dict()    #要素：要素の数を持つ

ans=0
for i in range(N+1):
    x=S[i]%K
    if i==0:
        d[x]=1
    else:
        if x in d:
            if 2<=K:    #K=1の時は自分の値も見てはいけない
                ans+=d[x]   #自分より前に同じ出現した、自分と同じ要素の数を答えに追加
            d[x]+=1
        else:
            d[x]=1      
        if 0<=i-K+1:
            x_head=S[i-K+1]%K  #長さK-1の範囲で配列Sを見るため、１つ進んだら一番先頭の要素を辞書から削除する
            d[x_head]-=1

print ans

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

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

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

d=dict()    #要素：要素の数を持つ

ans=0
for i in range(N+1):
    x=S[i]%K
    if i==0:
        d[x]=1
    else:
        if x in d:
            if 2<=K:    #K=1の時は自分の値も見てはいけない
                ans+=d[x]   #自分より前に同じ出現した、自分と同じ要素の数を答えに追加
            d[x]+=1
        else:
            d[x]=1      
        if 0<=i-K+1:
            x_head=S[i-K+1]%K  #長さK-1の範囲で配列Sを見るため、１つ進んだら一番先頭の要素を辞書から削除する
            d[x_head]-=1

print ans

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

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

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

d=dict()    #要素：要素の数を持つ

ans=0
for i in range(N+1):
    x=S[i]%K
    if i==0:
        d[x]=1
    else:
        if x in d:
            ans+=d[x]   #自分より前に同じ出現した、自分と同じ要素の数を答えに追加
            d[x]+=1
        else:
            d[x]=1      
        if 0<=i-K+1:
            x_head=S[i-K+1]%K  #長さK-1の範囲で配列Sを見るため、１つ進んだら一番先頭の要素を辞書から削除する
            d[x_head]-=1

print ans

Submission status: Accepted

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

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

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] * (n + 1)
for i in range(1, n + 1):
    S[i] = S[i - 1] + A[i - 1]

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

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


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

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque, Counter, defaultdict
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
import bisect
from logging import getLogger, StreamHandler, DEBUG, WARNING
logger = getLogger(__name__)
handler = StreamHandler()
handler.setLevel(DEBUG)
logger.setLevel(DEBUG)
# handler.setLevel(WARNING)
# logger.setLevel(WARNING)
logger.addHandler(handler)
def main():
    n, k = getList()
    nums = getList()
    acc = [0]
    tmp = 0
    for num in nums:
        tmp += num - 1
        tmp %= k
        acc.append(tmp)
    ans = 0
    df = {}
    for i in range(n + 1):
        if not acc[i] in df:
            df[acc[i]] = 1
        else:
            df[acc[i]] += 1
        ans += (df[acc[i]] - 1)
        if i >= k-1:
            df[acc[i-k+1]] -= 1



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

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
import collections


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


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
N, K = map(int, input().split())
A = list(map(int, input().split()))
S = [0]*(N+1)
# 累積和
for i in range(1, N + 1):
    S[i] = S[i - 1] + A[i - 1] - 1
    S[i] %= K
        
B = dd(int)  # ここで範囲内のS[i]-iの個数を数えていく。
cnt = 0
for j in range(1, N + 1):
    B[S[j - 1]] += 1
    if j - K >= 0:
        B[S[j - K]] -= 1
    cnt += B[S[j]]

print(cnt)

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

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

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

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

print(ret)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
from collections import defaultdict
input = sys.stdin.readline
N,K=map(int,input().split());A=list(map(int,input().split()))
S_=list(map(lambda t: (t[1]-t[0])%K,enumerate(accumulate([0]+A))))
count=0
C=defaultdict(int)
for t in range(1,N+1):
  C[S_[t-1]]+=1
  if t-K>=0:
    C[S_[t-K]]-=1
  count+=C[S_[t]]
print(count)

Submission status: Accepted

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

def solve(N, K, A):
    if K == 1:
        return 0
    
    S = [0 for _ in range(N+1)]
    for i in range(N):
        S[i+1] = S[i] + A[i]
    
    count_sum = 0
    count = dict()
    for j in range(1, N+1):
        j_mod_k = (S[j] - j) % K  # 0 <= jmodk < K
        if j == 1:
            for i in range(max(0, j-K+1), j):
                # (S[i] - i) % K の値 i_mod_k は、次のループでもほぼ重複する
                # i = max(0, j-K+1) の時の i_mod_k は、i+1で破棄する
                # i = j の時の i_mod_k は、i+1で生成する
                i_mod_k = (S[i] - i) % K
                if i_mod_k in count:
                    count[i_mod_k] += 1
                else:
                    count[i_mod_k] = 1
        else:
            if max(0, j-K+1) != max(0, (j-1)-K+1):
                i = max(0, (j-1)-K+1)
                i_mod_k = (S[i] - i) % K
                if i_mod_k in count:
                    if count[i_mod_k] == 1:
                        count.pop(i_mod_k)
                    else:
                        count[i_mod_k] -= 1
            i = j-1
            i_mod_k = (S[i] - i) % K
            if i_mod_k in count:
                count[i_mod_k] += 1
            else:
                count[i_mod_k] = 1
        if j_mod_k in count:
            count_sum += count[j_mod_k]
    return count_sum

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

from collections import defaultdict
cnt = defaultdict(int)

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

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

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

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

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

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

print(ans)