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: Runtime Error

Solution code:
import sys

#+++++
		
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=[0]*k
	for j in range(n+1):
		sj=sss[j]
		if j-k >= 0:
			#pa((j-k, sss[j-k]))
			mkl[sss[j-k]]-=1
		#pa((mkl,sj))
		count += mkl[sj]
		mkl[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: Runtime Error

Solution code:
import sys

#+++++
		
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=[0]*k
	for j in range(n+1):
		sj=sss[j]
		if j-k >= 0:
			#pa((j-k, sss[j-k]))
			mkl[sss[j-k]]-=1
		#pa((mkl,sj))
		count += mkl[sj]
		mkl[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: Runtime Error

Solution code:
import sys

#+++++
		
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=[0]*k
	for j in range(n+1):
		sj=sss[j]
		for i in range(j-1, max(-1, j-k), -1):
			si=sss[i]
			pa((j,i,sj, si, (sj - si) % k))
			if (sj - si) % k == 0:
				#pa((i,j))
				count+=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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000000)
from itertools import count
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 = [0] * (max(A)+1)
    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: Runtime Error

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(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: Runtime Error

Solution code:
N,K = input().split()
N,K = int(N),int(K)
#A = list(map(int,input().split()))
A = input().split()
A = [int(a) for a in A]
#N = 2*100000
#K = 3#random.randint(1,100)
#A = [random.randint(0,10000) for i in range(N)]

import numpy as np
per_Ks = np.zeros((N+1,K))
per_Ks[0][0] = 1

S_j_ = 0
count = 0

for j in range(1,N+1):
    j_ = j-1
    S_j_ += A[j_]
    
    per_K = int((S_j_-j)%K)
    per_Ks[j] = per_Ks[j-1]
    per_Ks[j][per_K] += 1
    
    max_ = max([0,j-K+1])
    if(max_==0):
        c = per_Ks[j-1][per_K]
        count += int(c)
    else:
        c = per_Ks[j-1][per_K]-per_Ks[max_-1][per_K]
        count += int(c)
        
print(count)

Submission status: Runtime Error

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

import numpy as np
per_Ks = np.zeros((N+1,K))
per_Ks[0][0] = 1

def f(j,S_j):
    return S_j%K-j 

i,j = 0,1
S_j_ = 0
count = 0

for j in range(1,N+1):
    j_ = j-1
    S_j_ += A[j_]
    
    per_K = (S_j_-j)%K
    per_Ks[j] = per_Ks[j-1]
    per_Ks[j][per_K] += 1
    
    max_ = max([0,j-K+1])
    if(max_==0):
        c = per_Ks[j-1][per_K]
        count += int(c)
    else:
        c = per_Ks[j-1][per_K]-per_Ks[max_-1][per_K]
        count += int(c)
        
print(count)

Submission status: Runtime Error

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

import numpy as np
per_Ks = np.array([0 for i in range(N+1)])
per_Ks = np.zeros((N+1,K))
per_Ks[0][0] = 1

def f(j,S_j):
    return S_j%K-j 

i,j = 0,1
S_j_ = 0
count = 0

for j in range(1,N+1):
    j_ = j-1
    S_j_ += A[j_]
    S_j[j] = S_j_
    
    per_K = (S_j_-j)%K
    per_Ks[j] = per_Ks[j-1]
    per_Ks[j][per_K] += 1
    
    max_ = max([0,j-K+1])
    if(max_==0):
        c = per_Ks[j-1][per_K]
        count += c
    else:
        c = per_Ks[j-1][per_K]-per_Ks[max_-1][per_K]
        count += c
        
print(int(count))

Submission status: Runtime Error

Solution code:
import numpy as np
N,K = input().split()
N,K = int(N),int(K)
A = list(map(int,input().split()))
S_j = [0 for i in range(N+1)]
per_Ks = np.array([0 for i in range(N+1)])
per_Ks = np.zeros((N+1,K))
per_Ks[0][0] = 1
def f(j,S_j):
    return S_j%K-j 

i,j = 0,1
S_j_ = 0
count = 0

for j in range(1,N+1):
    j_ = j-1
    S_j_ += A[j_]
    S_j[j] = S_j_
    
    per_K = (S_j_-j)%K
    per_Ks[j] = per_Ks[j-1]
    per_Ks[j][per_K] += 1
    
    max_ = max([0,j-K+1])
    if(max_==0):
        c = per_Ks[j-1][per_K]
        count += c
    else:
        c = per_Ks[j-1][per_K]-per_Ks[max_-1][per_K]
        count += c
        
print(int(count))

Submission status: Runtime Error

Solution code:
N,K = input().split()
N,K = int(N),int(K)
A = list(map(int,input().split()))
S_j = [0 for i in range(N+1)]
per_Ks = np.array([0 for i in range(N+1)])

def f(j,S_j):
    return S_j%K-j 

i,j = 0,1
S_j_ = 0
count = 0

for j in range(1,N+1):
    j_ = j-1
    S_j_ += A[j_]
    S_j[j] = S_j_
    
    per_K = (S_j_-j)%K
    per_Ks[j] = per_K
    
    max_ = max([0,j-K+1])
    count += (per_Ks[max_:j]==per_K).sum()
            
print(count)

Submission status: Runtime Error

Solution code:
n, k = map(int,input().split())
x = 0
ans = 0
A = [0]*k
A[0]=1
for a in map(int, input().split()):
  x+=a-1
  x%=k
  ans+=A[x]
  A[x]+=1
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int,input().split())
x = 0
ans = 0
A = [0]*k
A[0]=1
for a in map(int, input().split()):
  x+=a-1
  x%=k
  ans+=A[x]
  A[x]++
  print(ans)

Submission status: Runtime Error

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 = [0] * K
  
  ans = 0
  for j, S_j in enumerate(S):
    if j >= K:
      rec[S[j-K]] -= 1
    ans += rec[S_j]
    rec[S_j] += 1
  
  print(ans)

solve()

Submission status: Runtime Error

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())
  A = (a % K for a in A)
  S = (0,) + tuple(accumulate(A))
  rec = [0] * K
  rec[0] = 1
  
  ans = 0
  for j, S_j in enumerate(S[1:], start=1):
    d = (S_j - j) % K
    ans += rec[d]
    rec[d] += 1
    i = j - K + 1
    if i >= 0:
      d = (S[i] - i) % K
      rec[d] -= 1
  
  print(ans)

