Problem:


Score : 500 points

Problem Statement

Given are a sequence of N positive integers A_1, A_2, \ldots, A_N, and a positive integer K.

Find the number of non-empty contiguous subsequences in A such that the remainder when dividing the sum of its elements by K is equal to the number of its elements. We consider two subsequences different if they are taken from different positions, even if they are equal sequences.

Constraints

All values in input are integers.

1 \leq N \leq 2\times 10^5

1 \leq K \leq 10^9

1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \cdots A_N

Output

Print the number of subsequences that satisfy the condition.

Sample Input 1

5 4
1 4 2 3 5

Sample Output 1

4

Four sequences satisfy the condition: (1), (4,2), (1,4,2), and (5).

Sample Input 2

8 4
4 2 4 2 4 2 4 2

Sample Output 2

7

(4,2) is counted four times, and (2,4) is counted three times.

Sample Input 3

10 7
14 15 92 65 35 89 79 32 38 46

Sample Output 3

8



Sample input:
5 4
1 4 2 3 5


Sample output:
4

Submission status: Accepted

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


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


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



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


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



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


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

Submission status: Accepted

Solution code:
import itertools, collections
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
C = list(itertools.accumulate([0] + A))
D = [(v - i) % K for i, v in enumerate(C)]
#D[i]==D[j] and i-j<K
dp = collections.Counter(D[:K])
ans = 0
for i in range(N):
    dp[D[i]] -= 1
    ans += dp[D[i]]
    if i + K < len(D):
        dp[D[i + K]] += 1
print(ans)

Submission status: Accepted

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

ans = 0
for k in k_list:
    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: Accepted

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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
r = 0
s = {0: [0]}
for i in range(n):
    r = (r + a[i] - 1) % k
    if r in s:
        s[r].append(i + 1)
    else:
        s[r] = [i + 1]
ret = 0
for key in s:
    a = s[key]
    en = 0
    for st in range(len(a)):
        while en < len(a) and a[en] - a[st] < k:
            en += 1
        ret += en - st - 1
print(ret)

Submission status: Accepted

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

kinds = set(S)
counts = {}
ans = 0
for k in kinds:
	counts[k] = 0
for i in range(N+1):
	counts[S[i]] += 1
	if i >= K:
		counts[S[i-K]] -= 1
	ans += (counts[S[i]] - 1)
print(ans)

Submission status: Accepted

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

ans = 0
for k in d:
    l = d[k]
    for i in range(len(l)):
        n = l[i]
        j = bisect.bisect_left(l,n+K)
        ans += j-i-1
    if k==1:
        j = bisect.bisect_left(l,K-1)
        ans += j
            
print(ans)

Submission status: Accepted

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

s = [0]
for i in range(len(a)):
    s.append(s[-1] + a[i])

ss = []
for i in range(len(s)):
    ss.append((s[i] - i) % k)

# print(ss)

ans = 0
from collections import Counter
c = Counter(ss[1: min(k, len(ss))])
for i in range(len(ss)):
    # print(i, c)
    ans += c[ss[i]]

    if i + 1 < len(ss):
        c[ss[i + 1]] -= 1
    if i + k < len(ss):
        c[ss[i + k]] += 1

print(ans)

Submission status: Accepted

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

def main():
    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)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

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

s = [0]

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

d = defaultdict(int)

ret = 0
for i in range(min(K, N + 1)) :
    ret += d[s[i]]
    d[s[i]] += 1
for i in range(K, N + 1) :
    d[s[i-K]] -= 1
    ret += d[s[i]]
    d[s[i]] += 1

print(ret)

Submission status: Accepted

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 + 10)
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: Accepted

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
s = 0
B = [0]
C = {0:[0]}
for i, a in enumerate(A):
    s = (s+a)%K
    n = (s-i-1)%K
    B.append(n)
    if n not in C: C[n] = []
    C[n].append(i+1)

ans = 0

for k, v in C.items():
    if len(v)<=1: continue
    ans_k = 0
    ir=0
    for il in range(0,len(v)-1):
        l = v[il]
        while(ir<len(v) and v[ir]-l<=K-1): ir+=1
        ans_k+=(ir-1)-il
    ans+=ans_k
print(ans)

Submission status: Accepted

