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

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
#MOD=10**9+7
# sys.setrecursionlimit(2147483647)
# import math
#import numpy as np
# import operator
# import bisect
# from heapq import heapify,heappop,heappush
#from math import gcd
# from fractions import gcd
#from collections import deque
from collections import defaultdict
# from collections import Counter
from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
# from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
# from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


def main():
	n,k=map(int,input().split())
	A=list(map(int,input().split()))
	S=[0]+list(accumulate(A))
	for i in range(n+1):
		S[i]-=i
		S[i]%=k
	
	dct=defaultdict(int)
	
	ans=0
	for j in range(n+1):
		dct[S[j]]+=1
		if j>=k:
			dct[S[j-k]]-=1
		ans+=dct[S[j]]-1
	print(ans)
	
if __name__ == "__main__":
		main()

Submission status: Accepted

Solution code:

from collections import deque
from collections import defaultdict


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

Submission status: Accepted

Solution code:
import math
import sys
import bisect
import array

m=10**9 + 7 
sys.setrecursionlimit(1000010)
(N,K) = map(int,input().split())
A = list( map(int,input().split())) 
# print(N,K,A)
B = list( map(lambda x: x % K, A))
C = [0]
x = 0
i = 0 
for b in B:
    x = (x + b ) % K 
    C.append((x-i-1) % K) 
    i += 1 
    
# print(B,C)

E={}


ans=0
for i in range(N+1):
    if C[i] in E:
        ans += E[C[i]]
        E[C[i]] = E[C[i]] + 1
    else:
        E[C[i]] = 1
    if i >= K-1:
        E[C[i-K+1]] = E[C[i-K+1]] - 1
        if E[C[i-K+1]] == 0:
             E.pop(C[i-K+1])

print(ans)
exit(0)

Submission status: Accepted

Solution code:
from collections import deque
n, k = map(int, input().split())
a = list(map(int, input().split()))
#kを法とする配列を作る
a = [(i - 1) for i in a]
acc_a = [0 for i in range(n+1)]
acc_a[0] = 0
acc_a[1] = a[0] % k
#kを法とする累積和
for i in range(2,len(a) + 1):
    acc_a[i] = (a[i - 1] + acc_a[i-1]) % k
ans = 0
count = {}
q = deque()
for i in acc_a:
    if i not in count:
        count[i] = 0
    ans += count[i]
    count[i] += 1
    q.append(i)
    if len(q) == k:
        count[q.popleft()] -= 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n, k = map(int, input().split())
a = list(map(int, input().split()))
#kを法とする配列を作る
a = [(i - 1) for i in a]
acc_a = [0 for i in range(n+1)]
acc_a[0] = 0
acc_a[1] = a[0] % k
#kを法とする累積和
for i in range(2,len(a) + 1):
    acc_a[i] = (a[i - 1] + acc_a[i-1]) % k
ans = 0
count = {}
q = deque()
for i in acc_a:
    if i not in count:
        count[i] = 0
    ans += count[i]
    count[i] += 1
    q.append(i)
    if len(q) == k:
        count[q.popleft()] -= 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N, K = map(int, input().split())
A = list(map(lambda s: int(s) % K, input().split()))

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

counts = Counter()
ans = 0
for i in range(N + 1):

    if i >= K:
        counts[cumAm1[i - K]] -= 1

    cur = cumAm1[i]
    ans += counts[cur]

    counts[cur] += 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()))
    
    ans = 0
    ruiseki = [0]
    d = defaultdict(int)
    d[0]=1
    for i in range(n):
        if i - k + 1>= 0:
            d[ruiseki[i - k+1]]-=1
        ruiseki.append((ruiseki[i] + a[i] - 1)%k)
        ans += d[ruiseki[i+1]]
        d[ruiseki[i + 1]] += 1
    print(ans)
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# E - Rem of Sum is Num
import queue
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] - 1) % K

