Problem:


Score : 500 points

Problem Statement

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

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

Constraints

All values in input are integers.

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

1 \leq K \leq 10^9

1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \cdots A_N

Output

Print the number of subsequences that satisfy the condition.

Sample Input 1

5 4
1 4 2 3 5

Sample Output 1

4

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

Sample Input 2

8 4
4 2 4 2 4 2 4 2

Sample Output 2

7

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

Sample Input 3

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

Sample Output 3

8



Sample input:
5 4
1 4 2 3 5


Sample output:
4

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

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

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

ans = 0
dic = {}
for i, b in enumerate(B):
    if b in dic:
        dic[b].append(i)
    else:
        dic[b] = deque()
        dic[b].append(i)
    
    while len(dic[b]) > 0 and dic[b][0] <= i - K:
        dic[b].popleft()
    ans += len(dic[b])-1
    

print(ans)

Submission status: Accepted

Solution code:
import math
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

class Accumulation:
    def __init__(self,X,accumfunc,init_val=0):
        self.X = X
        self.accumfunc = accumfunc

        N = len(X)
        v1 = [0] * (N+1)
        v1[0] = init_val

        for i in range(N):
            v1[i+1] = accumfunc(v1[i],X[i])

        self.v1 = v1
    
    # 0-index
    def query(self,l,r):
        return self.v1[r+1] - self.v1[l]
    
    def get_array(self):
        return self.v1

class Counter:
    def __init__(self):
        self.dict = {}

    def add(self,x):
        if x in self.dict: self.dict[x] += 1
        else: self.dict[x] = 1

    def decrement(self,x):
        self.dict[x] -= 1

    def get_dict(self):
        return self.dict



INF=10**20
def main():
    N,K=mi()
    A=list(mi())

    def madd(x,y): return (x+y) % K
    V = Accumulation(A,madd)

    v = V.get_array()
    u = [-1] * (N+1)

    for i in range(N+1):  
        u[i] = v[i] - i
        u[i] %= K  
    
    # print(u)
    if K <= N:
        s = u[:K]
        counter = Counter()
        for i in range(K):
            _s = s[i]
            counter.add(_s)

        ans = 0
        current_count = counter.get_dict()
        ans += (current_count[u[0]] - 1)
    
        for i in range(1,N+1):
            # print(u[i:i+K])

            old = u[i-1]
            counter.decrement(old)

            if i+K-1 < len(u):
                new = u[i+K-1] 
                counter.add(new)

            current_count = counter.get_dict()
            ans += (current_count[u[i]] - 1)
            # print(i,current_count[u[i]] - 1)
        
        print(ans)


    else:
        counter = Counter()
        for i in range(N+1):
            counter.add(u[i])
        
        u = counter.get_dict()
        ans = 0
        for c in u.values():
            if c <= 0: continue
            ans += c*(c-1)//2
        
        print(ans)
            
    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
n, k = map(int, input().split())
a = list(map(int, input().split()))
d = defaultdict(int)
sa = [0] * (n + 1)
# d[0] = 1
# if k == 1:
#     print(0)
#     exit()
for i in range(n):
    sa[i + 1] = sa[i] + a[i]
    sa[i + 1] %= k
ans = 0
for i in range(n + 1):
    v = sa[i] - i
    v %= k
    ans += d[v]
    d[v] += 1
    if 0 <= i - k + 1:
        vv = sa[i - k + 1] - (i - k + 1)
        vv %= k
        d[vv] -= 1
print(ans)
# from collections import defaultdict
# n, k = map(int, input().split())
# a = list(map(int, input().split()))
# d = defaultdict(int)
# sa = [0] * (n + 1)
# d[0] = 1
# if k == 1:
#     print(0)
#     exit()
# for i in range(n):
#     sa[i + 1] = sa[i] + a[i]
#     sa[i + 1] %= k
# ans = 0
# for i in range(1, n + 1):
#     v = sa[i] - i
#     v %= k
#     ans += d[v]
#     d[v] += 1
#     if 0 <= i - k + 1:
#         vv = sa[i - k + 1] - (i - k + 1)
#         vv %= k
#         d[vv] -= 1
# print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n, k = map(int, input().split())
a = list(map(int, input().split()))
d = defaultdict(int)
sa = [0] * (n + 1)
d[0] = 1
if k == 1:
    print(0)
    exit()
