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 Counter

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

n,k=map(int,input().split())
a=list(map(int,input().split()))
# amari=[a[i]%k for i in range(n)]
rui=ruiseki(a)
# print(a)
# print(amari)
# print(rui)
dic=defaultdict(int)
ans=0
for i in range(n+1):
    if i>=k:
        dic[(rui[i-k]-(i-k))%k]-=1
    ans+=dic[(rui[i]-i)%k]
    dic[(rui[i]-i)%k]+=1
    # print(dic)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

n, k = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
shukei = defaultdict(int)
# AiからAjまでの和→SA[j]-SA[i-1]
# SA[j]-SA[i-1]=j-(i-1)
# 今回はkで割ったあまりなのでaccumulateは使わず自力
S = [0] * (n + 1)
T = [0] * (n + 1)
for i in range(1, n + 1):
    S[i] = S[i - 1] + A[i - 1]
    S[i] %= k
    T[i] = S[i] - i
    T[i] %= k
# i>=1, i<jで同じ値になっている組み合わせを探せば良い。
# kで割ったあまりなので、要素数j−(i-1)がkより小さくないといけない
ans = 0
if k > n + 1:
    for i in range(n + 1):
        shukei[T[i]] += 1
    for key, num in shukei.items():
        ans += num * (num - 1) // 2
else:
    shukei = defaultdict(int)
    for i in range(k):
        shukei[T[i]] += 1
    for key, num in shukei.items():
        ans += num * (num - 1) // 2
    for i in range(k, n + 1):
        j = i - k
        shukei[T[j]] -= 1
        temp = T[i]
        num = shukei[temp]
        ans += num
        shukei[temp] += 1
print(ans)

Submission status: Accepted

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

dic = dd(int)
K2 = min(N,K-1)
right = K2
for k,val in enumerate(c[1:K2+1]):
    dic[val] += 1
res = 0
# 左端を動かしていく
prev = 0
for val in c[1:]:
    tgt = prev
    res += dic[tgt]
    if right!=N:
        right += 1
        dic[c[right]] += 1
    dic[val] = max(0,dic[val]-1)
    prev = val
print(res)

Submission status: Accepted

Solution code:
import sys

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


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

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,k = map(int,readline().split())
if k == 1:
  print(0)
  exit()
  
a = [0]+[int(i) for i in readline().split()]
for i in range(1,n+1):
  a[i] = a[i-1]+a[i]
  
a = [(ai-i)%k for i,ai in enumerate(a)]
#print(a)
from collections import Counter,deque
c = Counter({a[0]:1})
d = deque([a[0]])
ans = 0
cnt = 1
for j,aj in enumerate(a[1:]):
  ans += c[aj]
  d.append(aj)
  c.update({aj:1})
  cnt += 1
  if cnt >= k:
    p = d.popleft()
    c.update({p:-1})
  
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,k = map(int,readline().split())
if k == 1:
  print(0)
  exit()
  
a = [0]+[int(i) for i in readline().split()]
for i in range(1,n+1):
  a[i] = a[i-1]+a[i]
  
a = [(ai-i)%k for i,ai in enumerate(a)]
#print(a)
from collections import Counter,deque
c = Counter({a[0]:1})
d = deque([a[0]])
ans = 0
cnt = 1
for j,aj in enumerate(a[1:]):
  ans += c[aj]
  d.append(aj)
  c.update({aj:1})
  cnt += 1
  if cnt >= k:
    p = d.popleft()
    c.update({p:-1})
  
print(ans)

Submission status: Accepted

Solution code:
import bisect
import collections
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.insert(0,0)
cuml=[0]*(N+1)
cuml[0]=A[0]
l=[]
cuml2=[]
l2=[]
buf=[]
ans=0
for i in range(N):
    cuml[i+1]=cuml[i]+A[i+1]
#print(cuml)
for i in range(N+1):
    cuml2.append([(cuml[i]-i)%K,i])
    cuml[i]=(cuml[i]-i)%K
