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, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
A = [0] + LI()

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


ans = 0
D = defaultdict(int)
for j in range(n + 1):
    if j >= k:
        D[A[j - k]] -= 1
    ans += D[A[j]]
    D[A[j]] += 1





print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

count = defaultdict(int)
count[0] = 1

prefix = [0]*(n+1)
ans = 0

for i in range(n):
  pre = prefix[i+1] = (prefix[i] + seq[i] - 1)%k
  
  if i >= k - 1:
    count[prefix[i - k + 1]] -= 1
  ans += count[pre]
  count[pre] += 1
print(ans)

Submission status: Accepted

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

import sys
from collections import defaultdict
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
# 全要素-1した状態で作る
A = [(a-1)%K for a in LIST()]

# 累積和
acc = [0] + list(accumulate(A))
acc = [a%K for a in acc]

cnt = defaultdict(int)
ans = 0
for i, a in enumerate(acc):
    # 自分より前に出現した自分と同じ値、を答えに足す
    ans += cnt[a]
    # 度数分布に自分を加える
    cnt[a] += 1
    # K個以上前の値は減らす
    if i - K + 1 >= 0:
        cnt[acc[i-K+1]] -= 1
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()))
    X = [0] * (N+1)
    for i, a in enumerate(A):
        X[i+1] = (X[i] + a - 1) % K
    cnt = defaultdict(int)
    ans = 0
    for i in range(N+1):
        if i >= K:
            cnt[X[i-K]] -= 1
        ans += cnt[X[i]]
        cnt[X[i]] += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
s = [0]
for i in range(len(a)):
    s.append(s[-1]+a[i])
for i in range(len(s)):
    s[i] = (s[i] - i) % k
# print(s)
d = {0:1}
ans = 0
for j in range(1,n+1):
    if s[j] in d:
        d[s[j]] += 1
    else:
        d[s[j]] = 1
    if j >= k:
        d[s[j-k]] -= 1
    ans += d[s[j]] - 1
    # print(d)
    # print(ans)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
#show_flg=True

n,k=LI()
a=LI()
b=[k-1]
for i in range(n):
    b.append((b[-1]+a[i])%k)
b=[(b[i]-i)%k for i in range(n+1)]
ans=0
dc=defaultdict(int)
show(a)
show(b)
for i in range(n+1):
    if i>=k:
        dc[b[i-k]]-=1
    ans+=dc[b[i]]
    #if dc[b[i]]>0:show(i,a[i],dc[b[i]],ans)
    #show(i,b[i],dc)
    dc[b[i]]+=1

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, input().rstrip('\n').split()))
    ls = [0] + list(map(lambda x: int(x) - 1, input().rstrip('\n').split()))
    ls = [i % k for i in list(itertools.accumulate(ls))]
    
    d = collections.defaultdict(int)
    t = 0
    for i, x in enumerate(ls):
        t += d[x]
        d[x] += 1
        if i >= k - 1:
            d[ls[i - k + 1]] -= 1
    print(t)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
A = [0] + LI()

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


ans = 0
D = defaultdict(int)
for j in range(n + 1):
    if j >= k:
        D[A[j - k]] -= 1
    ans += D[A[j]]
    D[A[j]] += 1



if k == 1:
    print(0)
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
A = [0] + LI()

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


ans = 0
D = defaultdict(int)
for j in range(n, -1, -1):
    ans += D[A[j]]
    D[A[j]] += 1
    if j + k - 1 < n + 1:
        D[A[j + k - 1]] -= 1


if k == 1:
    print(0)
else:
    print(ans)

Submission status: Accepted

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

s=[0]
for i in range(n):
    s.append(s[-1]+a[i])
s=list(map(lambda x:x%k,s))
from collections import defaultdict
d=defaultdict(int)
d[0]=1
ans=0

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

Submission status: Accepted

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

if k==1:
    print(0)
    exit()
s=[0]
for i in range(n):
    s.append(s[-1]+a[i])
s=list(map(lambda x:x%k,s))
from collections import defaultdict
d=defaultdict(int)
d[0]=1
ans=0

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from copy import deepcopy
import itertools
input = sys.stdin.readline
# 文字列の場合は普通のinput()を使うか下を使う
# input = sys.stdin.readline().rstrip()

