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: Time Limit Exceeded

Solution code:
N, K = input().split(' ')
N = int(N)
K = int(K)

A = input().split(' ')
A = [int(a) for a in A]

answers = []

for starti in range(len(A)):

    for length in range(1, K):
        # print('start-length', starti, length)

        if starti + length <= len(A):
            bubunretu = A[starti:starti + length]
        # print(bubunretu, 'bubun')

            if sum(bubunretu) % K == len(bubunretu):
                # print('ok',starti,length, bubunretu)
                answers.append(bubunretu)

# print(answers)

# ans_long = list(set(answers))
print(len(answers))

# print(len(list(set(answers))))

Submission status: Time Limit Exceeded

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

ans = 0

for i in range(1, n+1):
    for j in range(n-i+1):
        cut = li[j:j+i]
        if sum(cut)%k == i:
            ans += 1
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    A = tuple(map(int, input().split()))
    a = 0
    for j in range(N):
        x = A[j] % K
        if x == 1:
            a += 1
    s = A[0] % K
    for i in range(1, N):
        t = i + 1
        y = (s + A[i]) % K
        if y == t:
            a += 1
        s = y
        s2 = y
        for j in range(1, N-i):
            y = (s2 + A[i+j] - A[j-1]) % K
            if y == t:
                a +=1
            s2 = y
    return a
print(main())

Submission status: Time Limit Exceeded

Solution code:
list1 = input().split(" ")
list2 = input().split(" ")
count = 0
for t in range(1,len(list2)+1):
  p = len(list2)-t+1
  for i in range(0,p):
    sum = 0
    for s in range(i,i+t):
      sum+=int(list2[s])
    if sum%int(list1[1]) == t:
      count+=1
print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    A = tuple(map(int, input().split()))
    l = [0] * N
    a = 0
    for j in range(N):
        x = A[j] % K
        if x == 1:
            a += 1
        l[j] = x
    for i in range(1, N):
        t = i + 1
        y = (l[0] + A[i]) % K
        if y == t:
            a += 1
        l[0] = y
        for j in range(1, N-i):
            y = (l[j-1] + A[i+j] - A[j-1]) % K
            if y == t:
                a +=1
            l[j] = y
    return a
print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    A = tuple(map(int, input().split()))
    l = [[0] * N for _ in range(N)]
    a = 0
    for j in range(N):
        x = A[j] % K
        if x == 1:
            a += 1
        l[j][0] = x
    for i in range(1, N):
        t = i + 1
        y = (l[0][i - 1] + A[i]) % K
        if y == t:
            a += 1
        l[0][i] = y
        for j in range(1, N-i):
            y = (l[j-1][i] + A[i+j] - A[j-1]) % K
            if y == t:
                a +=1
            l[j][i] = y
    return a
print(main())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math

N, K = map(int, input().split(' '))
As = np.array(list(map(int, input().split(' '))))

# As %= K

c = 0
for l in range(1, len(As)+1):
    for s in range(0, len(As)-l + 1):
        # print(As[s:s+l])
        if As[s:s+l].sum() % K == l:
            c += 1

print(c)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K  = [int(i) for i in input().split()]
    A  = [int(i) for i in input().split()]
    v = [0] * N
    r = 0
    for i, a in enumerate(A, 1):
        for j in range(i):
            v[j] = t = (v[j] + a) % K
            if t == i - j:
                r += 1
    return(r)


print(main())

Submission status: Time Limit Exceeded

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

ans=0
for i in range(N):
    for j in range(i+1,N+1):
        if (R[j]-R[i])%K==(j-i):
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int,input().split()))
su = [0]
cnt = 0
def check():
    global k, su, cnt
    l = len(su) - 1 - k 
    if l < 0: l = 0
    for i in range(l, len(su)-1):
        if (su[len(su)-1] - su[i]) % k == len(su) - 1 - i:
            cnt += 1

for i in a:
    su.append(su[len(su)-1]+i)
    check()
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import accumulate
N ,K = map(int, input().split())
A = list(map(int, input().split()))

a = list(accumulate(A))

ans = 0