#print(cuml2,cuml)
cuml2.sort(key=lambda x:x[0])
piv=cuml2[0][0]
buf=[]
for i in range(N+1):
    if piv!=cuml2[i][0]:
        l2.append(buf)
        piv=cuml2[i][0]
        buf=[]
    buf.append(cuml2[i][1])
l2.append(buf)
#print(l2)
cnt=0
for i in range(len(l2)):
    for j in range(len(l2[i])):
        num=l2[i][j]
        id=bisect.bisect_left(l2[i], num + K)
        #print(j,id)
        cnt=cnt+(id-j-1)
print(cnt)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter
import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


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

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

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

    return ans


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


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

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

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

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

from collections import Counter

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

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

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

    return ans



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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

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




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


print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# E

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

N, K = map(int, input().split())
a = list(map(int, input().split()))
a = [a-1 for a in a]
# print(a)

s = [0] + list(accumulate(a))
# print(s)
s = [s % K for s in s]
# print(s)

d = defaultdict(int)
queue = deque()

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

    ans += d[s]
    d[s] += 1
    # print(d)

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

ans = 0
c = Counter()
c[0] = 1

S = [0] * (N+1)
s = 0

for idx, a in enumerate(A):
    idx += 1

    if idx >= K: c[S[idx-K]] -= 1
        
    s = (s+a) % K
    
    b = (s - idx) % K
    S[idx] = b    
    ans += c[b]
    c[b] += 1
    
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

accm = [0] * (n + 1)
for i in range(n):
  accm[i + 1] = accm[i] + A[i]
  
li = [(val - itr) % k for itr, val in enumerate(accm)]

ans = 0
box = defaultdict(int)

for i in range(n + 1):
  if i >= k:
    box[li[i - k]] -= 1
  ans += box[li[i]]
  box[li[i]] += 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    a = [0] + list(map(int, input().split()))
    a = list(accumulate(a))
    d = {}
    res = 0
    for i in range(n+1):
        b = (i - a[i]) % k
        if i - k < 0:
            if b not in d:
                d[b] = 1
            else:
                res += d[b]
                d[b] += 1
        else:
            j = i - k
            c = (j - a[j]) % k
            d[c] -= 1
            if b not in d:
                d[b] = 1
            else:
                res += d[b]
                d[b] += 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
N,K=map(int,input().split())
alist=list(map(int,input().split()))
#print(alist)

slist=[0]
for i in range(N):
  slist.append(slist[-1]+alist[i])
#print(slist)

sslist=[]
for i in range(N+1):
  sslist.append((slist[i]-i)%K)
#print(sslist)

answer=0
si_dic=defaultdict(int)
for i in range(N+1):
  if i-K>=0:
    si_dic[sslist[i-K]]-=1
    
  answer+=si_dic[sslist[i]]
  si_dic[sslist[i]]+=1
  
print(answer)

Submission status: Accepted

Solution code:
from collections import defaultdict
import itertools


n,k= map(int, input().split())
a= list(map(int, input().split()))
a=[0]+list(itertools.accumulate(a))
b=[0]*(n+1)
for i,x in enumerate(a):
    b[i]=(x-i)%k
d=defaultdict(int)
ans=0
for i in range(n+1):
    if i>=k:
        d[b[i-k]]-=1
    ans+=d[b[i]]
    d[b[i]]+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import defaultdict
from itertools import accumulate