for i in range(n):
    sa[i + 1] = sa[i] + a[i]
    sa[i + 1] %= k
ans = 0
for i in range(1, n + 1):
    v = sa[i] - i
    v %= k
    ans += d[v]
    d[v] += 1
    if 0 <= i - k + 1:
        vv = sa[i - k + 1] - (i - k + 1)
        vv %= k
        d[vv] -= 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_right

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

dd = defaultdict(list)
dd[0].append(0)
total = 0
for i, num in enumerate(alst, start = 1):
    total += num
    total %= k
    app = total - i
    app %= k
    dd[app].append(i)
ans = 0
for _, lst in dd.items():
    for i, num in enumerate(lst):
        num2 = num + k - 1
        pos = bisect_right(lst, num2)
        ans += pos - i - 1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect

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

s = list(itertools.accumulate(a))

# print(s)
for i in range(0, N+1):
    s[i] = (s[i] - i) % K

# print(s)

d = defaultdict(int)

count = 0
for j in range(1,N+1):
    d[s[j-1]] += 1
    if j-K >= 0:
        d[s[j-K]] -= 1
    # print(j,s[j],d)
    count += d[s[j]]

# print(d)
print(count)

Submission status: Accepted

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
#setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n,k = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]

    memo = deque()
    memo.append(0)
    d = defaultdict(int)
    ans = 0
    nv = 0
    d[0] += 1
    for i,ai in enumerate(a):
        nv += ai-1
        nv %= k
        memo.append(nv)
        if i >= k-1:
            pi = memo.popleft()
            d[pi] -= 1
        ans += d[nv]
        d[nv] += 1

    print(ans)

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n,k = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]

    memo = deque()
    memo.append(0)
    d = defaultdict(int)
    ans = 0
    nv = 0
    d[0] += 1
    for i,ai in enumerate(a):
        nv += ai-1
        nv %= k
        memo.append(nv)
        if i >= k-1:
            pi = memo.popleft()
            d[pi] -= 1
        ans += d[nv]
        d[nv] += 1

    print(ans)

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

n, k = map(int, input().split())
a = [int(x) for x in input().split()]

values = dict()
valuelist = [0]*(n+1)
values[0] = 1
s = 0
ans = 0
if k == 1:
  print(0)
  sys.exit()

for i in range(n):
  s += a[i]-1
  s %= k
  if s in values:
    ans += values[s]
    values[s] += 1
  else:
    values[s] = 1
  
  valuelist[i+1] = s
  if i >= k-2:
    values[valuelist[i-k+2]] -= 1

print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

# 余りの平均が１のもの
N, K = getNM()
A = getList()
A = [(i % K) - 1 for i in A]

for i in range(N - 1):
    A[i + 1] += A[i]
A.insert(0, 0)
A = [i % K if i >= 0 else i for i in A]

num = defaultdict(list)
for i in range(N + 1):
    num[A[i]].append(i)

cnt = 0
for key, opt in num.items():
    for i in range(len(opt)):
        index = bisect_right(opt, opt[i] + K - 1)
        cnt += index - i - 1
print(cnt)

Submission status: Accepted

Solution code:

from collections import defaultdict

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

cs = [0] * (N + 1)
for i in range(N):
    cs[i + 1] = cs[i] + X[i]

y = [(cs[i] - i) % K for i in range(N + 1)]
ctr = defaultdict(int)
ans = 0
for i in range(N + 1):
    ans += ctr[y[i]]
    ctr[y[i]] += 1
    if i - K + 1 >= 0:
        ctr[y[i - K + 1]] -= 1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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 = dict()
cnt[C[0]] = 1
res = 0
for i in range(1, N+1):
    if i >= K:
        cnt[C[i-K]] = cnt.get(C[i-K],0) - 1
    res += cnt.get(C[i], 0)
    cnt[C[i]] = cnt.get(C[i],0) + 1
print(res)

Submission status: Accepted

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 = dict()
cnt[C[0]] = 1
res = 0
for i in range(1, N+1):
    if i >= K:
        cnt[C[i-K]] = cnt.get(C[i-K],0) - 1
    res += cnt.get(C[i], 0)
    cnt[C[i]] = cnt.get(C[i],0) + 1