solve()

Submission status: Runtime Error

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())
  A = (a % K for a in A)
  S = [0] + list(accumulate(A))
  rec = [0] * K
  rec[0] = 1
  
  ans = 0
  for j, S_j in enumerate(S[1:], start=1):
    d = (S_j - j) % K
    ans += rec[d]
    rec[d] += 1
    i = j - K + 1
    if i >= 0:
      d = (S[i] - i) % K
      rec[d] -= 1
  
  print(ans)

solve()

Submission status: Runtime Error

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 = [0] * (N + 1)
  rec = dict(zip(range(K), [0] * K))
  rec[0] = 1
  
  ans = 0
  for j, a in enumerate(A, start=1):
    S[j] = (S[j-1] + a) % K
    d = (S[j] - j) % K
    ans += rec[d]
    rec[d] += 1
    i = j - K + 1
    if i >= 0:
      d = (S[i] - i) % K
      rec[d] -= 1
  
  print(ans)

solve()

Submission status: Runtime Error

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())
  A = (a % K for a in A)
  S = [0] + list(accumulate(A))
  rec = dict(zip(range(K), [0] * K))
  rec[0] = 1
  
  ans = 0
  for j in range(1, N + 1):
    d = (S[j] - j) % K
    ans += rec[d]
    rec[d] += 1
    i = j - K + 1
    if i >= 0:
      d = (S[i] - i) % K
      rec[d] -= 1
  
  print(ans)