n, k = map(int, readline().split())
a = list(map(lambda x: int(x) - 1, readline().split()))
cumsum = [0] + list(map(lambda x: int(x) % k, list(accumulate(a))))
dict = defaultdict(int)
ans = 0
for i, v in enumerate(cumsum):
    ans += dict[v]
    dict[v] += 1
    if i >= k - 1:
        dict[cumsum[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(1, n + 1):
    b[i] = b[i - 1] + a[i - 1]
for i in range(n + 1):
    b[i] -= i
    b[i] %= k
d = dict()
for i in range(min(n + 1, k)):
    if b[i] in d:
        d[b[i]] += 1
    else:
        d[b[i]] = 1
ans = []
j = min(n + 1, k)
for i in range(n):
    ans.append(d[b[i]])
    d[b[i]] -= 1
    if j <= n:
        if b[j] in d:
            d[b[j]] += 1
        else:
            d[b[j]] = 1
    j += 1
ans = sum(ans) - n
print(ans)

Submission status: Accepted

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

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

rem_count = {}
rem_count[0] = 1
ans = 0
for i in range(1, N + 1):
    if i - K >= 0:
        rem_count[A[i - K] % K] -= 1
    if A[i] % K in rem_count:
        ans += rem_count[A[i] % K]
        rem_count[A[i] % K] += 1
    else:
        rem_count[A[i] % K] = 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
from collections import defaultdict

n,k = map(int,input().split())
lis = list(map(int,input().split()))
lis = [0] + [lis[i]-1 for i in range(n)]

ruiseki = list(itertools.accumulate(lis))

ruiseki = [x % k for x in ruiseki]
  # print(ruiseki)

counter = defaultdict(int)
ans = 0

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

print(ans)

Submission status: Accepted

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

Acs = np.cumsum(A)
Acs %= K

ans = 0
cnt = defaultdict(deque)
for i,c in enumerate(Acs):
    cnt[c].append(i)
    while cnt[c]:
        if i-cnt[c][0]> K-1:
            cnt[c].popleft()
        else:
            break
    ans += len(cnt[c]) - 1
print(ans)

Submission status: Accepted

Solution code:
"""
(sum(j) - sum(i)) % K = j - i
sum(j) % K - sum(i) % K = j- i
j - i < K
"""
n, k = map(int,input().split())
al = list(map(int,input().split()))

import itertools
al_ac = [0] + list(itertools.accumulate(al))

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

from collections import defaultdict
dic = defaultdict(int)

ans = 0
for i in range(n+1):
    ans += dic[al_ac[i]]
    dic[al_ac[i]] += 1
    if i - k+1 >= 0:
        dic[al_ac[i-k+1]] -= 1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

# dic = {remainder:number}
dic = {0:1}
ans = 0
if n < k:
    for i in range(1, n+1):
        if s[i] in dic:
            ans += dic[s[i]]
            dic[s[i]] += 1
        else:
            dic[s[i]] = 1

else:
    for i in range(1, k):
        if s[i] in dic:
            ans += dic[s[i]]
            dic[s[i]] += 1
        else:
            dic[s[i]] = 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:
N, K = map(int, input().split())
A = list(map(int, input().split()))
X = [0 for _ in range(N)]
D = {0: [-1]}
E = {0: 1}
X[0] = (A[0] - 1) % K
if X[0] in D:
  D[X[0]].append(0)
  E[X[0]] += 1
else:
  D[X[0]] = [0]
  E[X[0]] = 1
for i in range(1, N):
  X[i] = (X[i-1] + A[i] - 1) % K
  if X[i] in D:
    D[X[i]].append(i)
    E[X[i]] += 1
  else:
    D[X[i]] = [i]
    E[X[i]] = 1
S = 0
for i in D:
  n = E[i]
  if n > 1:
    L = D[i][:]
    m = L[-1]
    for j in range(n-1):
      x = L[j]
      if m - x < K:
        S += n - 1 - j
      else:
        l, r = j, n
        d = (l + r) // 2
        tmp = 2 * n
        while tmp != 0:
          if L[d] - x <= K - 1:
            l = d
            d = (l + r) // 2
          else:
            r = d
            d = (l + r) // 2
          tmp //= 2
        S += d - j
print(S)

Submission status: Accepted

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

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

A.append(0)
A.sort()

A=[((A[i]-i)%K,i) for i in range(0,N+1)]
A.sort()
count=0
s=0
t=1
while N>=t and N>=s:
    if A[t][0]==A[s][0] and K>A[t][1]-A[s][1]:
        t+=1
        if t==N+1:
            count+=((t-s)*(t-s-1))//2
    else:
        count+=t-s-1
        s+=1
        if s==t:
            t+=1

print(count)

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 = list(accumulate([0]+a))
b = [(s[i]-i)%k for i in range(n+1)]

d = defaultdict(int)
# 初期化
for i in range(min(k-1,n+1)):
    d[b[i]]+=1

ans = 0
for i in range(n):
    # 自分を除外し、k-1個先が存在すれば加える。
    d[b[i]]-=1
    if i+k-1<=n:
        d[b[i+k-1]]+=1
    ans += d[b[i]]

print(ans)

Submission status: Accepted

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


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

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

s = list(accumulate([0]+a))

b = [s[i]-i for i in range(n+1)]

d = defaultdict(list)

for i in range(n+1):
    d[b[i]%k].append(i)

ans = 0
for x in d.keys():
    l = d[x]
    for j in range(len(l)):
        y = l[j]
        ans += max(0,bisect.bisect_right(l,k+y-1)-j-1)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from collections import defaultdict

def main():
    N,K = map(int,input().split())
    a = list(map(int,input().split()))
    
    d = defaultdict(int)
    cum = [0]
    for i in range(N):
        cum.append((cum[-1]+a[i]-1)%K)
    
    ans = 0
    for i in range(N+1):
        ans += d[cum[i]]
        d[cum[i]] += 1
        if i >= K-1:
            d[cum[i-K+1]] -= 1
    
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def main():
  input=sys.stdin.readline
  n,k=map(int,input().split())
  a=list(map(int,input().split()))
  accum=[0]*n
  accum[0]=a[0]
  d=dict()
  ans=0
  for i in range(1,n):
    accum[i]+=a[i]+accum[i-1]
  accum=[0]+accum
  for j in range(n+1):
    if j-k>=0:
      d[(accum[j-k]-(j-k))%k]-=1
    if (accum[j]-j)%k not in d:
      d[(accum[j]-j)%k]=1
    else:
      ans+=d[(accum[j]-j)%k]
      d[(accum[j]-j)%k]+=1
    #print(d)
  return print(ans)
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
from bisect import *
n,k = map(int,input().split())
A = list(map(int,input().split()))

s = 0
sl = {0:[0]}
for i in range(n):
    s += A[i] - 1
    s %= k
    if s not in sl.keys():
        sl[s] = []
    sl[s].append(i+1)
ans = 0
for ls in sl.values():
    for i,l in enumerate(ls):
        x = bisect_right(ls, l + k - 1)
        ans += x - i - 1
print(ans)

Submission status: Accepted

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

n,k = map(int, input().split())
a = list(map(int, input().split()))
a = [0] + list(accumulate([(i-1) % k for i in a]))
a = [i % k for i in a]
ans = 0
maps = defaultdict(list)
for k1,v in enumerate(a):
  maps[v].append(k1)
for i in range(n):
  v = a[i]
  ans += bisect.bisect_right(maps[v],i+k-1) - bisect.bisect_right(maps[v],i)
print(ans)

Submission status: Accepted

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

n,k = map(int, input().split())
a = list(map(int, input().split()))
a = [0] + list(accumulate([(i-1) % k for i in a]))
a = [i % k for i in a]
ans = 0
maps = defaultdict(list)
for k1,v in enumerate(a):
  maps[v].append(k1)
for i in range(n):
  v = a[i]
  ans += bisect.bisect_right(maps[v],i+k-1) - bisect.bisect_right(maps[v],i)
print(ans)

Submission status: Accepted

Solution code:
# int(input()) # 入力が1つ
from collections import defaultdict
n, k = map(int, input().split()) # 入力が複数
nums = [int(i) for i in input().split()] # 配列で数字

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

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    b = list(map(int, input().split()))
    a = [0]*(n+1)
    for i in range(n):
        a[i+1] = b[i]
    for i in range(n+1):
        if 0 < i:
            a[i] += a[i-1]
        a[i] %= k
    for i in range(1, n+1):
        a[i] = (a[i] - (i%k) + k) % k
    dic = {}
    ans = 0
    l, r = 0, 0
#    print(a)
    while r < n+1:
        x = a[r]
        if k <= r-l:
            dic[a[l]] -= 1
            l += 1
        if x in dic.keys():
            ans += dic[x]
            dic[x] += 1
        else:
            dic[x] = 1
#        print(l, r)
        r += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import defaultdict, deque

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

    def accumulate(a, mod):
        s = 0
        yield s
        for x in a:
            s = (s + x - 1) % mod
            yield s

    acc = accumulate(a, mod=K)

    d = defaultdict(int)
    dq = deque()
    ans = 0
    for x in acc:
        if x in d:  # inで判定してみる
            ans += d[x]
        d[x] += 1
        dq.append(x)
        if len(dq) >= K:
            r = dq.popleft()
            d[r] -= 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import defaultdict, deque

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

    def accumulate(a, mod):
        s = 0
        yield s
        for x in a:
            s = (s + x - 1) % mod
            yield s

    acc = accumulate(a, mod=K)

    d = defaultdict(int)
    dq = deque()
    ans = 0
    for x in acc:
        ans += d[x]
        d[x] += 1
        dq.append(x)
        if len(dq) >= K:
            r = dq.popleft()
            d[r] -= 1
    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

Solution code:
def main():
    from collections import defaultdict, deque

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

    def accumulate(a, mod):
        s = 0
        yield s
        for x in a:
            s = (s + x - 1) % mod
            yield s

    *acc, = accumulate(a, mod=K)

    d = defaultdict(int)
    dq = deque()
    ans = 0
    for x in acc:
        ans += d[x]
        d[x] += 1
        dq.append(x)
        if len(dq) >= K:
            r = dq.popleft()
            d[r] -= 1
    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

Solution code:
from collections import Counter, deque

N, K = map(int, input().split())
A = list(map(int, input().split()))
INF = 10**18

cnt = Counter()
cnt[0] = 1
que = deque([0])
sumR = 0
ans = 0
for right, a in enumerate(A, start=1):
    if len(que) >= K:
        cnt[que.popleft()] -= 1
    sumR = (a + sumR) % K
    D = (sumR - right) % K
    ans += cnt[D]
    cnt[D] += 1
    que.append(D)
print(ans)

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]
    a[i+1] %=k
cnt = {}
ans = 0
for i in range(n+1):
    left = i-k
    if left >=0:
        ldiff = (a[left] - left)%k
        cnt[ldiff] -= 1
    x = (a[i] - i)%k
    if x <0:x+=k
    if x not in cnt:cnt[x] = 0
    ans+= cnt[x]    
    cnt[x] +=1
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
c1=[0]
c2=[k]
s=0
if k==1:
    print(0)
    sys.exit()
for i in range(n):
    s=(s+a[i])%k
    c1.append(s-i-1)
    c2.append(s+k-i-1)
d1={}
for i in range(1,n+1):
    if c1[i] in d1:
        d1[c1[i]]+=1
    else:
        d1[c1[i]]=1
ans=0
for i in range(n):
    if c1[i] in d1:
        ans+=d1[c1[i]]
    d1[c1[i+1]]-=1
d2={}
for i in range(1,min(k,n+1)):
    if c2[i] in d2:
        d2[c2[i]]+=1
    else:
        d2[c2[i]]=1
for i in range(n):
    if c1[i] in d2:
        ans+=d2[c1[i]]
    d2[c2[i+1]]-=1
    if i+k<=n:
        if c2[i+k] in d2:
            d2[c2[i+k]]+=1
        else:
            d2[c2[i+k]]=1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

N, K = map(int, input().split())
A = list(map(int, input().split()))
acc = [0]

for Ai in A:
    acc.append(acc[-1]+Ai)

cnt = defaultdict(int)
ans = 0

for i in range(N+1):
    ans += cnt[(acc[i]-i)%K]
    cnt[(acc[i]-i)%K] += 1
    
    if i>=K-1:
        j = i-(K-1)
        cnt[(acc[j]-j)%K] -= 1

print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,k,*aaa = get_all_int()
# log(aaa)
ruiseki = [0] * (n+1)
for i,a in enumerate(aaa):
    ruiseki[i+1] = (ruiseki[i] + a - 1) % k

count = {}
ans = 0
for right in range(len(ruiseki)):
    x = ruiseki[right]
    # log(x, count.get(x, 0), count)
    count[x] = count.get(x, 0) + 1

    if right >= k:
        y = ruiseki[right-k]
        count[y] -= 1

    ans += count.get(x, 0) - 1

print(ans)