print(res)

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()))
B = accumulate([0]+ A)
C = [(b-i)%K for i, b in enumerate(B)]
cnt = defaultdict(int)
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: Accepted

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

"""
j - i < K and
Sj - Si == j - i (mod K)
Sj - j == Si - i (mod K) この変形が肝だ…
"""

S = [0 for _ in range(N+1)]
for i in range(N):
  S[i+1] = (S[i] + A[i] - 1) % K
ans = 0
C = Counter(S[:K])
for k,v in C.items():
  ans += v * (v-1) // 2
  
for i in range(K,N+1):
  deln = S[i-K]
  C[deln] -= 1
  addn = S[i]
  if addn in C:
    ans += C[addn]
    C[addn] += 1
  else:
    C[addn] = 1
    
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
n,k=map(int,input().split())
a=list(map(int,input().split()))
x=[0]+list(accumulate(a))
mods=dict()
for i in range(n+1):
    now=(x[i]-i)%k
    if now in mods:
        mods[now].append(i)
    else:
        mods[now]=[i]
ans=0
from bisect import bisect_left
#mods中はソート済
#K未満なら選べる
for i in mods:
    l=len(mods[i])
    for j in range(l):
        b=bisect_left(mods[i],mods[i][j]+k)-1
        ans+=(b-j)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


def main():
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    S = [0] * (N + 1)  # 累積和
    for i in range(1, N + 1):
        S[i] = S[i - 1] + A[i - 1]
    T = [(s - i) % K for i, s in enumerate(S)]
    counter = defaultdict(int)
    ans = 0
    for j in range(N + 1):
        if j >= K:
            counter[T[j - K]] -= 1
        ans += counter[T[j]]
        counter[T[j]] += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
a = list(map(int, input().split()))
def cumsum(a):
    """※ aを破壊する
    l[i] = sum(a[:i]) なるlを返す
    sum(a[i:j]) == l[j+1] - l[i]
    """
    c = 0
    n = len(a)
    a.insert(0, 0)
    for i in range(1, n+1):
        a[i] = a[i-1]+a[i]
    return a
a = cumsum(a)
aa = [((item - i)%k) for i,item in enumerate(a)]
ans = 0
from collections import defaultdict
c = defaultdict(int)
for i in range(min(k, len(aa))):
    c[aa[i]] += 1
for i,item in enumerate(aa):
    c[item] -= 1
#     print(c, item)
    ans += c[item]
    if i+k<n+1:
        c[aa[i+k]] += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import bisect
import heapq
from collections import Counter


def input():
    return sys.stdin.readline().rstrip()


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

    AS = [0]

    it = 0
    for i in range(0, N):
        it += A[i]
        it %= K
        sj = (it - i - 1) % K
        AS.append(sj)
    # 最初だけ作る

    C = dict()
    C[0] = 1
    current = 0
    for j in range(1, N + 1):
        if j > K-1:
            C[AS[j - K]] -= 1
        if AS[j] in C:
            current += C[AS[j]]
            C[AS[j]] += 1
        else:
            C[AS[j]] = 1

    print(current)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

val_cnt = {}
val_cnt[0] = 1
val_q = deque([0])
if k == 1:
    print(0)
    exit()

ans = 0
curr_sum = 0
for i in range(n):
    curr_sum += al[i]
    curr_sum %= k
    val = (curr_sum - (i+1))%k
    val_cnt.setdefault(val,0)
    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: Accepted

Solution code:
import sys 
import numpy as np
from collections import defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K = map(int, readline().split())
A = [0] + list(map(int,readline().split()))
S = np.cumsum(A)
dic = defaultdict(int)
ans = 0
SS = [0] * (N+1)
for i in range(1,N+1):
    rem = (S[i]-i) % K
    SS[i] = rem

for i in range(N+1):
    if i >= K:
        dic[SS[i-K]] -= 1
    ans += dic[SS[i]]
    dic[SS[i]] += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N,K = LI()
A = LI()

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

B = [0]  # Aの累積和をKで割ったもの
for i in range(N):
    B.append((B[-1]+A[i]) % K)

from collections import defaultdict

# 要素の個数がKを超えないことに注意