solve()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from bisect import bisect_left
N, K = map(int, input().split())
a = [int(c)-1 for c in input().split()]
s = [0]
for i in range(N):
  s += [(s[-1]+a[i])%K]
dic = defaultdict(list)

for i in range(N+1):
  dic[s[i]] += [i]

ans = 0
for k in dic.keys():
  ls = dic[k]
  for j in range(len(ls)):
    ind = bisect_left(ls, ls[j]-K+2)
    ans += j-ind
    if ind>0 and ls[ind-1]+1 == ls[ind]:
      ans += 1
    elif ind<ls[0]:
      ans += 1
#  print(k, ans)

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from bisect import bisect_left
N, K = map(int, input().split())
a = [int(c)-1 for c in input().split()]
s = [0]
for i in range(N):
  s += [(s[-1]+a[i])%K]
dic = defaultdict(list)

for i in range(N+1):
  dic[s[i]] += [i]

ans = 0
for k in dic.keys():
  ls = dic[k]
  for j in range(len(ls)):
    ind = bisect_left(ls, ls[j]-K+2)
    ans += j-ind
    if ind>0 and ls[ind-1]+1 == ls[ind]:
      ans += 1
#  print(k, ans)

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from bisect import bisect_left
N, K = map(int, input().split())
a = [int(c)-1 for c in input().split()]
s = [0]
for i in range(N):
  s += [(s[-1]+a[i])%K]
dic = defaultdict(list)

for i in range(N+1):
  dic[s[i]] += [i]

ans = 0
for k in dic.keys():
  ls = dic[k]
  for j in range(len(ls)):
    ind = bisect_left(ls, ls[j]-K+2)
    ans += j-ind
    if ind!=0 and ls[ind-1]+1 == ls[ind]:
      ans += 1
#  print(k, ans)

print(ans)

Submission status: Runtime Error

Solution code:
import queue

N, K = map(int, input().split())
A = [int(x) - 1 for x in input().split()]

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

mp = [0] * K
ans = 0
for j in range(N):
    if j < K - 1:
        if S[j] == 0:
            ans += 1
    ans += mp[S[j]]
    mp[S[j]] += 1
    if j >= K - 1:
        mp[S[j-K+1]] -= 1
print(ans)

Submission status: Runtime Error

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))]
    print(ls)

    d = collections.defaultls):
        t += d[x]
        d[x] += 1
        if i >= k - 1:
            d[ls[i - k + 1]] -= 1
    print(t)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, input().rstrip('\n').split()))
    ls = list(map(lambda x: int(x) % k, input().rstrip('\n').split()))
    cnt = 0
    print(ls)
    for i in range(min(n, k)):
        t = sum(ls[:i+1])
        if t % k == i + 1:
            cnt += 1
            print(i, j)
        for j in range(i+1, n):
            t -= ls[j-i-1]
            t += ls[j]
            if t % k == i + 1:
                cnt += 1
                print(i, j)
            elif t % k > k:
                break
    print(cnt)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

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

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

B = {}
count = 0
for i , d in enumerate(b):
    if i > k:
        B[b[i-k]] -= 1
        
    if d in B:
        count += B[d]
        B[d] += 1
    else:
        B[d] = 1
        
print(count)

Submission status: Runtime Error

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)
    *A,=accumulate(A)
    for i,a in enumerate(A):
        A[i] = a%K
    for i in range(K-1):
        ans += before[A[i]]
        before[A[i]] += 1
    for i in range(K-1,N):
        before[A[i-K]]-=1
        ans += before[A[i]]
        before[A[i]]+=1
    ans += A.count(0)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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 = [0]*K

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: Runtime Error

Solution code:
aa = list(map(int,input().split()))
k = aa[1]
a = list(map(int,input().split()))
#print(a)
res = []