Solution code:
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, K = list(map(int, sys.stdin.buffer.readline().split()))
A = list(map(int, sys.stdin.buffer.readline().split()))

if K == 1:
    print(0)
    exit()
if K == 2:
    ans = sum([1 for a in A if a % 2 == 1], 0)
    # ans = (A % 2 == 1).sum()
    print(ans)
    exit()


def test():
    ans = 0
    for i, a in enumerate(A):
        if a % K == 1:
            ans += 1
        j = 1
        while i - j >= 0 and j + 1 < K:
            if (sum(A[i - j: i]) + a) % K == j + 1:
                ans += 1
            j += 1
    print(ans)


# 和-長さ を覚える
counts = defaultdict(int)
hist = [-1] * N
offset = 0
ans = 0
for i, a in enumerate(A):
    a %= K
    if a == 1:
        ans += 1
    ans += counts[(K - a + 1 - offset) % K]
    offset += a - 1
    offset %= K
    counts[(a - 1 - offset) % K] += 1

    if i - K + 2 >= 0:
        counts[hist[i - K + 2]] -= 1
    hist[i] = (a - 1 - offset) % K
print(ans)

Submission status: Accepted

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 = {0 : []}
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: Accepted

Solution code:
import bisect
n, k = map(int, input().split())
a = [0] + list(map(int, input().split()))
for i in range(n):
    a[i + 1] += a[i]
ans = 0
for i in range(n):
    a[i + 1] -= i + 1
    a[i + 1] %= k
d = dict()
for i, x in enumerate(a):
    if x in d:
        d[x].append(i)
    else:
        d[x] = [i]
ans = 0
for v in d.values():
    for i, x in enumerate(v):
        t = bisect.bisect_right(v, x + k - 1) - i - 1
        ans += t
print(ans)

Submission status: Accepted

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):
    a[i] -= 1
sm= 0
a_sm = [0]
for i in range(n):
    sm += a[i]
    sm%=k
    a_sm.append(sm)

dic = {}
for i in range(n+1):
    if a_sm[i] in dic:
        dic[a_sm[i]].append(i)
    else:
        dic[a_sm[i]]=[i]

for t in dic:
    for j in range(len(dic[t])-1):
        dm = bisect_left(dic[t],dic[t][j]+k)
        ans += dm - j - 1

       
print(ans)

Submission status: Accepted

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

B=[a-1 for a in A]

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

from collections import Counter
C=Counter()

ANS=0
for i in range(N+1):
    ANS+=C[S[i]]
    #print(i,ANS,C)
    C[S[i]]+=1

    if i-K+1>=0:
        C[S[i-K+1]]-=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:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

#n = int(input())
n,k = [int(i) for i in input().split()]
a = [int(i)-1 for i in input().split()]


acc = [0]
for ai in a:
    acc.append((acc[-1]+ai)%k)

#print(acc)
ans = 0
d = {}
for num,i in enumerate(acc):
    #print(d,num)
    if num >= k:
        d[acc[num-k]] -= 1
    #print(d,num)
    if i in d:
        ans += d[i]
        d[i] += 1
    else:
        d[i] = 1
    #print(ans)

print(ans)