if N < K:
    d = defaultdict(int)
    for n in B:
        d[n] += 1
    ans = 0
    for n in d.keys():
        m = d[n]
        ans += m*(m-1)//2
    print(ans)
else:
    d = defaultdict(int)
    ans = 0
    for i in range(N):  # A[i]から始まる部分列を考える
        if i == 0:
            for j in range(K):
                d[B[j]] += 1
            ans += d[B[i]]-1
        elif i <= N-K+1:
            d[B[K+i-1]] += 1
            d[B[i-1]] -= 1
            ans += d[B[i]]-1
        else:
            d[B[i-1]] -= 1
            ans += d[B[i]]-1
    print(ans)

Submission status: Accepted

Solution code:
# Rem of sum is Num
# Reviewing problem


from collections import defaultdict


def cnt_func(X):
    res = 0
    right = 0
    L = len(X)
    for i in range(L):
        while right+1 < L and X[right+1] < K+X[i]:
            right += 1
        res += right-i
    return res


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

A = list(map(int, input().split()))
A.insert(0, 0)
for i in range(1, N+1):
    A[i] += A[i-1]
B = [0 for i in range(N+1)]
for i in range(N+1):
    B[i] = (A[i]-i) % K
ans = 0
Mod = defaultdict(list)
for i in range(N+1):
    Mod[B[i]].append(i)
for X in Mod.values():
    ans += cnt_func(X)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

ctr = defaultdict(int)
ans = 0
for j in range(N + 1):
    ans += ctr[y[j]]
    ctr[y[j]] += 1
    if j - K + 1 >= 0:
        ctr[y[j - K + 1]] -= 1
print(ans)

Submission status: Accepted

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


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
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 = 10 ** 9 + 7


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

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

print(ans)

Submission status: Accepted

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


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
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 = 10 ** 9 + 7


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

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

print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
DP=dict()
if K==1:
  print(0)
  exit()
DP[0]=1
P=0
Y=[0]*(N+1)
for i in range(N):
  Y[i+1]=(Y[i]+A[i]-1)%K
  P+=DP.get(Y[i+1],0)
  DP[Y[i+1]]=DP.get(Y[i+1],0)+1
  if i>=K-2:
    DP[Y[i-K+2]]-=1
print(P)

Submission status: Accepted

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

for i in range(N):
  A[i]-=(i+1)
  A[i]%=K
A=[0]+A
D={}
ans=0
for j in range(1,N+1):
  D[A[j-1]]=D.get(A[j-1],0)+1
  if j-K>=0:
    D[A[j-K]]-=1
  ans+=D.get(A[j],0)
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
from collections import defaultdict

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_dic = defaultdict(int)
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_dic[v]
        cnt_dic[v] += 1
        if i + K <= N:
            heapq.heappush(mod_queue, (i+K-0.5, 2, v))
    else:
        cnt_dic[v] -= 1
    # print(i, v, q, ans)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

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: Accepted

Solution code:
from collections import Counter
def solve():
    ans = 0
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    cum = [0]*(N+1)
    for i in range(N):
        cum[i+1] = (cum[i]+A[i])%K
    for i in range(N):
        cum[i+1] = (i+1-cum[i+1])%K
    if N<K:
        c = Counter(cum)
        for v in c.values():
            ans += v*(v-1)//2
    else:
        c = Counter(cum[:K-1])
        for i in range(N):
            c[cum[i]] -= 1
            if i+K-1<=N:
                c[cum[i+K-1]] += 1
            ans += c[cum[i]]
    return ans
print(solve())

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 146
# E - Rem of Sum is Num
# https://atcoder.jp/contests/abc146/tasks/abc146_e
from collections import defaultdict
N, K = map(int, input().split())
*A, = map(int, input().split())

A = [0]+A
d = []
c = defaultdict(int)
x = 0
ans = 0
for i, a in enumerate(A):
    x += a - 1
    x %= K

    d.append(x)
    if i-K >= 0:
        c[d[i-K]] -= 1
    ans += c[x]
    c[x] += 1

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
current=[0]
dic={}
dic[0]=1
ans=0
for i in range(n):
  current.append((current[-1]+a[i]-1)%k)
  if i>=k-1:
    dic[current[-k-1]]-=1
  if current[-1] in dic:
    ans+=dic[current[-1]]
    dic[current[-1]]+=1
  else:
    dic[current[-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()))