N, K = map(int, input().split())
A = list(map(int, input().split()))
S = [0] + list(itertools.accumulate(A))
"""
「iからjまで」--->「0からjまで」-「0から(i - 1)まで」
に分解すれば、求める条件は
(S[j] - S[i]) % K = j - i
と書ける。これを式変形して
S[j] - j = S[i] - i mod K "with j - i < K"
とすれば、次を示せばよい：

For 1 <= j <= N, count the number of j - K < i < j
such that S[j] - j = S[i] - i mod K
"""

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

d = defaultdict(int)
d[(S[0] - 0) % K] = 1

ans = 0
for j in range(1, N + 1):
    x = (S[j] - j) % K
    ans += d[x]
    d[x] += 1
    if j - K >= -1:
        y = (S[j - K + 1] - (j - K + 1)) % K
        d[y] -= 1

print(ans)

Submission status: Accepted

Solution code:
n,k,*a=map(int, open(0).read().split())
b=[0]*-~n
for i in range(n):b[i+1]=(a[i]+b[i]-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:
from itertools import accumulate
from collections import Counter
n, k, *a = map(int, open(0).read().split())
a = [x % k - 1 for x in a]
a = [0] + [x % k for x in accumulate(a)]
d = Counter()
ans = 0
for l, r in zip([k] * min(k, n + 1) + a, a):
	d[l] -= 1
	ans += d[r]
	d[r] += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n,k=MI()
    aa=LI()
    cs=[0]*(n+1)
    s=0
    for i,a in enumerate(aa,1):
        cs[i]=(cs[i-1]+a-1)%k
    #print(cs)
    cnt=defaultdict(int)
    ans=0
    for i,c in enumerate(cs):
        if i-k>=0:cnt[cs[i-k]]-=1
        ans+=cnt[c]
        cnt[c]+=1
    print(ans)

main()

Submission status: Accepted

Solution code:
import numpy
N,K=map(int,input().split())

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

A=list(map(int,input().split()))
S=[0]+list(numpy.cumsum(A)) #累積和
S2=[(S[i]-i)%K for i in range(N+1)]

d = {}
ans = 0
for j in range(1,N+1):
    if j>K-1:
        if S2[j-K] in d:
            d[S2[j-K]] -= 1
        
    if S2[j-1] in d:
        d[S2[j-1]] += 1
    else:
        d[S2[j-1]] = 1
        
    if S2[j] in d:
        ans += d[S2[j]]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import accumulate

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

d = Counter()

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

ans = 0
for i in range(N+1):
    ans += d[(A[i]-i) % K]
    d[(A[i]-i) % K] += 1
    if i-K+1 >= 0:
        d[(A[i-K+1] - (i-K+1)) % K] -= 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+1)]
for i in range(1,N+1):
    S[i] = S[i-1] + A[i-1]
cnt = 0
dict1 = {}
        
dict1[0] = 1

for j in range(1,N+1):
    if j-K >= 0:
        dict1[(S[j-K]-j+K)%K] -= 1
    if (S[j]-j)%K in dict1:
        cnt += dict1[(S[j]-j)%K]
        dict1[(S[j]-j)%K] += 1
    else:
        dict1[(S[j]-j)%K] = 1
print (cnt)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,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
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_()
    ans = 0
    before = defaultdict(int)
    *cumsum,=accumulate(A)
    for i,a in enumerate(cumsum):
        cumsum[i] = a%K
    # print(cumsum)
    for i,a in enumerate(cumsum):
        if i >= K:
            before[cumsum[i-K]]-=1
        ans += before[a]
        before[a]+=1

    ans += cumsum[:K-1].count(0)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
m = list(map(int, input().split()))
T = [0] * (n + 1)

b = 0
for i, a in enumerate(m):
    b += a - 1
    b %= k
    T[i + 1] = b

tmp = {}
count = 0

for i, b in enumerate(T):
    if i >= k:
        tmp[T[i - k]] -= 1

    if b in tmp:
        count += tmp[b]
        tmp[b] += 1
    else:
        tmp[b] = 1

print(count)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
A = LIST()

A_acc = list(accumulate(A))
S = [0] + A_acc
S = [(S[i]-i)%K for i in range(N+1)]

ans = 0
dic = defaultdict(int)

for i, x in enumerate(S):
	ans += dic[x]  # 範囲内かつ今まで出てきたxの個数を探す
	dic[x] += 1
	if i >= K-1:  # 範囲外のものを捨てる
		dic[S[i-K+1]] -= 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a=[i-1 for i in a]
    from itertools import accumulate
    import bisect
    a=[0]+list(accumulate(a))
    d=dict()
    a=[i%k for i in a]
    cnt=0
    for j,i in enumerate(a):
        if i not in d.keys():
            d[i]=[j]
        else:
            d[i].append(j)
    for l in d.values():
        for j,i in enumerate(l):
            cnt+=bisect.bisect_left(l,i+k)-j-1
    print(cnt)
