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 collections
n,k  = map(int,raw_input().split(' '))
elems = map(int ,raw_input().split(' '))

res, cumul,cc = 0,0,collections.Counter()

q = collections.deque()
for j,e in enumerate(elems):
	cumul += e
	res += cc[(cumul - j) % k]
	if cumul % k == j + 1 and j + 1 < k: res += 1
	cc[(cumul -j) % k] += 1
	
	if len(q) == k - 1:
		u = q.popleft()
		cc[u] -=1
	q.append((cumul -j ) % k)
	
print res

Submission status: Runtime Error

Solution code:
import sys

input = lambda: sys.stdin.readline().rstrip()


def comb(n, k):

    if n < k:
        return 0

    m = 1
    for i in range(n, n - k, -1):
        m = m * i

    n = 1
    for i in range(1, k + 1):
        n = n * i

    return (m // n)


def solve():

    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    S = [0 for _ in range(N + 1)]

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

    if N < K:
        d = dict()
        for i in range(N + 1):
            k = S[i] % K
            if d[k]:
                d[k] += 1
            else:
                d[k] = 1

        ans = 0
        for k, v in d.items():
            ans += comb(v, 2)

        print(ans)
        exit()

    elif N >= K:

        ans = 0
        d = dict()

        # first
        kf = S[0] % K
        for i in range(K):
            k = S[i] % K
            if k in d:
                d[k] += 1
            else:
                d[k] = 1

        for k, v in d.items():
            ans += comb(v, 2)

        # slide
        for i in range(1, N + 1 - K):
            d[kf] -= 1
            kf = S[i] % K
            k = S[i + K] % K
            if k in d:
                ans += d[k]
                d[k] += 1
            else:
                d[k] = 1

    print(ans)
    exit()


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

Submission status: Runtime Error

Solution code:
#標準入力からKを求めるまで
N = int(input())
node = [0] * N
AB = []
for i in range(N-1):
    ab = list(map(int, input().split()))
    node[ab[0] - 1] += 1
    node[ab[1] - 1] += 1
    AB.append(ab)
K = max(node)
print(K)

#各辺の色を求めていく
color = [[ i for i in range(1, K + 1)] for i in range(N)]
for i in range(N-1):
    now = list(set(color[AB[i][0]-1]) & set(color[AB[i][1] - 1]))
    tmp = now[0]
    color[AB[i][0]-1].remove(tmp)
    color[AB[i][1]-1].remove(tmp)
    print(tmp)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * (n + 1)
for i in range(1, n + 1):
    b[i] = b[i - 1] + a[i - 1]
for i in range(n + 1):
    b[i] -= i
    b[i] %= k
d = dict()
for i in range(k):
    if b[i] in d:
        d[b[i]] += 1
    else:
        d[b[i]] = 1
ans = []
j = k
for i in range(n):
    ans.append(d[b[i]])
    d[b[i]] -= 1
    if j <= n:
        if b[j] in d:
            d[b[j]] += 1
        else:
            d[b[j]] = 1
    j += 1
ans = sum(ans) - n
print(ans)

Submission status: Runtime Error

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


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

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

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

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

d = defaultdict(int)

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

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

print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter, deque

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
S = [0] * (N+1)
T = [0] * (N+1)
for i in range(N):
    S[i+1] = (S[i] + A[i])%K
    T[i+1] = (S[i+1] - (i+1))%K
rest = [0] * K
for i in range(N+1):
    if i < K:
        ans += rest[T[i]]
        rest[T[i]] += 1
    else:
        rest[T[i-K]] -= 1
        ans += rest[T[i]]
        rest[T[i]] += 1
print(ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
S = [0] * (N+1)
T = [0] * (N+1)
for i in range(N):
    S[i+1] = (S[i] + A[i])%K
    T[i+1] = (S[i+1] - (i+1))%K
rest = [0] * K
if N+1 >= K:
    for i in range(K):
        rest[T[i]] += 1
    for i in range(N-K+1):
        rest[T[i]] -= 1
        ans += rest[T[i]]
        rest[T[i+K]] += 1
    for i in range(N-K+1, N+1):
        rest[T[i]] -= 1
        ans += rest[T[i]]
else:
    for i in range(N+1):
        rest[T[i]] += 1
    for i in range(N+1):
        rest[T[i]] -= 1
        ans += rest[T[i]]
print(ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
S = [0] * (N+1)
T = [0] * (N+1)
for i in range(N):
    S[i+1] = (S[i] + A[i])%K
    T[i+1] = (S[i+1] - (i+1))%K
rest = [0] * K
for i in range(K):
    rest[T[i]] += 1 
for i in range(N-K+1):
    rest[T[i]] -= 1
    ans += rest[T[i]]
    rest[T[i+K]] += 1
for i in range(N-K+1, N+1):
    rest[T[i]] -= 1
    ans += rest[T[i]]
print(ans)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
l = list(map(int,input().split()))
mo = [0]
mod = [0]
for i in range(n):
    a = l[i]%k
    mo.append((a+mo[-1])%k)
    mod.append((mo[-1]-(i+1))%k)
dic = {0:1}
le = 1
ans = 0
for i in range(1,n+1):
    if le < k:
        if mod[i] in dic:
            ans += dic[mod[i]]
            dic[mod[i]] += 1
        else:
            dic[mod[i]] = 1
        le += 1
    else:
        dic[mod[i-k]] -= 1
        if mod[i] in dic:
            ans += dic[mod[i]]
            dic[mod[i]] += 1
        else:
            dic[mod[i]] = 1
    print(dic)
print(ans)

Submission status: Runtime Error

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

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

ans, trg = 0, 0
for i in range(N):
	ans += cnt[trg]
	cnt[asm[i]] -= 1
	if i + K - 1 < N:
		cnt[asm[i + K - 1]] += 1
	trg += (A[i] - 1)
	trg %= K

print(ans)

Submission status: Runtime Error

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

cnt = 0
dic = {}

for i, s in enumerate(S):
    x = (s - i) % K

    if x in dic:
        cnt += dic[x]
        dic[x] += 1
    else:
        dic[x] = 1

    K_prev = i - K + 1

    if K_prev >= 0:
        y = (S[K_prev] - (K_prev)) % K
        dic[y] -= 1


print(cnt)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from collections import defaultdict

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = np.array([0] + lr())
A = (A-1) % K
Acum = A.cumsum()
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)



for i in range(len(Acum)):
    x = Acum(i)
    answer += counter[x]
    counter[x] += 1
    if i >= K-1:
        counter[Acum[i-(K-1)]] -= 1

print(answer)
# 27

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from collections import defaultdict

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = np.array([0] + lr())
A = (A-1) % K
Acum = A.cumsum()
counter = defaultdict()
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: Runtime Error

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

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

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

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

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

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

print(res)

Submission status: Runtime Error

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

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

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

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

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

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

print(res)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * (n + 1)
for i in range(n):
    S[i+1] = S[i] + A[i]

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

Submission status: Runtime Error

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

C = [0] * k
ans = 0
for i in range(n+1):
    j = i - k
    mi = (S[i] - i) % k
    if j >= 0:
        mj = (S[j] - j) % k
        C[mj] -= 1
    ans += C[mi]
    C[mi] += 1
print(ans)

Submission status: Runtime Error

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

C = [0] * k
ans = 0
for i in range(n+1):
    j = i - k
    mi = (S[i] - i) % k
    mj = (S[j] - j) % k
    if j >= 0:
        C[mj] -= 1
    ans += C[mi]
    C[mi] += 1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

n, k = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * (n + 1)
for i in range(n):
    S[i+1] = S[i] + A[i]

C = defaultdict(int)
ans = 0
for i in range(n+1):
    j = i - k
    mi = (S[i] - i) % k
    mj = (S[j] - j) % k
    if j >= 0:
        C[mj] -= 1
    ans += C[mi]
    C[mi] += 1

Submission status: Runtime Error

Solution code:
import numpy as np

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

ans = 0
accum = np.array([], dtype=int)
for i, a in enumerate(A):
  accum += a
  accum = np.r_[accum, a]
  ans += sum((accum % K) == np.arange(i+1, 0, -1))

print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def rem_of_sum(n, k, arr):
    count = 0
    for i in range(n):
        for j in range(i + 1, min(n + 1, i + k)):
            part = arr[i:j]
            if sum(part) % k == len(part):
                count += 1
    return count


n, k = map(int, input().split())
arr = list(map(input().split()))
print(rem_of_sum(n, k, arr))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

D = {}
s = 0
t = 0
ans = 0
for i in range(N+1):
    s = B[i]
    if s in D:
        ans += D[s]
        D[s] += 1
    else:
        D[s] = 1
    if i >= K - 2:
        t = B[i-K+2]
        D[t] -= 1
print(ans)

Submission status: Runtime Error

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

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

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

print(ans)

Submission status: Runtime Error

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

ans = 0
#s = []
b = []
temp = 0
for i, x in enumerate(a):
    temp = (temp + x) % k
    c = (temp - (i % k) + k) % k
    b.append(c)
    #if x % k == 1:
    #    ans += 1

#print(s)
#print(b)

m = [0] * k

for i in range(min(k, n+1)):
    ans += m[b[i]]
    m[b[i]] += 1

#print(m)

for i in range(k, n+1):
    m[b[i-k]] -= 1
    ans += m[b[i]]
    m[b[i]] += 1
    #print(m)

print(ans)

Submission status: Runtime Error

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

ans = 0
#s = []
b = []
temp = 0
for i, x in enumerate(a):
    temp = (temp + x) % k
    c = (temp - (i % k) + k) % k
    b.append(c)
    #if x % k == 1:
    #    ans += 1

#print(s)
#print(b)

m = [0] * k

for i in range(k):
    ans += m[b[i]]
    m[b[i]] += 1

#print(m)

for i in range(k, n+1):
    m[b[i-k]] -= 1
    ans += m[b[i]]
    m[b[i]] += 1
    #print(m)

print(ans)

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<cstdlib>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
#include<cmath>
#include<iomanip>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int i(0);i<n;i++)
const int INF = 1001001001;

int main(){
	ll n,k;
	cin >> n >> k;
	vector<ll> a(n,0);
	rep(i,n){
		cin >> a[i];
	}

	ll ans(0);

	for(ll i(0);i<n;i++){
		ll sum(a[i]);
		if(sum%k == 1)ans++;
		for(ll j(i+1);j<n;j++){
			sum+=a[j];
			if(sum%k == j-i+1)ans++;
		}
	}
	cout << ans << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<cstdlib>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
#include<cmath>
#include<iomanip>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int i(0);i<n;i++)
const int INF = 1001001001;

int main(){
	ll n,k;
	cin >> n >> k;
	vector<ll> a(n,0);
	rep(i,n){
		cin >> a[i];
	}

	ll ans(0);

	for(ll i(0);i<n;i++){
		ll sum(a[i]);
		if(sum%k == 1){
			ans++;
			//printf("i=%lld\n",i);
		}
		for(ll j(i+1);j<n;j++){
			sum+=a[j];
			if(sum%k == j-i+1){
				ans++;
				//printf("i,j=%lld,%lld\n",i,j);
			}
		}
	}
	cout << ans << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
def main():
    N, K = map(int, input().split())
    A = tuple(map(int, input().split()))
    d = {}
    d2 = {}
    d[0] = [0]
    s = 0
    for i in range(1, N+1):
        s = (s + A[i-1]) % K
        t = (s-i) % K
        if t in d:
            d[t].append(i)
        else:
            d[t] = [i]
        d2[i] = t
    a = 0
    x = [0] * K
    for i in range(1, N+1):
        for j, v in enumerate(d[d2[i]][x[d2[i]]:]):
            if i - K < v and v < i:
                a += 1
            elif v >= i:
                break
            else:
                x[d2[i]] = j
    return a

print(main())

Submission status: Runtime Error

Solution code:
def main():
    N, K = map(int, input().split())
    A = tuple(map(int, input().split()))
    d = {}
    d2 = {}
    d[0] = [0]
    s = 0
    for i in range(1, N+1):
        s = (s + A[i-1]) % K
        t = (s-i) % K
        if t in d:
            d[t].append(i)
        else:
            d[t] = [i]
        d2[i] = t
    a = 0
    x = [0] * K
    for i in range(1, N+1):
        t = d[d2[i]]
        for j in t[x[d2[i]]:]:
            if i - K < j and j < i:
                a += 1
            elif j >= i:
                break
            else:
                x[d2[i]] = j

    return a

print(main())

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
import queue
import bisect

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

def solve(N, K, A):
    S = [0 for _ in range(N+1)]
    T = [0 for _ in range(N+1)]
    # (S[j] - S[i]) % K == j - i
    # (S[j] - j) % K == (S[i] - i) % K and 0 <= (j - i) < K
    # 1 <= j <= N に対して、(S[j] - j) % K == (S[i] - i) % K　を満たす (j - K) < i < j の個数を調べたい
    # j = kのとき i の調べる区間は (k - K) < i < k　つまり C[k] = sum(C[k-K+1], ... , C[k-1])
    # j = k+1のとき i の調べる区間は (k+1 - K) < i < k+1 つまり C[k+1] = sum(C[k-K+2], ... , C[k])
    # j = k+1 では、j = k の結果を用いて C[k+1] = C[k] - C[k-K+1] + C[k]
    for i in range(N):
        S[i+1] = S[i] + A[i]
    
    count_sum = 0
    count = dict()
    for j in range(1, N+1):
        j_mod_k = (S[j] - j) % K  # 0 <= jmodk < K
        if j == 1:
            for i in range(max(0, j-K+1), j):
                # (S[i] - i) % K の値 i_mod_k は、次のループでもほとんど同じ値が使われることに注意
                # i = max(0, j-K+1) の時の i_mod_k は、i+1で破棄する
                # i = j の時の i_mod_k は、i+1で生成する
                i_mod_k = (S[i] - i) % K
                if i_mod_k in count:
                    count[i_mod_k] += 1
                else:
                    count[i_mod_k] = 1
        else:
            # for i in range(j-K+1, j)
            if max(0, j-K+1) != max(0, (j-1)-K+1):
                i = max(0, (j-1)-K+1)
                i_mod_k = (S[i] - i) % K
                if count[i_mod_k] == 1:
                    count.pop(i_mod_k)
                else:
                    count[i_mod_k] -= 1
            i = j-1
            i_mod_k = (S[i] - i) % K
            if i_mod_k in count:
                count[i_mod_k] += 1
            else:
                count[i_mod_k] = 1
        count_sum += count[j_mod_k] if j_mod_k in count else 0
    return count_sum

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

Submission status: Runtime Error

Solution code:
from itertools import accumulate
from collections import defaultdict

N,K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
A = [0]+[i-1 for i in A]
sumA = list(accumulate(A))
sumA = [i % K for i in sumA]
x = sumA[:K]
modmap = [0]*K
ans = 0
for i in x:
    modmap[i] += 1

for i in range(K):
    t = modmap[i]
    ans += t * (t-1) // 2

for i in range(N-K+1):
    modmap[sumA[K+i]] += 1
    modmap[sumA[i]] -= 1
    ans += modmap[sumA[K+i]]-1

print(ans)

Submission status: Runtime Error

Solution code:
from itertools import accumulate
from collections import defaultdict

N,K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
A = [0]+[i-1 for i in A]
sumA = list(accumulate(A))
sumA = [i % K for i in sumA]
x = sumA[:K]
modmap = [0]*N
ans = 0
for i in x:
    modmap[i] += 1

for i in range(K):
    t = modmap[i]
    ans += t * (t-1) // 2

for i in range(N-K+1):
    modmap[sumA[K+i]] += 1
    modmap[sumA[i]] -= 1
    ans += modmap[sumA[K+i]]-1

print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 9)

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, K = rl()
A = np.array([0] + rl())
A_cum = A.cumsum()
A_cum2 = A_cum - np.arange(N+1)
A_cum2 = A_cum2 % K
answer = 0
remain = [0] * (K)
cnt = 0
for i in range(N+1):
    x = A_cum2[i] % K    
    if i - K >= 0:
        y = A_cum2[i-K] % K
        remain[y] -= 1
    answer += remain[x]
    remain[x] += 1
print(answer)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, K = rl()
A = np.array([0] + rl())
A_cum = A.cumsum()
A_cum2 = A_cum - np.arange(N+1)
A_cum2 = A_cum2 % K
answer = 0
remain = [0] * (K)
cnt = 0
for i in range(N+1):
    x = A_cum2[i] % K    
    if i - K >= 0:
        y = A_cum2[i-K] % K
        remain[y] -= 1
    answer += remain[x]
    remain[x] += 1
print(answer)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, K = rl()
A = np.array([0] + rl())
A_cum = A.cumsum()
A_cum2 = A_cum - np.arange(N+1)
A_cum2 = A_cum2 % K
answer = 0
remain = [0] * (K)
cnt = 0
for i in range(N+1):
    x = A_cum2[i] % K    
    if i - K >= 0:
        y = A_cum2[i-K] % K
        remain[y] -= 1
    answer += remain[x]
    remain[x] += 1
print(answer)

Submission status: Runtime Error

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

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

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

cnt = [0]*k
left = 0
right = k-1
if right > n:
    right = n

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

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

print(ans)

Submission status: Runtime Error

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

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

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

cnt = [0]*k
left = 0
right = k-1
if right >= n:
    right = n-1

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

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

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque


def p_e():
    n, k = map(int, input().split())
    *a, = map(int, input().split())
    s = [0] * (n + 1)
    for i in range(n):
        s[i + 1] = (s[i] + a[i] - 1) % k
    mp = [0] * k
    q = deque()
    ans = 0
    for i in range(n + 1):
        ans += mp[s[i]]
        mp[s[i]] += 1
        q.append(s[i])
        if len(q) == k:
            mp[q.popleft()] -= 1
    print(ans)
    
p_e()

Submission status: Runtime Error

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

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

Solution code:
from itertools import accumulate
from math import factorial as fc

def cmb_2(n):
    return n*(n-1)//2

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

sumA = list(accumulate(A))
sumA = [0]+[i % K for i in sumA]
x = sumA[:K]
modmap = [0]*K
for i in x:
    modmap[i] += 1

ans = 0
for i in range(K):
    ans += cmb_2(modmap[i])

for i in range(N-K+1):
    modmap[sumA[K+i]] += 1
    modmap[sumA[i]] -= 1
    ans += modmap[sumA[K+i]]-1

print(ans)

Submission status: Runtime Error

Solution code:
from itertools import accumulate
from math import factorial as fc

def cmb_2(n):
    return n*(n-1)//2

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

sumA = list(accumulate(A))
sumA = [0]+[i % K for i in sumA]
x = sumA[:K]
modmap = [0]*K
for i in x:
    modmap[i] += 1

ans = 0
for i in range(K):
    ans += cmb_2(modmap[i],2)

for i in range(N-K+1):
    modmap[sumA[K+i]] += 1
    modmap[sumA[i]] -= 1
    ans += modmap[sumA[K+i]]-1

print(ans)

Submission status: Runtime Error

Solution code:
from itertools import accumulate
from math import factorial as fc

def cmb(n,r):
    if n < 0 or r < 0 or n-r < 0:
        return 0
    return fc(n)//(fc(n-r)*fc(r))

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

sumA = list(accumulate(A))
sumA = [0]+[i % K for i in sumA]
x = sumA[:K]
modmap = [0]*K
for i in x:
    modmap[i] += 1

ans = 0
for i in range(K):
    ans += cmb(modmap[i],2)

for i in range(N-K+1):
    modmap[sumA[K+i]] += 1
    modmap[sumA[i]] -= 1
    ans += modmap[sumA[K+i]]-1

print(ans)