def dfs(a,k,res,index,temp):
    if temp:
        if sum(temp) % k == len(temp):
            #print('?')
            #print(temp)
            res.append(1)
            if len(temp) == len(a):
                return
    for i in range(index,len(a)):
        dfs(a,k,res,i+1, temp+[a[i]])
dfs(a,k,res,0,[])
 
   
print(len(res))

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(lambda x:(int(x)-1)%k,input().split()))
s=[0,0]
#print(a)
for i in a:
    s.append((s[-1]+i)%k)
s.append(s[-1])
#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 i>0:
        if s[i-1] in mp:
            mp[s[i-1]]+=1
        else:
            mp[s[i-1]]=1
    #print(i,ans)
print(ans)

Submission status: Runtime Error

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.copy()
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: Runtime Error

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(K-1):
  if A[i]==0:
    out+=1
    
for i in range(1,K-1):
  if A[i] in hm:
    hm[A[i]]+=1
  else:
    hm[A[i]]=1
  out += hm[A[i]]-1
  
for i in range(K-1,N):
  if A[i] in hm:
    hm[A[i]]+=1
  else:
    hm[A[i]]=1
  hm[A[i-K+1]] -= 1
  out += hm[A[i]]-1

print(int(out))

Submission status: Runtime Error

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 = {}
for i in range(min(k, n)):
    if ruiseki[i] not in memo:
        memo[ruiseki[i]] = 1
    else:
        memo[ruiseki[i]] += 1

ans = 0
for i in range(n+1):
    tmp = memo[ruiseki[i]]
    ans += tmp - 1
    memo[ruiseki[i]] -= 1
    if i+k < n+1:
        if ruiseki[i+k] not in memo:
            memo[ruiseki[i+k]] = 1
        else:
            memo[ruiseki[i+k]] += 1
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from collections import Counter
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):
        s+=a
        cs[i]=(s-i)%k
    #print(cs)
    cnt=[0]*k
    for a in cs[:k]:
        cnt[a]+=1
    ans=0
    for l,a in enumerate(cs):
        cnt[a]-=1
        ans+=cnt[a]
        if l+k<=n:cnt[cs[l+k]]+=1
    print(ans)

main()

Submission status: Runtime Error

Solution code:
import numpy as np

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

count = [0] * K
ans = 0

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

print(ans)

Submission status: Runtime Error

Solution code:
d = {}
S = []
N,K = map(int,input().split())
A = list(map(int,input().split()))
s = 0
for i in range(1,N+1):
    s = (s+A[i-1])%K
    k = (s-i)%K
    if k not in S:
        S.append(k)
        d[k] = 0
    d[k] += 1
ans = 0
for i in range(len(S)):
    x = S[i]
    y = d[x]
    ans += (y*(y-1))//2
ans += d[0]
print(ans)

Submission status: Runtime Error

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

L = [-1] * N
D = [0] * K
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
  D[t] += 1
  L[i] = t

n = 1
ans = D[n]
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
    D[t] += 1
    L[i + K - 1] = t
  n = (n - 1 + A[i]) % K
  #n -= 1
  if n < 0:
    n += K
  ans += D[n]
  
print(ans)

Submission status: Runtime Error

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
tbl = [0] * K
for i in range(min(K,N+1)):
    tbl[B[i]] += 1
    ans += tbl[B[i]] - 1
for i in range(K, N+1):
    tbl[B[i-K]] -= 1
    tbl[B[i]] += 1
    ans += tbl[B[i]] - 1
print(ans)

Submission status: Runtime Error

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

import numpy as np

res=[0]*(N+1)
res[1] = A[0]
for i in range(0,len(A)):
    res[i+1] = (res[i] + A[i])%K

array=np.array(res)
ans=0

for i in range(1,N):
    ans+=((array-shift(array,i,cval=0))%K==i).sum()
print(ans)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
ans=[0]*(10**9+1)