a[0]=(a[0]-1)%k
for i in range(n-1):a[i+1]=(a[i+1]+a[i]-1)%k
d=defaultdict(int)
ans=0
d[0]=1
for i in range(n):
  if i==k-1:d[0]-=1
  if i>=k:d[a[i-k]]-=1
  ans+=d[a[i]]
  d[a[i]]+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n,k = map(int,input().split())
a = list(map(int,input().split()))
ruisekiwa = [0 for _ in range(n+1)]
for i in range(n):
	ruisekiwa[i+1] = (ruisekiwa[i] + a[i] - 1) % k
dp = defaultdict(lambda: 0)
ans = 0
tmp = 0
for i in range(n+1):
	tmp += 1
	if tmp > k:
		dp[ruisekiwa[i-k]] -= 1
	ans += dp[ruisekiwa[i]]
	dp[ruisekiwa[i]] += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from collections import defaultdict

N, K = map(int, input().split())
As = np.array([0] + list(map(int, input().split())))
#Find (i, j) that satisfies "sum(As[i:j]) % K == j - i"
#If 0 < j - i < K then 
#sum(As[i:j]) % K == j - i % K
#<-> (sum(As[:j]) - j) % K == (sum(As[:i]) - i) % K

mods = As % K
csum_mods = np.cumsum(mods)
magic_array = (csum_mods - np.arange(0, N+1)) % K

indices = defaultdict(list)
for i, m in enumerate(magic_array.tolist()):
    indices[m].append(i)

ans = 0
for ls in indices.values():
    j = 1
    for i in range(len(ls)):
        while j < len(ls):
            if ls[j] - ls[i] < K:
                j += 1
            else:
                break
        ans += j - i - 1
        
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter


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]) % K
    # S[i + 1] = S[i] + A[i]

cnt = 0
C = Counter()
for r in range(N + 1):
    R = (S[r] - r) % K
    cnt += C[R]
    C[R] += 1
    l = r - (K - 1)
    if l >= 0:
        L = (S[l] - l) % K
        C[L] -= 1

print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter


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]) % K
    S[i + 1] = S[i] + A[i]

cnt = 0
C = Counter()
for r in range(N + 1):
    R = (S[r] - r) % K
    cnt += C[R]
    C[R] += 1
    l = r - (K - 1)
    if l >= 0:
        L = (S[l] - l) % K
        C[L] -= 1

print(cnt)

Submission status: Accepted

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)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

d = defaultdict(int)
l, r = 0, 0
ans = 0
while r <= N:
    a = Acc[r]
    ans += d[a]
    d[a] += 1
    r += 1
    if r - l >= K:
        d[Acc[l]] -= 1
        l += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect
input = lambda: sys.stdin.readline().rstrip()


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

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

    # print(d)

    ans = 0
    for k, v in d.items():
        if len(v) <= 1:
            continue
        else:
            for i in range(len(v)):
                s = v[i] + K - 1
                si = bisect.bisect_right(v, s)
                ans += (si - i) - 1
                # print(i, si)

    print(ans)


if __name__ == '__main__':
    solve()

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()))

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

ans = 0
counter = defaultdict(int)
queue = []
for i,s in enumerate(S):
  t = (s-i) % K

  ans += counter[t]
  counter[t] += 1

  queue.append(t)
  if len(queue) >= K:
    counter[queue[0]] -= 1
    queue.pop(0)

print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,k = LI()
    aa = LI()

    c = collections.defaultdict(int)
    c[0] = 1
    t = [0]
    r = 0
    for i in range(n):
        a = aa[i]
        tt = (t[-1] + a - 1) % k
        t.append(tt)
        if i >= k-1:
            # print("k", t[i-k+2],i-k+2)
            c[t[i-k+1]] -= 1
        r += c[tt]
        c[tt] += 1
        # print("ar", a,tt,r,sorted(c.items()), t)

    return r

print(main())

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]
mp={0:1}
ans=0
for t in range(n):
  i=a[t]
  
  if t>=k-1:
    mp[dp[-k]]-=1  
    
  num=(dp[-1]+i-1)%k
  if num in mp.keys():
    ans += mp[num]
    mp[num] += 1
  else:
    mp[num] = 1
  dp.append(num)

print(ans)