main()

Submission status: Accepted

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

a_cs = [0] * (n + 1)
for i in range(n):
    a_cs[i + 1] = a_cs[i] + a[i]

d = defaultdict(list)
for i in range(n + 1):
    d[(a_cs[i] - i) % k].append(i)

ans = 0
for l in range(n):
    idx_1 = bisect_right(d[(a_cs[l] - l) % k], l)
    idx_2 = bisect_left(d[(a_cs[l] - l) % k], l + k)
    ans += idx_2 - idx_1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n, k = LI()
    a = LI_()
    ab = a[::1]
    a[0] = a[0] % k
    for i in range(n - 1):
        a[i + 1] = (a[i] + a[i + 1]) % k
    ans = 0
    q = deque([0])
    d = defaultdict(int)
    d[0] += 1
    for x, i in enumerate(a):
        q.append(i)
        if len(q) == k+1:
            x = q.popleft()
            d[x] -= 1
        ans += d[i]
        d[i] += 1
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from itertools import accumulate
read = sys.stdin.read

N, K, *A = map(int, read().split())
a = list(accumulate([0] + A))
a = [(a[i] - i) % K for i in range(N + 1)]

answer = 0
if N < K:
    for i in Counter(a).values():
        answer += i * (i - 1) // 2
else:
    dic = Counter(a[:K])
    for i in dic.values():
        answer += i * (i - 1) // 2
    here = K
    for i, x in enumerate(a[K:]):
        dic[a[i]] -= 1
        answer += dic[x]
        dic[x] += 1

print(answer)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from itertools import accumulate
read = sys.stdin.read

N, K, *A = map(int, read().split())
a = list(accumulate([0] + A))
a = [(a[i] - i) % K for i in range(N + 1)]

answer = 0
dic = defaultdict(int)

for i, x in enumerate(a):
    answer += dic[x]
    dic[x] += 1
    if i >= K - 1:
        dic[a[i - K + 1]] -= 1

print(answer)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from itertools import accumulate
read = sys.stdin.read

N, K, *A = map(int, read().split())
a = list(accumulate([0] + A))
a = [(a[i] - i) % K for i in range(N + 1)]


def cmb(x):
    return x * (x - 1) // 2


answer = 0
if N < K:
    for i in Counter(a).values():
        answer += cmb(i)
else:
    dic = Counter(a[:K])
    for i in dic.values():
        answer += cmb(i)
    here = K
    for i, x in enumerate(a[K:]):
        dic[a[i]] -= 1
        answer += dic[x]
        dic[x] += 1

print(answer)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

d = defaultdict(int)
ans = 0
for j in range(N + 1):
    v = (S[j] - j) % K
    ans += d[v]
    d[v] += 1
    if j >= K - 1:
        d[(S[j - K + 1] - (j - K + 1)) % K] -= 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_cs = [0] * (n + 1)
for i in range(n):
    a_cs[i + 1] = a_cs[i] + a[i]

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

    # print(j, d, d[(a_cs[j] - j) % k])
    ans += d[(a_cs[j] - j) % k]

    d[(a_cs[j] - j) % k] += 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()))
s=[0]
for i in a:
    s.append((s[-1]+i)%k)
mp={}
ans=0
for i in range(len(s)):
    if i-k>=0:
        mp[s[i-k]]-=1
    if s[i] in mp:
        ans+=mp[s[i]]
        mp[s[i]]+=1
    else:
        mp[s[i]]=1
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = [ int(i) for i in input().split() ]
ans = 0
dp = dict()
dp[0] = 1
pref = [ 0 for i in range(n+1) ]
pre = 0
for i in range(n):
    pre += a[i] - 1
    pre %= k
    pref[i+1] = pre
    if i >= k-1:
        dp[pref[i-k+1]] -= 1

    try:
        ans += dp[pre]
        dp[pre] += 1
    except:
        dp[pre] = 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()))
s=[0]
#print(a)
for i in a:
    s.append((s[-1]+i)%k)