A=list(map(int,input().split()))
A=[A[j]%K for j in range(N)]
ans[1] = A.count(1)

B=[(A[j]+A[j+1])%K for j in range(N-1)]
ans[2] = B.count(2)

for i in range(2,min(K+1,N)):
    C = [(B[j]+B[j+1]-A[j+1])%K for j in range(N-i)]
    ans[i+1] = C.count(i+1)
    A = B
    B = C
    
print(sum(ans))

Submission status: Runtime Error

Solution code:
import numpy as np
N, K = map(int, input().split())
A = [0]
B = [int(x) for x in input().split()]
for x in B:
    A.append(x)
cumsum = np.cumsum(np.array(A))%K
c = 0
for n in range(N+1):
    for m in range(n+1, n+1+K):
        if (cumsum[m]-cumsum[n])%K == m-n:
            c += 1
print(c)

Submission status: Runtime Error

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
tbl = [0] * K
for i in range(K):
    tbl[B[i]] += 1
    ans += tbl[B[i]] - 1
for i in range(K, N+1):
    tbl[B[i-K]] -= 1
    tbl[B[i]] += 1
    ans += tbl[B[i]] - 1
print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, K = inpl()
A = inpl()
C = [[] for _ in range(K)]
m = 0
C[0].append(-1)
for i in range(N):
    m = (m + A[i] - 1) % K
    C[m].append(i)

ans = 0
for k in range(K):
    L = len(C[k])
    if L <= 1:
        continue
    l = r = 0
    while r < L:
        r = bisect_left(C[k], C[k][l]+K-1, l)
        if r == L:
            ans += (L-l)*(L-l-1)//2
        else:
            ans += r - l - 1
            if C[k][r] == C[k][l]+K-1:
                ans += 1
            l += 1
print(ans)

Submission status: Runtime Error

Solution code:
#import sys
#input = sys.stdin.readline
def main():
    N, K = map( int, input().split())
    A = list( map( int, input().split()));
    M = [0]*N
    Mod = [0]*K
    Mod[0] = 1
    now = 0
    ans = 0
    for i in range(N):
        if i == K-1:
            Mod[0] -= 1
        if i >= K-1:
            Mod[M[i-(K-1)]] -= 1
        #     print("aa", i-K, M[i-K])
        # print(Mod, M)
        now = (now + A[i] - 1)%K
        M[i] = now
        ans += Mod[now]
        Mod[now] += 1
        # print(i, ans)

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

Submission status: Runtime Error

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

counts = [0] * K
counts2 = [0] * K

cumAm1 = [1] 
for i, Ai in enumerate(A):
    cumAm1.append((-1 + cumAm1[-1] + Ai) % K)

for i in range(N + 1):
    if i >= K:
        counts[cumAm1[i - K]] -= 1

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

    counts[cur] += 1

print(sum(counts2))

Submission status: Runtime Error

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
mk = min(K,N+1)
qs = [deque() for i in range(mk)]

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

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=0
for l in range(1,len(a)):
    for i in range(len(a)-l+1):
        print(a[i:i+l])
        if sum(a[i:i+l])%k==l:
            ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
N, K = list(map(int, input().split()))
An = list(map(int, input().split()))
An = [elem%K for elem in An]
count = 0
for i in range(len(An)):
    for k in range(1,K):
        if i - j == sum(An[i:i+k])%K:
            count += 1
print(count)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
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=[0]*k
for i in r:
    p[i]+=1
ans=0
for i in p:
    ans+=i*(i-1)//2
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter
input = sys.stdin.readline
INF = 10**9

n, k = [int(item) for item in input().split()]
a = [int(item) - 1 for item in input().split()]
cumsum = [0] * (n + 1)
for i in range(n):
    cumsum[i+1] = cumsum[i] + a[i]
    cumsum[i+1] %= k

ls = list(set(cumsum))
dic = dict()
for i, item in enumerate(ls):
    dic[item] = i