v_set = set(S)
mp = {v: 0 for v in v_set}
ans = 0
q = queue.Queue()
for i in range(N + 1):
    ans += mp[S[i]]
    mp[S[i]] += 1
    
    q.put(S[i])
    if q.qsize() == K:
        mp[q.get()] -= 1

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
from collections import defaultdict

N,K = map(int,input().split())
# 全要素を-1する
A = [0] + [int(i)-1 for i in input().split()]

# Acum[i]: A[1]からA[i]までの累積和
Acum = np.cumsum(A)
Acum = [i%K for i in Acum]

answer = 0
counter = defaultdict(int)

# iの範囲で探索
# 1 <= j <= N
# j-K+1 <= i <= j-1
for j,x in enumerate(Acum):
    # (i-K+1)回目から(i-1)回目の探索において、xの出現回数
    answer += counter[x]
    # i回目の結果を辞書に追加
    counter[x] += 1
    # 辞書にK回追加した場合
    if j-K+1 >= 0:
        # 辞書から一番古い探索記録を削除
        counter[Acum[j-K+1]] -= 1

print(answer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
from collections import defaultdict

N,K = map(int,input().split())
A = [0] + [int(i)-1 for i in input().split()]
Acum = np.cumsum(A)
Acum = [i%K for i in Acum]

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

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
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC146 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
S := aの累積和
(Sj - Si) % k = j - i
ある整数mに対して
Sj - Si = m*k + j - i
Sj - j = m*k + Si - i
(Sj - j) - (Si - i) Ξ 0 (mod k)
(Sj - j) Ξ (Si - i) (mod k)
"""
n,k = LI()
a = LI()
s = [0] + list(accumulate(a))
ans = 0
d = defaultdict(int)
for j in range(n+1):
    t = (s[j] - j) % k
    if j >= k:
        x = (s[j-k] - (j-k)) % k
        d[x] -= 1
    ans += d[t]
    d[t] += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N,K=map(int, input().split())
A=list(map(int,input().split()))
"""count=0
for l in range(N):
    if A[l]%K==1:
        count+=1
for l in range(N-1):
    sum=A[l]
    for r in range(l+1,N):
        sum+=A[r]
        if sum%K==r-l+1:
            count+=1
print(count)"""
cum=[0]*(N+1)
for i in range(N):
    cum[i+1]=(cum[i]+A[i]-1)%K
dic=defaultdict(int)
ans=0
for i in range(N+1):
    ans+=dic[cum[i]]
    dic[cum[i]]+=1
    if i-(K-1)>=0:
        dic[cum[i-(K-1)]]-=1
print(ans)

Submission status: Accepted

Solution code:
import itertools
from collections import defaultdict

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

A = [0] + [x-1 for x in A]

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

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

print(answer)

Submission status: Accepted

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

B = [0]*(N+1)

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

Q = {}
X = 0

for i, b in enumerate(B):
    if i>=K:
        Q[B[i-K]] -= 1
 
    if b in Q:
        X += Q[b]
        Q[b] += 1
    else:
        Q[b] = 1

print(X)

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+1]+a[i]-1)%k
from collections import defaultdict
d=defaultdict(int)
x=0
d[0]=1
for i in range(1,n+1):
  if i-k>=0:d[a[i-k]]-=1
  x+=d[a[i]]
  d[a[i]]+=1
print(x)

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

    ans=0
    C=defaultdict(int)
    Q=deque()
    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:
import sys
from collections import defaultdict

#+++++
		
def main():
	n, k = map(int, input().split())
	aal = list(map(int, input().split()))
	
	sss = [0]*(n+1)
	si=0
	for i, a in enumerate(aal):
		si+=a-1
		sss[i+1]=si%k
	
	count=0
	mkl_dict=defaultdict(lambda :0)
	for j in range(n+1):
		sj=sss[j]
		if j-k >= 0:
			mkl_dict[sss[j-k]]-=1
		count += mkl_dict[sj]
		mkl_dict[sj] += 1
			
	print(count)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import defaultdict
N, K = map(int, input().split())
A = [0] + [a-1 for a in map(int, input().split())]
A_cum = list(accumulate(A))
A_cum = [a%K for a in A_cum]

ans = 0
dd = defaultdict(int)
q = []
for j in range(N+1):  
  ans += dd[A_cum[j]]
  dd[A_cum[j]] += 1
  q.append(A_cum[j])
  if len(q) == K:
    dd[q[0]] -= 1
    q.pop(0)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N, K = map(int, input().split())
A = list(map(int, input().split()))
res = 0
cs = [0] * (N + 1)
d = dd(list)
d[0].append(0)
for i in range(N):
  cs[i + 1] = cs[i] + A[i] - 1
  cs[i + 1] %= K
  d[cs[i + 1]].append(i + 1)
for i in range(N):
  x = bl(d[cs[i]], i) + 1
  y = bl(d[cs[i]], i + K)
  res += y - x
  #print(x, y, i)
  #print(res)
print(res)

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import Counter

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

S = [0] + [a % K for a in accumulate(a - 1 for a in A)]

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

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
from itertools import count
from collections import defaultdict
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#


def main():
    N, K = mis()
    A = [0] + lmis()
    for i in range(1, len(A)):
        A[i] = ((A[i] - 1) + A[i-1]) % K
    #
    C = defaultdict(int)
    ans = 0
    for i in range(len(A)):
        if i >= K:
            C[A[i-K]] -= 1
        a = A[i]
        ans += C[a]
        C[a] += 1
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    B=[0]*(N+1)
    for i in range(N):
        B[i+1]=(A[i]+B[i]-1)%K
    ans=0
    d={}
    for i in range(1,N+1):
        if i-K<0:
            if B[i-1] in d:
                d[B[i-1]]+=1
            else:
                d[B[i-1]]=1
        else:
            if B[i-1] in d:
                d[B[i-1]]+=1
            else:
                d[B[i-1]]=1
            d[B[i-K]]-=1
        if B[i] in d:
            ans+=d[B[i]]
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

print(ans)

Submission status: Accepted

Solution code:
def e_rem_of_sum_is_num():
    # 参考: https://maspypy.com/atcoder-参加感想-2019-11-16abc-146
    from itertools import accumulate
    from collections import defaultdict

    N, K = [int(i) for i in input().split()]
    # 1 引くと、条件を満たす連続部分列の要素の平均は 0 (mod K で) となる
    A = [0] + [int(i) - 1 for i in input().split()]

    acc = list(accumulate(A))
    acc = [x % K for x in acc]  # mod K 上で同一視する

    # S_j ≡ S_i となるような j-K < i < j の個数を数え上げればいい。
    # そのためには、j 未満のインデックスに対する S の度数分布を管理しておけばいい。
    counter = defaultdict(int)  # 値の度数分布
    ans = 0
    for j, x in enumerate(acc):
        ans += counter[x]
        # 数列の右端を追加
        counter[x] += 1
        # 数列の左端を削除 (数列の長さが K 未満になるようにする。
        # 数列の長さが K 以上だと、数列の和を K で割った余りと一致するはずがない)
        if j - K + 1 >= 0:
            counter[acc[j - K + 1]] -= 1
    return ans

print(e_rem_of_sum_is_num())

Submission status: Accepted

Solution code:
import itertools
from collections import defaultdict

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

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

A = [0] + [x-1 for x in A]

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

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

print(answer)

Submission status: Accepted

Solution code:
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]-1)%k
d = dict()
ans = 0
for i in range(n+1):
    if i >= k:
        d[a[i-k]] -= 1
    if a[i] in d:
        ans += d[a[i]]
        d[a[i]] += 1
    else:
        d[a[i]] = 1
print(ans)

Submission status: Accepted

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

ans = 0
dd = defaultdict(int)
q = []
for i, a in enumerate(A_cum):
  a -= i
  a %= K
  if i-K >= 0:
    dd[q[i-K]] -= 1
  ans += dd[a]
  dd[a] += 1
  q.append(a)
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()))

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

# print(S)

D = {}
S = [0] + S
ans = 0
for i in range(len(S)):
    key = (S[i] - i) % k

    if i >= k:
        j = i-k
        key1 = (S[j] - j) % k
        D[key1] -= 1
        try:
            ans += D[key1]
            # print(i, j, D[key1])
        except:
            ans += 0

    try:
        D[key] += 1
    except:
        D[key] = 1

for j in range(max(0, len(S)-k), len(S)):
    key1 = (S[j] - j) % k
    D[key1] -= 1
    try:
        ans += D[key1]
        # print(i, j, D[key1])
    except:
        ans += 0
# print(D)
print(ans)

Submission status: Accepted

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

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

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

memo = {}
cnt = 0
ans = 0
for i in range(n+1):
    if ruiseki[i] in memo:
        ans += memo[ruiseki[i]]

    if ruiseki[i] in memo:
        memo[ruiseki[i]] += 1
    else:
        memo[ruiseki[i]] = 1

    if cnt < k - 1:
        cnt += 1
    else:
        memo[ruiseki[i-cnt]] -= 1 

print(ans)

Submission status: Accepted

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

ans=0
dict=collections.defaultdict(int)
for i in range(1,n+1):
  x=m[i]
  if i<=k-1:
    dict[m[i-1]]+=1
  else:
    dict[m[i-1]]+=1
    dict[m[i-k]]-=1
  ans+=dict[x]
print(ans)

Submission status: Accepted

Solution code:
import collections
n,k=map(int,input().split())
a=list(map(int,input().split()))
m=[]
m2=[0]
for i in range(n):
  m.append(a[i])
for i in range(n):
  m2.append((m2[-1]+m[i]))
for i in range(n+1):
  m2[i]-=i
  m2[i]%=k

ans=0
dict=collections.defaultdict(int)
for i in range(1,n+1):
  x=m2[i]
  if i<=k-1:
    dict[m2[i-1]]+=1
  else:
    dict[m2[i-1]]+=1
    dict[m2[i-k]]-=1
  ans+=dict[x]
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 itertools import groupby
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
    T=[(s,i) for i,s in enumerate(S)]
    T.sort()

    ans=0
    for key,group in groupby(T,lambda x:x[0]):
        G=[i for s,i in group]
        n=len(G)
        r=0
        for l in range(n):
            while(r+1<n and G[r+1]-G[l]<k):
                r+=1
            ans+=r-l
    print(ans)
resolve()

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(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)
    ans=0
    for i in range(n+1):
        ans+=C[S[i]]
        C[S[i]]+=1
        if(i-k+1>=0): C[S[i-k+1]]-=1
    print(ans)
resolve()

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(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)
    ans=0
    for i in range(n+1):
        if(i-k>=0):
            C[S[i-k]]-=1
        ans+=C[S[i]]
        C[S[i]]+=1
    print(ans)
resolve()

Submission status: Accepted

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

A=list(map(lambda x:x%K-1,A))
sa=[0]*(N+1)
for i in range(1,N+1):
  sa[i]=(sa[i-1]+A[i-1])%K

c=Counter(sa[:K-1])

ans=0
for i in c.values():
  ans+=i*(i-1)//2
  
for i in range(K-1,N+1):
  ans+=c[sa[i]]
  c[sa[i-(K-1)]]-=1
  c[sa[i]]+=1

  
print(ans)

Submission status: Accepted

Solution code:
import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n, k = ril()
ls = ril()
acc = [0]
for x in ls:
    acc.append((acc[-1] + x - 1) % k)
counter = collections.Counter(acc[:k])
res = 0
for i in range(n + 1):
    res += counter[acc[i]] - 1
    counter[acc[i]] -= 1
    if i + k < n + 1:
        counter[acc[i + k]] += 1
print(res)

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

mods = defaultdict(int)
cnt = 0
tmp = 0
for i in range(min(k-1, n)):
	tmp = (tmp+a[i])%k
	mods[tmp] += 1
	cnt += 1

ans = 0
tmp2 = 0
for i in range(n):
	ans += mods[tmp2]
	tmp2 = (tmp2+a[i])%k
	mods[tmp2] -= 1
	if cnt < n:
		tmp = (tmp+a[cnt])%k
		mods[tmp] += 1
		cnt += 1

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
if k==1:
    print(0)
    exit()
nl=[]
for i in range(n):
    nl.append((l[i]-1)%k)
r=[0]*(n+1)
for i in range(n):
    r[i+1]=(r[i]+nl[i])%k
p=[]
for i in range(n+1):
    p.append([r[i],i])
p.sort()
s=0
e=0
ans=0
f=0
while e<n+1:
    if p[s][0]!=p[e][0]:
        ans+=f*(f-1)//2
        s=e
        f=0
    else:
        if p[s][1]+k-1>=p[e][1]:
            f+=1
            e+=1
        else:
            ans+=f-1
            f-=1
            s+=1
print(ans+f*(f-1)//2)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

n, k = map(int, input().split())
a = tuple(map(int, input().split()))
acc = [0]
t = 0
for a_ in a:
    t = (t + a_ - 1) % k
    acc.append(t)

d = defaultdict(int)

ret = 0
count = 0
dq = deque()

for acc_ in acc:
    ret += d[acc_]
    d[acc_] += 1
    dq.append(acc_)
    if len(dq) >= k:
        v = dq.popleft()
        d[v] -= 1
print(ret)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

N,K = m()

a = l()


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

count = 0
ddd = dict()
ddd[0] = 1
if K == 1:
    print(0)
else:
    for i in range(1,N+1):
        ppp = (aaa[i] - i)%K
        count += ddd.get(ppp,0)
        ddd[ppp] = ddd.get(ppp,0) + 1
        if i - K + 1 >= 0:
            ddd[(aaa[i-K+1] - i + K - 1)%K] -= 1
    print(count)

Submission status: Accepted

Solution code:
n,k=[int(j) for j in input().split()]
a=[int(j) for j in input().split()]
from itertools import accumulate
l=[0]+list(accumulate(a))
ll=[]
for i in range(n+1):
    ll.append((i-l[i])%k)
import collections
c=collections.Counter()
ans=0
for i in range(n+1):
    ans+=c[ll[i]]
    c[ll[i]]+=1
    if i>=k-1:
        c[ll[i-k+1]]-=1
print(ans)

Submission status: Accepted

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

if K == 1:
    print(0)
else:
    S, LUT, ans = [0], {0: 1}, 0
    for a in A:
        S.append(S[-1] + a)
    for i in range(1, N + 1):
        p = (S[i] - i) % K
        ans += LUT.get(p, 0)
        LUT[p] = LUT.get(p, 0) + 1
        if i - K + 1 >= 0:
            LUT[(S[i - K + 1] - i + K - 1) % K] -= 1
    print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = [int(ai) - 1 for ai in input().split()]
s = [0]
cur = 0
for ai in a:
    cur += ai
    cur %= k
    s.append(cur)

d = {}
ans = 0

# first interval
for si in s[:k]:
     if si in d:
         d[si] += 1
     else:
        d[si] = 1
for key in d:
    val = d[key]
    if val > 1:
        ans +=  val * (val - 1) // 2

# syakutori
r = 0
for l in range(k, n+1):
    d[s[r]] -= 1
    if s[l] in d:
        ans += d[s[l]]
        d[s[l]] += 1
    else:
        d[s[l]] = 1
    r += 1

print(ans)

Submission status: Accepted

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


# あらかじめ数列から１を引いておく
A = [a - 1 for a in A]

# mod K の累積和を取る
S = [0] + list(accumulate(A))
S = [s % K for s in S]


ans = 0
counter = defaultdict(int)
for i, s in enumerate(S):
    ans += counter[s]  # 過去の出現数を参考に数え上げ

    counter[s] += 1  # 今見たところを追加
    if i - K + 1 >= 0:
        counter[S[i - K + 1]] -= 1  # 条件を見たしうる長さK-1からはみ出たところを取り除く

print(ans)

Submission status: Accepted

Solution code:
def solve():
  from itertools import accumulate
  from sys import stdin
  
  f_i = stdin
  N, K = map(int, f_i.readline().split())
  A = map(int, f_i.readline().split())
  S = accumulate(a - 1 for a in A)
  S = (0, ) + tuple(s % K for s in S)
  
  rec = {}
  ans = 0
  for j, S_j in enumerate(S):
    if j >= K:
      rec[S[j-K]] -= 1
    if S_j in rec:
      ans += rec[S_j]
      rec[S_j] += 1
    else:
      rec[S_j] =1
  
  print(ans)

solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import accumulate
n, k = map(int, input().split())
a = list(map(int, input().split()))
s = [0] + list(accumulate(a))


def f(x):
    return (x + n * k) % k


ans = 0
dic = {}
for i in range(n + 1):
    if i >= k:
        prev = f(s[i - k] - (i - k))
        dic[prev] -= 1

    cur = f(s[i] - i)
    if cur in dic:
        ans += dic[cur]
        dic[cur] += 1
    else:
        dic[cur] = 1

print(ans)

Submission status: Accepted

Solution code:
def examE():
    N, K = LI()
    A = LI()
    sumA = [0]*(N+1)
    for i in range(1,N+1):
        sumA[i] = sumA[i-1]+A[i-1]
    d = defaultdict(int)
    ans = 0
    #連想配列 先頭からの番号　余分な量
    que = deque()
    for i,a in enumerate(sumA):
        #K番目以降は一番左のやつ消していく
        if que and que[0][0] <= (i-K):
            d[que.popleft()[1]] -= 1
        cur = (a-i)%K
        ans +=d[cur]
        d[cur] +=1
        que.append((i,cur))
#        print(ans,que,d,a-i)
    print(ans)
    return

def examF():
    return

import sys,copy,bisect,itertools,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examE()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(lambda x: int(x)-1, input().split()))
sa = [0]
for a in A:
    sa.append((sa[-1] + a) % K)
d = {0: 1}
ans = 0
for i in range(1, N+1):
    if i >= K:
        d[sa[i-K]] -= 1
    v = d.get(sa[i], 0)
    ans += v
    d[sa[i]] = v + 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

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

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

cnt = defaultdict(int)
que = deque([])
ans = 0

for i, c in enumerate(cumA):
    while que and que[0][0] <= i - K:
        cnt[que.popleft()[1]] -= 1
    diff = (i - c) % K
    ans += cnt[diff]
    cnt[diff] += 1
    que.append((i, diff))
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import itertools

N, K = map(int, input().split())
A = [int(c)-1 for c in input().split()]
A = [0] + A
Acum = list(itertools.accumulate(A))
Acum = [x%K for x in Acum]

counter = defaultdict(int)

ans = 0
for i,x in enumerate(Acum):
  ans += counter[x]
  counter[x] += 1
  if i>=K-1:
    counter[Acum[i-K+1]] -= 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import accumulate
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

A_acc = [0]+list(accumulate(A))


ans = 0
D = defaultdict(int)
for l in range(N+1):
    t = (A_acc[l]-l) % K
    if l>=K:
      r = (A_acc[l-K]-(l-K))
      D[r%K]-=1
    ans += D[t]
    D[t] += 1


print(ans)

Submission status: Accepted

Solution code:
#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, K = getlist()
	A = getlist()
	for i in range(N):
		A[i] -= 1

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

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

if __name__ == '__main__':
	main()