#print(s)
mp={}
ans=0
for i in range(len(s)):
    if i-k>=0:
        mp[s[i-k]]-=1
    if s[i] in mp:
        ans+=mp[s[i]]
    if s[i] in mp:
        mp[s[i]]+=1
    else:
        mp[s[i]]=1
    #print(i,ans)
print(ans)
#ans+=sum(list(map(lambda x: x==0,s)))
#print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
B = [a%K for a in A]
cs = [0]
for b in B:
    c = (cs[-1] + b-1) % K
    cs.append(c)

from collections import deque
from collections import defaultdict
qs = defaultdict(lambda: deque())

ans = 0
for i,c in enumerate(cs):
    while qs[c] and qs[c][0] + K <= i:
        qs[c].popleft()
    ans += len(qs[c])
    qs[c].append(i)
print(ans)

Submission status: Accepted

Solution code:
import collections
def main():

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

    d = collections.defaultdict(int)

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

    ans = 0
    for j in range(N+1):
        v = (prefix[j] - j) % K
        ans += d[v]
        d[v] += 1
        if j >= K-1:
            d[(prefix[j-K+1] - (j-K+1)) % K] -= 1
        # print(ans)
    return ans



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

Submission status: Accepted

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

a = [0]

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

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

print(ans)

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

    C=defaultdict(list)
    for i in range(n+1):
        C[S[i]].append(i)

    ans=0
    C=list(C.values())
    for d in range(len(C)):
        n=len(C[d])
        if(n<=1): continue
        r=0
        for l in range(n):
            while(r+1<n and C[d][r+1]-C[d][l]<k):
                r+=1
            ans+=r-l
            if(r==l): r+=1
    print(ans)
resolve()

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

hm = {}
hm[A[0]] = 1
out = 0
for i in range(1,N):
  A[i] += A[i-1]
  A[i] %= K

for i in range(min(K-1,N)):
  if A[i]==0 and K != 1:
    out+=1
    
for i in range(1,min(N,K)):
  if A[i] in hm:
    hm[A[i]]+=1
  else:
    hm[A[i]]=1
  out += hm[A[i]]-1
  
for i in range(min(K,N),N):
  if A[i] in hm:
    hm[A[i]]+=1
  else:
    hm[A[i]]=1
  hm[A[i-K]] -= 1
  out += hm[A[i]]-1

print(int(out))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = [0] * (N+1)
for i, a in enumerate(A):
    B[i+1] = B[i] + a%K
for i in range(N+1):
    B[i] -= i
    B[i] %= K
ans = 0
# compress
C = B[::]
C.sort()
I = dict()
itmp = 0
I[C[0]] = 0
for i in range(1, N+1):
    if C[i] != C[i-1]:
        itmp += 1
        I[C[i]] = itmp

tbl = [0] * (N+1)
for i in range(min(K,N+1)):
    tbl[I[B[i]]] += 1
    ans += tbl[I[B[i]]] - 1
for i in range(K, N+1):
    tbl[I[B[i-K]]] -= 1
    tbl[I[B[i]]] += 1
    ans += tbl[I[B[i]]] - 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from collections import defaultdict

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

B = (np.add.accumulate(A) - np.arange(N+1)) % K

counter = defaultdict(int)
ans = 0

for j in range(N+1):
    if j - K >= 0:
        counter[B[j-K]] -= 1
    ans += counter[B[j]]
    counter[B[j]] += 1

print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
*A, = map(lambda x:(int(x)%K-1)%K,input().split())

class cumulative_sum:
    def __init__(self,A):
        N = len(A)
        self.S = [0]*(N+1)
        for i in range(N):
            self.S[i+1] = (self.S[i] + A[i])%K
    def get(self,i,j=None):
        if j==None:j=len(self.S)-1
        if j<=i:return 0
        return (self.S[j]-self.S[i])%K

SumA = cumulative_sum(A)

def binary_search(l,r,func):
    if func(l):return l-1
    if not func(r):return r
    while l+1<r:
        i = (l+r)//2
        if func(i):
            r = i
        else:
            l = i
    return l

def f(j):
    return cnt[s][j] > idx - K

ans = 0
cnt = {}
for idx,s in enumerate(SumA.S):
    if not s in cnt:
        cnt[s] = [-2*K]
    cnt[s].append(idx)
    l = len(cnt[s])
    j = binary_search(0,l-1,f)
    ans += (l-1)-(j+1)
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=[0]+list(map(int,input().split()))
for i in range(1,n+1):
    a[i]+=a[i-1]