for i in range(N):
    if a[i] % K == i + 1:
        ans += 1
    for j in range(i):
        s = a[i] - a[j]            
        if s % K == i - j:
            ans += 1
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  _, k = map(int, input().split())
  values = list(map(lambda x: int(x) % k, input().split()))
  count = 0

  for i in range(len(values)):
    s = 0

    for j in range(i, len(values)):
      s = (s + values[j]) % k
      count += int(s == j - i + 1)

  print(count)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K  = [int(i) for i in input().split()]
    A  = [int(i) for i in input().split()]
    r = 0
    for i in range(N):
        t = 0
        for c, a in enumerate(A[i:], 1):
            t = (t + a) % K
            if t == c:
                r += 1
    return(r)


print(main())

Submission status: Time Limit Exceeded

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

cums = [0]
for a in A:
    cums.append(cums[-1] + a)

ans = 0
for d in range(1,min(K,N+1)):
    for i in range(N+1-d):
        v = (cums[i+d] - cums[i]) % K
        if v==d:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

cums = [0]
for a in A:
    cums.append(cums[-1] + a)

ans = 0
for d in range(1,K):
    for i in range(N+1-d):
        v = (cums[i+d] - cums[i]) % K
        if v==d:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(i) for i in input().split()]
A = [int(i)%K for i in input().split()]
# print(A)
c = 0
for a in range(1,K):
    # print(A[0:a])
    total = sum(A[0:a])
    for b in range(len(A)-a+1):
        # print(total, a, b, a+b, c)
        if total%K == a:
            c += 1
        total -= A[b]
        if a+b < len(A):
            total += A[b+a]
print(c)

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=[(A[i]-i-1)%K for i in range(N)]
A=[0]+A
from collections import Counter
if K>N:
  a=Counter(A)
  ans=0
  for v in a.values():
    ans+=v*(v-1)/2
  print(int(ans))
else:
  ans=0
  d={}
  for i in range(K):
    if A[i] in d:
      ans+=d[A[i]]
      d[A[i]]+=1
    else:
      d[A[i]]=1
  for i in range(K,N+1):
    d[A[i-K]]-=1
    if A[i] in d:
      ans+=d[A[i]]
      d[A[i]]+=1
    if A[i] not in d or d[A[i]]==0:
      d[A[i]]=1
  print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


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

    if K == 1:
        print(0)
        return

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

    dp = [d % K for d in dp]

    ans = 0
    d = defaultdict(int)
    d[0] = 1
    for i in range(1, N + 1):
        ans += d[dp[i]]
        d[dp[i]] += 1

        if i - K + 1 >= 0:
            d[dp[i - K + 1]] -= 1

    print(ans)


def main():
    solve()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    A = [(a - 1) % K for a in A]

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

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

    ans = 0
    for vec in indices.values():
        right = 0
        for left in range(len(vec)):
            while right + 1 < len(vec) and vec[right + 1] - vec[left] < K:
                right += 1

            ans += right - left
            if left == right:
                right += 1

    print(ans)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
n,k = ma()
A = lma()
s = [0]*(n+1)
l = [0]*(n+1)
for i in range(n):
    s[i+1]=(s[i]+A[i])%k
    l[i+1]=(s[i+1]-(i+1))%k
ans = 0
co = collections.Counter(l[:min(n+1,k)])
for num,cnt in co.items():
    ans+=cnt*(cnt-1)//2
for i in range(k,n+1):
    co[l[i-k]]-=1
    ans+=co[l[i]]
    co[l[i]]+=1



print(ans)

Submission status: Accepted

Solution code:
import bisect
N,K=map(int,input().split())
A=list(map(int,input().split()))
S=[0 for i in range(N+1)]
for i in range(N):
    S[i+1]=S[i]+A[i]
    S[i+1]%=K
X=[(S[i]-i)%K for i in range(N+1)]
D=dict()
for i in range(N+1):
    if X[i] in D:
        D[X[i]].append(i)
    else:
        D[X[i]]=[i]