Submission status: Accepted

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

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

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

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

    # print (A)

    d = defaultdict(int)

    for i in range(1, min(N + 1, K)):
        d[A[i]] += 1

    ans = 0
    tmp = min(N + 1, K)
    for i in range(N):
        ans += d[A[i]]
        d[A[i + 1]] -= 1
        if tmp <= N:
            d[A[tmp]] += 1
            tmp += 1

    print (ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
from collections import defaultdict

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

A = [(a-1) % K for a in A_raw]
acc = [0] * (N+1)
for i in range(N):
    acc[i+1] = (acc[i] + A[i]) % K

cnt = defaultdict(list)
cnt[0].append(-1)
ans = 0
for i, a in enumerate(acc[1:]):
    if cnt[a]:
        ans += len(cnt[a]) - bisect.bisect_left(cnt[a], i - K+1)
        # print(bisect.bisect_right(cnt[a], i - K+1), i, i-K+2, ans)
        # print(i, len(cnt[a]) - bisect.bisect_left(cnt[a], i - K+1))
    cnt[a].append(i)
# print(cnt)
print(ans)

Submission status: Accepted

Solution code:
import queue
import math
import copy
"""
N = int(input())
#S = input()
# (N,M) = (int(i) for i in input().split(" "))
# A = [int(i) for i in input().split()]
A = []
for i in range(N):
	A.append(int(input()))

print(A)

"""
(N,M) = (int(i) for i in input().split(" "))
A = [int(i)-1 for i in input().split()]

mp={}
mp[0] = 1
hT = [0]
T = 0
ans = 0
for i,a in enumerate(A):
	T += a
	T %= M
	if i>=M-1:
		mp[hT[i-M+1]]-=1
	if T in mp.keys():
		ans += mp[T]
		mp[T] += 1
	else:
		mp[T] = 1
	hT.append(T)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect
n,k = map(int,input().split())
a = list(map(int,input().split()))
aa = [0]
cur = 0
for i in a:
  cur = (cur+i-1) % k
  aa.append(cur)
d = defaultdict(list)
for i in range(n+1):
  d[aa[i]].append(i)
ans = 0
for i in d.values():
  for j in i:
    ans += bisect.bisect_right(i,j+k-1)-bisect.bisect_right(i,j)
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate, chain
from collections import defaultdict

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

A = accumulate(chain((0,),map(lambda x: int(x)-1, input().split())))

d = defaultdict(list)
for i,a in enumerate(A):
    d[a%K].append(i)

cnt = 0
for l in d.values():
    if len(l) == 1:
        continue
    j = 0
    for i,li in enumerate(l):
        li += K
        while j < len(l) and l[j] < li:
            j += 1
        cnt += j-i-1

print(cnt)

Submission status: Accepted

Solution code:

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

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

sa = [0]

for i in range(N):

    if i == 0:
        sa.append(A[0] % K)
    else:
        sa.append((sa[-1] + A[i]) % K)


#print (sa)
nm = 1
for i in range(N):
    i += 1

    if sa[i] < nm:
        sa[i] += K
    sa[i] -= nm
    nm += 1
    nm %= K

#print (sa)

ndic = {}

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

    if sa[i] in ndic:
        ans += ndic[sa[i]]
        ndic[sa[i]] += 1
    else:
        ndic[sa[i]] = 1

    if i - (K-1) >= 0:
        ndic[sa[i-(K-1)]] -= 1

print (ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

n,k = map(int, input().split())
a = list(map(int, input().split()))
if k == 1:
    print(0)
    exit()
s = [0]
for i in a:
    s.append((s[-1]+i-1)%k)

d = defaultdict(int)
d[0] = 1
ans = 0
for r in range(1, n+1):
    sr = s[r]
    if d[sr]>0:
        ans += d[sr]
    d[sr] += 1
    l = r-k+1
    if l >= 0:
        d[s[l]] -= 1
print(ans)

Submission status: Accepted

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

cnt = {0:1}

ans = 0

for i in range(1, n+1):
    left = i - k
    if left >= 0:
        ldif = (a[left] - left) % k
        if ldif < 0: ldif += k
        cnt[ldif] -= 1
    
    a[i] += a[i-1]
    dif = (a[i] - i) % k
    if dif < 0: dif += k
    if dif not in cnt:
        cnt[dif] = 0
        
    ans += cnt[dif]
    cnt[dif] += 1

print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    a = LI()
    s = [0]
    for i in a:
        s.append((s[-1]+i-1)%k)
    ans = 0
    d = defaultdict(lambda : 0)
    for i in range(n+1):
        ans += d[s[i]]
        d[s[i]] += 1
        j = i-k+1
        if j >= 0:
            d[s[j]] -= 1
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]


def bi(x, a):
    mi = 0
    ma = len(x) - 1
    while mi != ma:
        m = (mi + ma) // 2+1
        if x[m] < a:
            mi = m
        else:
            ma = m - 1
    return mi


b = [0]
for i in a:
    b.append(b[-1] + i-1)

c = {}
for l, j in enumerate(b):
    i = j % k
    if i in c:
        c[i].append(l)
    else:
        c[i] = [l]
j = 0
for i in c:
    i = c[i]
    i.sort()
    for m, l in enumerate(i):
        j += bi(i, l+k)-m
print(j)

Submission status: Accepted

Solution code:
from collections import defaultdict


def solve(n, k, a_list):
    b_list = [a - 1 for a in a_list]
    res_dict = defaultdict(list)
    res_dict[0].append(0)

    r = 0
    for i in range(n):
        r += b_list[i]
        r %= k
        res_dict[r].append(i + 1)

    res = 0
    for r in res_dict.keys():
        r_list = res_dict[r]
        if len(r_list) == 1:
            continue
        i = 0
        j = 0
        # print(r_list)
        while i < len(r_list) - 1:
            if j < len(r_list) - 1:
                while r_list[j + 1] - r_list[i] < k:
                    j += 1
                    if j == len(r_list) - 1:
                        break
            res += j - i
            # print(i, j)
            i += 1
    return res


def main():
    n, k = map(int, input().split())
    a_list = list(map(int, input().split()))
    res = solve(n, k, a_list)
    print(res)


def test():
    assert solve(5, 4, [1, 4, 2, 3, 5]) == 4
    assert solve(8, 4, [4, 2, 4, 2, 4, 2, 4, 2]) == 7
    assert solve(10, 7, [14, 15, 92, 65, 35, 89, 79, 32, 38, 46]) == 8


if __name__ == "__main__":
    # test()
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
import bisect
sys.setrecursionlimit(10**9)
N, K = map(int, input().split())
A = list(map(lambda x:int(x)-1, input().split()))
S = [0]*(N+1)
R = defaultdict(list)
R[0].append(0)
for i in range(N):
    S[i+1] = (S[i]+A[i])%K
    R[S[i+1]].append(i+1)
ans = 0
for i in range(N+1):
    a = bisect.bisect_right(R[S[i]], i)
    b = bisect.bisect_left(R[S[i]], i+K)
    ans+=b-a
print(ans)

Submission status: Accepted

Solution code:

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,K = inpl()
AA = inpl()

rAA = [0]
for a in AA:
    rAA.append(rAA[-1]+a)


AA = [(A+N-i)%K for i,A in enumerate(rAA)]


cnts = defaultdict(int)
ans = 0
for i,a in enumerate(AA):
    if i >= K:
        cnts[AA[i-K]] -= 1

    ans += cnts[a]
    cnts[a] += 1



print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, k = na()
a = na()

cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = (cum[i] + a[i] + k - 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 sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools
from collections import defaultdict

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

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

# 和が0となる場所を答えればよい

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

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
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()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6#float('inf')
#mod = 10 ** 9 + 7 
mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, M = MAP()
a = LIST()

A = sorted([x//2 for x in a], reverse=True)

lcm = A[0]
for x in A[1:]:
	lcm = lcm*x//gcd(lcm, x)

r = lcm//A[0]
n = M//A[0]

#2p+1が1<=2p+1<=n の範囲で rの倍数となるpの個数
if r%2 == 0 or r == 1:
	print(0)
else:
	print(n//r - n//(2*r))

Submission status: Runtime Error

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))


"""
N^2なので素直に計算は無理，部分和を使いたいのでとりあえず累積和
[i+1:j]が条件を満たすとはS[j]-S[i]とj-iが合同．
移行して，S[j]-jとS[i]-iが合同
基本は個数だけ見れば良い

これだけだと，個数がKより大きい時にダメ
直近Kこの情報だけ持つ，今見てる数字が直近K個のものと何個組にできるか
"""
def main():

    mod=10**9+7
    N,K=MI()
    A=LI()
    from collections import defaultdict
    dd = defaultdict(int)
    
    S=[0]*(N+1)
    for i in range(N):
        S[i+1]=(S[i]+A[i])%K
        
    ans=0
    for i in range(K):
        temp=(S[i]-i)%K
        ans+=dd[temp]
        dd[temp]+=1
        
    for i in range(K,N+1):
        temp=(S[i]-i)%K
        temp_m=(S[(i-K)]-(i-K))%K
        dd[temp_m]-=1
        ans+=dd[temp]
        dd[temp]+=1
        
    print(ans)
        
        
    

        

main()

Submission status: Runtime Error

Solution code:
#変数名の付け方の注意！ 配列や集合は大文字！（なぜなら数がたくさんあるから）
#                   要素は小文字（なぜなら１個しかないから）
A = [1,5,7,15,26,45,60,256]

x = int(input())

li = 0
ri = len(A) -1

while (li != ri):
	print(li,ri)
	print("",A[li],A[ri])
	mi = (li + ri) // 2
	if A[mi] < x:
		li = mi+1
	elif A[mi] > x:
		ri = mi-1
	else:
		li = mi
		ri = mi
		print("HIT")
if A[li] == x:
	print("発見！",li)
else:
	print("ないよ！")

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
L=list(map(int,input().split()))
R=list()
if K>=N:
  sums=0
  c=[0]*K
  for i in range(N):
    sums+=L[i]
    sums%=K
    a=(sums-i-1)%K
    R.append(a)
    c[a]+=1
  ans=0
  for i in range(N):
    ans+=(c[i]-1)*c[i]//2
  print(ans+c[0])
else:
  ans=0
  c=[0]*K
  sums=0
  for i in range(N):
    sums+=L[i]
    sums%=K
    a=(sums-i-1)%K
    R.append(a)
  for i in range(K-1):
    c[R[i]]+=1
  ans+=c[0]
  c[R[K-1]]+=1
  for i in range(N):
    if i<N-K:
      ans+=c[R[i]]-1
      c[R[i]]-=1
      c[R[i+K]]+=1
    else:
      ans+=c[R[i]]-1
      c[R[i]]-=1
  print(ans)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
L=list(map(int,input().split()))
R=list()
if K>=N:
  sums=0
  c=[0]*K
  for i in range(N):
    sums+=L[i]
    sums%=K
    a=(sums-i-1)%K
    R.append(a)
    c[a]+=1
  ans=0
  for i in range(N):
    s=(K-R[i])%K
    if s!=0:
      ans+=c[s]
    else:
      ans+=c[s]-1
  print((ans//2)+c[0])
else:
  ans=0
  c=[0]*K
  sums=0
  for i in range(N):
    sums+=L[i]
    sums%=K
    a=(sums-i-1)%K
    R.append(a)
  for i in range(K-1):
    c[R[i]]+=1
  ans+=c[0]
  c[R[K-1]]+=1
  for i in range(N):
    if i<N-K:
      ans+=c[R[i]]-1
      c[R[i]]-=1
      c[R[i+K]]+=1
    else:
      ans+=c[R[i]]-1
      c[R[i]]-=1
  print(ans)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
L=list(map(int,input().split()))
R=list()
if K>=N:
  sums=0
  for i in range(N):
    sums+=L[i]
    sums%=K
    a=(sums-i-1)%K
    R.append(a)
    c[a]+=1
  ans=0
  c=[0]*K
  for i in range(N):
    s=(K-R[i])%K
    ans+=c[s]
  print(ans)
else:
  ans=0
  c=[0]*K
  sums=0
  for i in range(N):
    sums+=L[i]
    sums%=K
    a=(sums-i-1)%K
    R.append(a)
  for i in range(K-1):
    c[R[i]]+=1
  ans+=c[0]
  c[R[K-1]]+=1
  for i in range(N):
    if i<N-K:
      ans+=c[R[i]]-1
      c[R[i]]-=1
      c[R[i+K]]+=1
    else:
      ans+=c[R[i]]-1
      c[R[i]]-=1
  print(ans)

Submission status: Runtime Error

Solution code:
from itertools import accumulate
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = accumulate([0]+ A)
C = [(b-i)%K for i, b in enumerate(B)]
cnt = [0]*N
cnt[C[0]] = 1
res = 0
for i in range(1, N+1):
    if i >= K:
        cnt[C[i-K]] -= 1
    res += cnt[C[i]]
    cnt[C[i]] += 1
print(res)

Submission status: Runtime Error

Solution code:
from collections import deque

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

val_cnt = [0]*k
val_cnt[0] = 1
val_q = deque([0])

ans = 0
curr_sum = 0
for i in range(n):
    curr_sum += al[i]
    curr_sum %= k
    val = (curr_sum - (i+1))%k
    ans += val_cnt[val]
    val_cnt[val] += 1
    val_q.append(val)
    if len(val_q) >= k:
        poped = val_q.popleft()
        val_cnt[poped] -= 1

print(ans)

Submission status: Runtime Error

Solution code:
import sys
import heapq

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N, K = na()

A_array = na()

cusum = 0
mod_array = [0]
for i, a in enumerate(A_array):
    cusum = (cusum + a) % K
    mod = (cusum + K - (i+1)) % K
    mod_array.append(mod)

# print(mod_array)

ans = 0
mod_queue = []
cnt_array = [0] * K
for i, v in enumerate(mod_array):
    heapq.heappush(mod_queue, (i, 1, v))

while(len(mod_queue)):
    i, q, v = heapq.heappop(mod_queue)
    if q == 1:
        ans += cnt_array[v]
        cnt_array[v] += 1
        heapq.heappush(mod_queue, (i+K-0.5, 2, v))
    else:
        cnt_array[v] -= 1
    # print(i, v, q, ans)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
import heapq

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N, K = na()

A_array = na()

cusum = 0
mod_array = [0]
for i, a in enumerate(A_array):
    cusum = (cusum + a) % K
    mod = (cusum + K - (i+1)) % K
    mod_array.append(mod)

# print(mod_array)

ans = 0
mod_queue = []
cnt_array = [0] * N
for i, v in enumerate(mod_array):
    heapq.heappush(mod_queue, (i, 1, v))

while(len(mod_queue)):
    i, q, v = heapq.heappop(mod_queue)
    if q == 1:
        ans += cnt_array[v]
        cnt_array[v] += 1
        heapq.heappush(mod_queue, (i+K-0.5, 2, v))
    else:
        cnt_array[v] -= 1
    # print(i, v, q, ans)

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] = a[i] % k

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

mini = 0
dic = {}
ans = 0
for j in range(1, n+1):
    if j-k+1 > mini:
        dic[(ruiseki[mini]-mini)%k] -= 1
        mini += 1
    if (ruiseki[j-1]-(j-1))%k in dic:
        dic[(ruiseki[j-1]-(j-1))%k] += 1
    else:
        dic[(ruiseki[j-1]-(j-1))%k] = 1
    if (ruiseki[j]-j)%k in dic:
        ans += dic[(ruiseki[j]-j)%k]
print(ans)

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
red=[]
blue=[]
for i in range(H):
  A=list(map(int,input().split()))
  red.append(A)
for i in range(H):
  B=list(map(int,input().split()))
  blue.append(B)
list=[[[0 for i in range(80*(j+k+1))] for j in range(W)] for k in range(H)]
list[0][0][abs(red[0][0]-blue[0][0])]=1
for i in range(H):
  for j in range(W):
    for k in range(len(list[i][j])):
      if list[i][j][k]==1:
        if i+1<H:
          if abs(k-abs(red[i+1][j]-blue[i+1][j]))<12801: 
            list[i+1][j][abs(k-abs(red[i+1][j]-blue[i+1][j]))]=1
          if abs(k+abs(red[i+1][j]-blue[i+1][j]))<12801: 
            list[i+1][j][abs(k+abs(red[i+1][j]-blue[i+1][j]))]=1
        if j+1<W:
          if abs(k-abs(red[i][j+1]-blue[i][j+1]))<12801: 
            list[i][j+1][abs(k-abs(red[i][j+1]-blue[i][j+1]))]=1
          if abs(k+abs(red[i][j+1]-blue[i][j+1]))<12801: 
            list[i][j+1][abs(k+abs(red[i][j+1]-blue[i][j+1]))]=1           
for i in range(12801):
  if list[H-1][W-1][i]==1:
    print(i)
    break

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

N, K = map(int, input().split())
A = list(map(int, input().split()))
cum = [0]*(N+1)
for i in range(1,N+1):
    cum[i] = cum[i-1] + A[i-1]
ans = 0
dic = defaultdict(int)
v_by_indx = defaultdict(int)
for i in range(N+1):
    if i-K >= 0:
        dic[v_by_indx[i-K]] -= 1
    diff = (cum[i]-i)%K
    ans += dic[diff]
    dic[diff] += 1
    v_by_indx[i] = diff
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter

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

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

c = Counter()
for i in range(K-1):
    c[ac[i]] += 1
ans = 0
for i in range(N+1):
    if i+K-1<=N:
        c[ac[i+K-1]] += 1
    ans += c[ac[i]]-1
    c[ac[i]] -= 1

print(ans)