for i in range(1,n+1):
    a[i]=(a[i]-i)%k
b=[[] for i in range(n+1)]
for i in range(n+1):
    b[i]=[a[i],i]
b.sort()
left=0
right=0
ans=0
while left<n:
    while right<n:
        if b[left][0]==b[right+1][0] and b[right+1][1]-b[left][1]<k:
            right+=1
        else:
            break
    ans+=right-left
    left+=1
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a2 = [0]
for i in range(n):
    a2.append(a2[-1] + a[i] - 1)
a2 = [a2[i] % k for i in range(n + 1)]
count = {}
temp = a2[:min(k, len(a2))]
for i in temp:
    count.setdefault(i, 0)
    count[i] += 1
ans = 0
for i in count.values():
    ans += (i * (i - 1) // 2)
for i in range(1, len(a2) - len(temp) + 1):
    temp = a2[i: i + len(temp)]
    temp2 = temp[:-1]
    ans += temp2.count(temp[-1])
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from itertools import accumulate as acc

def func(s):
    return (int(s)-1)%K


N,K=map(int,input().split())
a=list(map(int,input().split()))
x=[0]
tmp=0
for i in range(N):
    tmp=(tmp+a[i]-1)%K
    x+=[tmp]
dic={}
ans=0
if N<K:
    for i in range(N+1):
        if x[i] in dic: dic[x[i]]+=1
        else: dic[x[i]]=1
    for i in dic:
        ans+=dic[i]*(dic[i]-1)//2

    
else:
    for i in range(K):
        p=x[i]
        if p in dic: dic[p]+=1
        else: dic[p]=1
        ans+=dic[p]-1
    for i in range(K,N+1):
        p=x[i]
        if p in dic: dic[p]+=1
        else: dic[p]=1
        dic[x[i-K]]-=1
        ans+=dic[p]-1

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from itertools import accumulate as acc

def func(s):
    return (int(s)-1)%K


N,K=map(int,input().split())
a=list(map(int,input().split()))
x=[0]
tmp=0
for i in range(N):
    tmp=(tmp+a[i]-1)%K
    x+=[tmp]
dic={}
ans=0
if N<K:
    for i in range(N+1):
        if x[i] in dic: dic[x[i]]+=1
        else: dic[x[i]]=1
    for i in dic:
        ans+=dic[i]*(dic[i]-1)//2

    
else:
    for i in range(K):
        p=x[i]
        if p in dic: dic[p]+=1
        else: dic[p]=1
        ans+=dic[p]-1
    for i in range(K,N+1):
        p=x[i]
        if p in dic: dic[p]+=1
        else: dic[p]=1
        dic[x[i-K]]-=1
        ans+=dic[p]-1

print(int(ans))

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import accumulate

n, k = map(int, input().split())
aaa = list(map(int, input().split()))
bbb = list(accumulate(aaa))
ccc = list(-i % k for i in range(n))
ddd = [(b + c) % k for b, c in zip(bbb, ccc)]

# print(aaa)
# print(bbb)
# print(ccc)
# print(ddd)

count = dict(Counter(ddd[:k - 1]))
ans = 0
for i in range(n):
    key = (1 - aaa[i] + bbb[i] + ccc[i]) % k
    if key in count:
        ans += count[key]

    j = i + k - 1
    if j < n:
        dj = ddd[j]
        if dj not in count:
            count[dj] = 1
        else:
            count[dj] += 1

    di = ddd[i]
    count[di] -= 1
    if count[di] == 0:
        count.pop(di)

print(ans)

Submission status: Accepted

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

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

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

n = 1
if n in D:
  ans = D[n]
else:
  ans = 0
for i in range(N):
  if L[i] != -1:
    D[L[i]] -= 1
  if i + K - 1 < N:
    t = (t + A[i + K - 1] - 1) % K
    if t < 0:
      t += K
    if t in D:
      D[t] += 1
    else:
      D[t] = 1
    L[i + K - 1] = t
  n = (n - 1 + A[i]) % K
  #n -= 1
  if n < 0:
    n += K
  if n in D:
    ans += D[n]
  
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right

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

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

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

dic = {}
for i, b in enumerate(B):
    if not b in dic.keys():
        dic[b] = [i]
    else:
        dic[b].append(i)

ans = 0
for L in dic.values():
    for i in range(len(L)):
        #print(L, i)
        j = bisect_right(L, L[i]+K-1)
        #print(j)
        ans += j-i-1
print(ans)