cnt = [0] * n
num = 0
ans = 0
for i, item in enumerate(cumsum):
    index = dic[item]
    ans += cnt[index]
    cnt[index] += 1
    num += 1
    if num >= k:
        left = cumsum[i - k + 1]
        index = dic[left]
        if cnt[index] > 0:
            cnt[index] -= 1
        num -= 1

print(ans)

Submission status: Runtime Error

Solution code:
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 = [0] * K
counts2 = [0] * K
for i in range(N + 1):

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

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

    counts[cur] += 1

print(sum(counts2))

Submission status: Runtime Error

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

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

counts = [0] * K
counts2 = [0] * K
for i in range(N + 1):

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

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

    counts[cur] += 1

print(sum(counts2))

Submission status: Runtime Error

Solution code:
N, K = list(map(int, input().split()))
An = list(map(int, input().split()))
An = [elem%K for elem in An]
count = 0
for i in range(len(An)-1):
    for k in range(1,K):
        if i - j == sum(An[i:i+k])%K:
            count += 1
print(count)

Submission status: Runtime Error

Solution code:
import bisect

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

memo = {}
for i in range(n):
  if a[i] % k not in memo.keys():
    memo[a[i] % k] = [i]
  else:
    memo[a[i] % k].append(i)

ans = bisect.bisect_left(memo[0], k - 1)

for i in memo.keys():
  for j in range(len(memo[i]) - 1):
    ans += bisect.bisect_left(memo[i], memo[i][j] + k) - 1 - j

print(ans)

Submission status: Runtime Error

Solution code:
N,K = nums()
A = nums()
cursor = 0
ans = 0
def cond(bubun_):
    global K
    return (sum(bubun_) % K) == len(bubun_)
for i in range(N):
    for j in range(N):
        if cursor + j > N:break
        bubun = A[cursor:cursor+j]
        if cond(bubun) and len(bubun):
            ans += 1
    cursor += 1
print(ans)

Submission status: Runtime Error

Solution code:
N, K = list(map(int, input().split()))
An = list(map(int, input().split()))
An = [elem%K for elem in An]
count = 0
for i in range(len(An)-1):
    if i - j == sum(An[i:i+K])%K:
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
import numpy as np

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

# N = 2 * 10 ** 5
# A = [10 ** 9 for i in range(N)]


cumAm1 = np.cumsum(np.array([1] + A) % K - 1) % K

counts = [0] * K
counts2 = [0] * K
for i in range(N + 1):

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

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

    counts[cur] += 1

print(sum(counts2))

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
n,k = map(int,input().split( ))
a = list(map(int, input().split( )))
ans = 0
for i in range(n):
    #if a[i]%k==1:
    #    ans+=1
    a[i] -= 1
sm= 0
a_sm = [0]
for i in range(n):
    sm += a[i]
    sm%=k
    a_sm.append(sm)
#print(a_sm)
dic = {i:[] for i in range(n)}
for i in range(n+1):
    dic[a_sm[i]].append(i)
#print(dic)
for i in range(n):
    for j in range(len(dic[i])-1):
        dm = bisect_left(dic[i],dic[i][j]+k)
        #print(ans)
        #print(i,j,dm)
        ans += dm - j-1
        #print("test",ans)
       
print(ans)

Submission status: Runtime Error

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

cumAm1 = np.cumsum(np.array([1] + A) - 1)
cumAm1 %= K

counts = np.zeros(K, dtype=int)
counts2 = np.zeros(K, dtype=int)
for i in range(N + 1):

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

    counts2[cumAm1[i]] += counts[cumAm1[i]]

    counts[cumAm1[i]] += 1

print(counts2.sum())

Submission status: Runtime Error

Solution code:
A, B, X = map(int, input().split())

num = min(10**9, X // A, 10 ** (X // B))


while num > 0:
    if A * num + B * len(str(num)) <= X:
        break
    else:    
        num -= 1
    
print(num)