ans=0
for k in D:
    for i in D[k]:
        L=bisect.bisect_left(D[k],i-K+1)
        R=bisect.bisect_right(D[k],i+K-1)
        ans+=R-L-1
print(ans//2)

Submission status: Accepted

Solution code:
from collections import defaultdict
n, k = map(int, input().split())

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

mp = defaultdict(int)

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

Submission status: Accepted

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(min(K,N+1)):
        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: Accepted

Solution code:
# n,k = map(int,input().split())
# A = list(map(int,input().split()))
# c = 0
# from collections import Counter
# d = Counter()
# d[0] = 1
# ans = 0
# r = [0]*(n+1)
# for i,x in enumerate(A):
#     if i>=k-1:
#         d[r[i-(k-1)]]-=1#ここで範囲kからはみ出たものの数を減らす
#     c = (c+x-1)%k
#     ans += d[c]
#     d[c] += 1
#     r[i+1] = c
# print(ans)
n,k = map(int,input().split())
A = list(map(int,input().split()))
S = [0]
for a in A:
    S.append(S[-1] + a)
# print(S)
from collections import defaultdict
dic = defaultdict(int)
ans = 0

for i,s in enumerate(S):
    if i >=k:
        dic[(S[i-k] - (i-k))%k]-=1
    ans += dic[(S[i]- i)%k]
    # print(i,s,(S[i]- i)%k,dic[(S[i]- i)%k],ans)
    dic[(S[i]- i)%k] += 1
print(ans)



#(12-6)%4

Submission status: Accepted

Solution code:
from collections import defaultdict

N, K = map(int, input().split())
A = list(map(lambda x: int(x) - 1, input().split()))
A_accsum = [0] * (N+1)
for i, a in enumerate(A):
    A_accsum[i+1] = (A_accsum[i]+a) % K

count = defaultdict(lambda: 0)
piv = A_accsum[0]
count[piv] += 1
ans = 0
for i in range(1, min(K, N+1)):
    a = A_accsum[i]
    count[a] += 1
for i in range(K, N + 1):
    a = A_accsum[i]
    piv = A_accsum[i-K]
    count[piv] -= 1
    ans += count[piv]
    count[a] += 1
for i in range(max(0, N - K+1), N+1):
    piv = A_accsum[i]
    count[piv] -= 1
    ans += count[piv]
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal
from argparse import ArgumentParser

args=ArgumentParser()
args.add_argument('-loc', '--local', type=bool,default=False)
LOCAL=args.parse_args().local

def input(): 
    x=sys.stdin.readline(); 
    if x[-1]=="\n": 
        return x.rstrip() 
    return x
    
def printe(*x):_=print("## ",*x,file=sys.stderr) if LOCAL else 0
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    acc=[0]*(N+1)
    cur=0
    if K==1:
        print(0)
        return 

    for i,a in enumerate(A):
        cur+=a
        cur%=K
        acc[i+1]=(cur-i-1)%K

    j=1
    d=Counter()
    d[0]=1
    ans=0
    for i in range(N):
        d[acc[i]]-=1
        while j-i<K and j<N+1:
            d[acc[j]]+=1
            j+=1
        ans+=d[acc[i]]

    print(ans)
        
        



if __name__ == "__main__":
    main()

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
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 main():
    N, K = LI()
    A = LI()
    cumsum = [0] * (N+1)
    c = collections.defaultdict(list)
    memo = [0] * (N+1)
    c[0].append(0)
    for i in range(N):
        # cumsum[i] ... [0, i)
        cumsum[i+1] = (cumsum[i] % K + A[i]) % K
        val = (cumsum[i+1] - (i+1)) % K
        memo[i+1] = val
        c[val].append(i+1)
    # print(cumsum)
    # print(memo)
    # print(c)
    ans = 0
    for i in range(N+1):
        val = memo[i]
        l_ix = bisect.bisect_right(c[val], i)
        r_ix = bisect.bisect_right(c[val], i + (K-1))
        # print('i: {}, memo[i]: {}, c[val]: {}, l_ix: {}, r_ix: {}'.format(i, memo[i], c[val], l_ix, r_ix))
        ans += r_ix - l_ix
    # for i in range(N):
    #     if A[i] % K == 1:
    #         ans += 1
    print(ans)
main()

Submission status: Accepted

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

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

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

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

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

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

mp = defaultdict(int)
ans = 0
q = deque([])
for j in range(N + 1):
    ans += mp[acc[j]]
    mp[acc[j]] += 1
    q.append(acc[j])
    if len(q) == K:
        mp[q[0]] -= 1
        q.popleft()
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
c = 0
from collections import Counter
d = Counter()
d[0] = 1
ans = 0
r = [0]*(n+1)
for i,x in enumerate(A):
    if i>=k-1:
        d[r[i-(k-1)]]-=1#ここで範囲kからはみ出たものの数を減らす
    c = (c+x-1)%k
    ans += d[c]
    d[c] += 1
    r[i+1] = c
print(ans)

Submission status: Accepted

Solution code:

from itertools import accumulate
from collections import defaultdict, deque
def resolve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A = accumulate([a % K for a in A])
    A = [0] + list(A)

    # 区間 [i,j] の和(累積和): dj+1−di
    # 区間 [i,j] の要素の数(0_indの為 +1): j−i+1
    # 上記を一般化:  dr−dl=r−l となるものの個数を求める
    # r−l<K  の時、mod K において式変形が成り立つ, dr−r=dl−l
    # rを固定し辞書で管理すれば、dl−lと同じ値なので個数を求められる。

    cnt = defaultdict(int)
    q = deque()
    ans = 0
    for r in range(N + 1):
        t = (A[r] - r) % K
        ans += cnt[t]
        cnt[t] += 1

        q.append(t)
        if len(q) == K:
            left = q.popleft()
            cnt[left] -= 1

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

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

N,MOD = IL()
A = IL()

if MOD == 0:
  print(0)
  exit()

def ACC1(l):
  N = len(l)
  ret = [0]*(N+1)
  for i in range(N):
    ret[i+1] = ret[i]+l[i]
  return ret

ACC = ACC1(A)

dic = DD(list)
for i in range(N+1):
  dic[(ACC[i]-i)%MOD].append(i)
ans = 0
for k in dic:
  l = len(dic[k])
  for i in range(l):
    p = bisect.bisect(dic[k],dic[k][i]+MOD-1)
    ans += p-i-1

print(ans)

Submission status: Accepted

Solution code:
def add(x):
	if x in dic:
		dic[x]+=1
	else:
		dic[x]=1
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[0]
for i in range(n):
	b.append((b[-1]+a[i]-1)%k)
dic={}
ans=0
for i in range(n+1):
	add(b[i])
	ans+=dic[b[i]]-1
	if i-k+1>=0:
		dic[b[i-k+1]]-=1
print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

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

    c = 0
    d = collections.Counter()
    d[0] = 1
    ans = 0
    r = [0] * (N+1)
    for i,x in enumerate(A):
        if i >= K-1:
            d[r[i-(K-1)]] -= 1
        c = (c + x - 1) % K
        ans += d[c]
        d[c] += 1
        r[i+1] = c

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007
INF = float("inf")

def main():
    N, K = LI()
    A = LI()
    S = list(itertools.accumulate(A))
    keep = defaultdict(int)
    keep[0] += 1
    ans = 0

    for i in range(1, N+1):
        v = (S[i-1] - i) % K
        if i == K:
            keep[0] -= 1
        if i - K > 0:
            w = (S[i-K-1] - (i - K)) % K
            keep[w] -= 1
        ans += keep[v]
        keep[v] += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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]
    s[i] = (s[i] - i) % k
s[n] = (s[n] - n) % k

count = dict()
for i in range(min(k-1, n+1)):
    if not s[i] in count:
        count[s[i]] = 0
    count[s[i]] += 1

ans = 0
for i in range(k-1, n+1):
    if not s[i] in count:
        count[s[i]] = 0
    count[s[i]] += 1
    count[s[i-k+1]] -= 1
    ans += count[s[i-k+1]]

for i in count.values():
    ans += i * (i - 1) // 2

print(ans)