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: Wrong Answer

Solution code:
n, m = map(int, input().split())
l = list(map(int, input().split()))

l = [0] + l
from itertools import accumulate
cum =list(accumulate(l))
cum = [c%m for c in cum]

d = {}
ans = 0
for i in range(n+1):
  if cum[i] not in d:
    d[cum[i]] = 1
  else:
    ans += d[cum[i]]
    d[cum[i]] += 1
print(ans)

Submission status: Wrong Answer

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

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

N, K = lr()
A = np.array([0] + lr())
A = (A-1) % K
Acum = A.cumsum()
counter = defaultdict(int)
answer = 0
for i, x in enumerate(Acum):
    answer += counter[x]
    counter[x] += 1
    if i >= K-1:
        counter[Acum[i-(K-1)]] -= 1

print(answer)

Submission status: Wrong Answer

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

count = 0
# 始めの数字の指定
for i in range(n):
  # 要素数の指定
  for j in range(n-i):
    sum = 0
    for k in range(j-1):
      sum += a[i+(k+1)]
    if sum % (k+1) == j:
      count += 1
      
print(count-1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#解説解答
n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(n):
  a[i] -= 1
  a[i] %= k
#print(a)
b = [0]
for i in range(n):
  b.append((b[-1]+a[i])%k)
#print(b)

ans = 0
now = {0:1}
for i in range(1,n+1):
  if b[i] in now:
    ans += now[b[i]]
    now[b[i]] += 1
  else:
    now[b[i]] = 1
  if i - k + 1 >= 0:
    now[b[i-k+1]] -= 1
  #print(now,i,ans)
print(ans)

Submission status: Wrong Answer

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

D={}
D[0]=1
ans=0

for i in range(1,N+1):
    if A[i] in D:
        ans+=D[A[i]]
        D[A[i]]+=1
    else:
        D[A[i]]=1
    if i-K+1>=0:
        D[A[i-K+1]]-=1
#print(D)
print(ans)

Submission status: Wrong Answer

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

D={}
D[0]=1
ans=0

for i in range(1,N+1):
    if A[i] in D:
        ans+=D[A[i]]
        D[A[i]]+=1
    else:
        D[A[i]]=1
    if i-K+1>=0:
        D[A[i-K+1]]-=1
#print(D)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [(int(a) % K) - 1 for a in input().split()]
    sum_A = [0 for _ in range(N + 1)]

    count = 0
    modK = dict()
    modK[0] = [0]
    for i in range(N):
        sum_A[i + 1] = (sum_A[i] + A[i]) % K
        if sum_A[i+1] not in modK: modK[sum_A[i+1]] = [i + 1]
        else: modK[sum_A[i+1]].append(i+1)

    for key in modK: 
        lenK = len(modK[key])
        for i, a in enumerate(modK[key]):
            width = (a + K if a == 0 else a + K - 1)
            count += bisect_left(modK[key], width, i, lenK) - i - 1
    
    print(count)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
lists=list(map(int,input().split()))
uselist=[0 for i in range(n+1)]
for i in range(n):
    uselist[i+1]=(uselist[i]+lists[i])
anslist=[0 for i in range(n+1)]
for j in range(1,n+1):
    anslist[j]=(uselist[j]-j)%k
dic={}
for i in range(n+1):
    if anslist[i] in  dic.keys():
        dic[anslist[i]].append(i+1)
    else:
        dic[anslist[i]]=[1+i]
#answerに答えを格納することにする
answer=0
for lis in dic.values():  
        index=1
        counter=0
        for i in range(0,len(lis)-1):
            answer+=index-i
            for j in range(index,len(lis)):
                if lis[j]-lis[i]<k:
                    index+=1
                if lis[j]-lis[i]>=k:
                    break
    #lisの要素に対して、部分列の合計がKを超えないように尺取法でその個数を数える
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import accumulate
from collections import defaultdict
input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))
a = [i-1 for i in a]
suma = [0]+list(accumulate(a))
suma = [i%k for i in suma]
rem = defaultdict(int)
ans = 0
if k > n:
    for i in range(n):
        x = suma[i]
        rem[x] += 1
    for s in rem.values():
        ans += s*(s-1)//2
    print(ans)
    exit()
for i in range(k):
    x = suma[i]
    rem[x] += 1
for s in rem.values():
    ans += s*(s-1)//2
for i in range(n-k+1):
    rem[suma[i]] -= 1
    rem[suma[i+k]] += 1
    ans += rem[suma[i+k]] -1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import accumulate
from collections import defaultdict
input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))
a = [i-1 for i in a]
suma = [0]+list(accumulate(a))
suma = [i%k for i in suma]
rem = defaultdict(int)
ans = 0
if k > n:
    for i in range(n):
        x = suma[i]
        rem[x] += 1
    for s in rem.values():
        ans += s*(s-1)//2
    print(ans)
    exit()
for i in range(k):
    x = suma[i]
    rem[x] += 1
for s in rem.values():
    ans += s*(s-1)//2
for i in range(n-k+1):
    rem[suma[i]%k] -= 1
    rem[suma[i+k]%k] += 1
    ans += rem[suma[i+k]] -1
print(ans)

Submission status: Wrong Answer

Solution code:
print("reference: maspy")

from itertools import accumulate
from collections import defaultdict
 
N, K = map(int, input().split())
A = [0] + list(map(lambda x: int(x) - 1, input().split())) # なんで1引いたのか謎。
print("A:", A)
 
# 和が0となる場所を答えればよい
 
Acum = list(accumulate(A))
Acum = [x % K for x in Acum] # この書き方は綺麗。
print("Acum:", Acum)
 
counter = defaultdict(int) # 連想配列。配列番号がワンクッション。
answer = 0
for i, x in enumerate(Acum):
  print("i, x:", i, x)
  print("counter:", counter)
  answer += counter[x]
  counter[x] += 1
  if i >= K - 1:
    print("i - K + 1, Acum[i - K + 1]:", i - K + 1, Acum[i - K + 1])
    counter[Acum[i - K + 1]] -= 1

print(answer)

Submission status: Wrong Answer

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

   for i in range(n):
      a[i] = (a[i]-1)%k
   
   b = [0]
   d = {}
   d[0] = 1

   res = 0
   p = 0

   for i,e in enumerate(a):
      p = (p+e)%k
      if p in d:
         res += d[p]
         d[p] += 1
      else:
         d[p] = 1
      b.append(p)
      if i >= k-2:
         d[b[i-(k-2)]] -= 1
   print(res)

if __name__ == '__main__':
   main()

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
A = list(map(int, input().split()))
S = [0]*(N+1)
dict = {}#最新K件の度数分布の管理

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

ans =0
for i in range(N+1):
    if dict.get(S[i],0):
        ans += dict[S[i]]
        print(i,ans)
    dict[S[i]]=dict.get(S[i],0)+1
    if i >=K:
        dict[S[i-K]]-=1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as d
from itertools import accumulate as ac
n,k=map(int,input().split())
a=[0]+list(ac(list(map(int,input().split()))))
b=d(int)
c=0
for i in range(n+1):
    p=(a[i]-i)%k
    c+=b[p]
    b[p]+=1
    if i-k>=0:
        b[(a[i-k]-i+k)%k]-=1
print(c)

Submission status: Wrong Answer

Solution code:
from collections import Counter

n,k=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
ruisekiwa=[0]
ans=0
for ai in a:
    ruisekiwa.append((ruisekiwa[-1]+ai-1)%k)
# print(ruisekiwa)
c=Counter(ruisekiwa[1:])
for key,val in c.most_common():
    ans+=val*(val-1)//2
print(ans)

Submission status: Wrong Answer

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

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

for i in range(N+1,K+1):
    if K % i == 0:
        K = i
        break

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

check = {0: [0,1,[0]]}

s = 0
for i in range(1,N+1):
    s = (s + A[i-1]) % K
    if s in check:
        j = check[s][0]
        l = check[s][1]
        while j < l and i - check[s][2][j] >= K:
            j += 1
        check[s][0] = j
        count += l - j
        check[s][2].append(i)
        check[s][1] = l + 1
    else:
        check[s] = [0,1,[i]]

print(count)

Submission status: Wrong Answer

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

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

for i in range(N+1,K+1):
    if K % i == 0:
        K = i
        break

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

check = {0: [0,1,[0]]}

s = 0
for i in range(1,N+1):
    s += A[i-1]
    if s >= K:
        s -= K
    if s in check:
        j = check[s][0]
        l = check[s][1]
        while j < l and i - check[s][2][j] >= K:
            j += 1
        check[s][0] = j
        count += l - j
        check[s][2].append(i)
        check[s][1] = l + 1
    else:
        check[s] = [0,1,[i]]

print(count)

Submission status: Wrong Answer

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

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

for i in range(N+1,K+1):
    if K % i == 0:
        K = i
        break

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

check = {0: [0]}

s = 0
for i in range(1,N+1):
    s += A[i-1]
    if s >= K:
        s -= K
    if s in check:
        check[s] = [j for j in check[s] if i - j < K]
        count += len(check[s])
        check[s].append(i)
    else:
        check[s] = [i]

print(count)

Submission status: Wrong Answer

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

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

for i in range(N+1,K+1):
    if K % i == 0:
        K = i
        break

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

check = {0: [0]}

s = 0
for i in range(1,N+1):
    s += A[i-1]
    if s >= K:
        s -= K
    if s in check:
        if i - check[s][0] >= K:
            del check[s][0]
        count += len(check[s])
        check[s].append(i)
    if s not in check:
        check[s] = [i]

print(count)

Submission status: Wrong Answer

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

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

for i in range(N+1,K+1):
    if K % i == 0:
        K = i
        break

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

check = {0: [0]}

s = 0
for i in range(1,N+1):
    s += A[i-1]
    if s >= K:
        s -= K
    if s in check:
        count += len([j for j in check[s] if i - j < K])
        check[s].append(i)
    if s not in check:
        check[s] = [i]

print(count)

Submission status: Wrong Answer

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

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

for i in range(N+1,K+1):
    if K % i == 0:
        K = i
        break

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

check = {0: 0}

s = 0
for i in range(1,N+1):
    s += A[i-1]
    if s >= K:
        s -= K
    if s in check:
        count += check[s]
    if s not in check:
        check[s] = 1
    else:
        check[s] += 1

print(count)

Submission status: Wrong Answer

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

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

for i in range(N+1,K+1):
    if K % i == 0:
        K = i
        break

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

check = {0: True}

s = 0
for i in range(1,N+1):
    s += A[i-1]
    if s >= K:
        s -= K
    if s in check:
        count += 1
    check[s] = True

print(count)

Submission status: Wrong Answer

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

ans = 0
accum = [0]
d = {0 : 1}

for i, a in enumerate(A):
  accum.append((accum[-1] + a - 1)%K)
  if i > K - 1:
    d[accum[i-K]] -= 1
  
  if accum[-1] in d:
    ans += d[accum[-1]]
    d[accum[-1]] += 1
  
  else:
    d[accum[-1]] = 1

print(ans)

Submission status: Wrong Answer

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

ans = 0

S = [0] * N

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

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from collections import defaultdict
N,K = map(int, input().split())
Xs = list(accumulate([0] + [int(x) for x in input().split()]))
Xs = [(x-i)%K for i, x in enumerate(Xs)]
d,r=defaultdict(int),0
for i, x in enumerate(Xs):
    r += d[x]
    d[x]+=1
    if i < K:
        continue
    d[Xs[i-K]] -= 1
print(r)

Submission status: Wrong Answer

Solution code:

def main(A, K):
    t = [0]
    for i, a in enumerate(A):
        t.append((t[i] + a) % K)
    res = 0
    for i in range(1, len(t)):
        if t[i] == i:
            res += 1
        for j in range(1, i):
            if (K + t[i] - t[j]) % K == i - j:
                res += 1
    print(res)


if __name__ == "__main__":
    N, K = map(int, input('N K >').split(' '))
    A = map(int, input('A >').split(' '))
    main(A, K)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
A=map(lambda a: (a-1)%K, A)

S=[0]
for a in A:
    S.append( (S[-1]+a)%K )   #累積和


d=dict()    #要素：要素の数を持つ

ans=0
#S[r]=S[l-1](mod K)
for i in range(N+1):
    x=S[i]%K
    if i==0:
        d[x]=1
    else:
        if x in d:
            ans+=d[x]   #自分より前に同じ出現した、自分と同じ要素の数を答えに追加
            d[x]+=1
        else:
            d[x]=1      
        if 0<=i-K+1:
            x_head=S[i-K+1]%K  #長さK-1の範囲で配列Sを見るため、１つ進んだら一番先頭の要素を辞書から削除する
            d[x_head]-=1

print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
A=map(lambda a: (a-1)%K, A)

S=[0]
for a in A:
    S.append( (S[-1]+a)%K )   #累積和


d=dict()    #要素：要素の数を持つ

ans=0
#S[r]=S[l-1](mod K)
for i in range(N+1):
    x=S[i]
    if i==0:
        d[x]=1
    else:
        if x in d:
            ans+=d[x]   #自分より前に同じ出現した、自分と同じ要素の数を答えに追加
            d[x]+=1
        else:
            d[x]=1      
        if 0<=i-K+1:
            x_head=S[i-K+1]  #長さK-1の範囲で配列Sを見るため、１つ進んだら一番先頭の要素を辞書から削除する
            d[x_head]-=1

print ans

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

S = [0 for _ in range((len(A) + 1))]
D = defaultdict(list)
D[0].append(0)
for i in range(len(A)):
    S[i + 1] = (S[i] + A[i] + K - 1) % K
    D[S[i + 1]].append(i)

# print(S)
# print(D)

total = 0
for k in D.keys():
    # print("key", k)
    n = len(D[k])
    total += n*(n + 1) / 2

print(total)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

S = [0 for _ in range((len(A) + 1))]
D = defaultdict(list)
D[0].append(0)
for i in range(len(A)):
    S[i + 1] = (S[i] + A[i] + K - 1) % K
    D[S[i + 1]].append(i)

# print(S)
# print(D)

total = 0
for k in D.keys():
    # print("key", k)
    for s in range(len(D[k])):
        e = s
        while (e + 1 < len(D[k])) and (D[k][e + 1] - D[k][s] + 1 < K):
            e += 1

        total += e - s
        # print(s, e, D[k][s], D[k][e], total)
        # if k == 0:
        #     total += 1
        #     print(s, e, D[k][s], D[k][e], total, "+1")

        #     total += e - s + 1
        # else:


print(total)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

S = [0] * (len(A) + 1)
D = defaultdict(list)
D[0].append(0)
for i in range(len(A)):
    S[i + 1] = (S[i] + A[i] + K - 1) % K
    D[S[i + 1]].append(i)

print(S)
print(D)

total = 0
for k in D.keys():
    print("key", k)
    for s in range(len(D[k])):
        e = s
        while (e + 1 < len(D[k])) and (D[k][e + 1] - D[k][s] + 1 < K):
            e += 1

        total += e - s
        print(s, e, D[k][s], D[k][e], total)
        # if k == 0:
        #     total += 1
        #     print(s, e, D[k][s], D[k][e], total, "+1")

        #     total += e - s + 1
        # else:


print(total)

Submission status: Wrong Answer

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

sl = [0 for _ in range(N+1)]

for i in range(N):
    sl[i+1] = (sl[i]+ls[i]-1)%K
ans = 0

dic = {}

for i in range(K):
    dic[i] = 0

que = []

for i in range(N+1):
    ans += dic[sl[i]]
    dic[sl[i]] += 1
    que.append(sl[i])
    if len(que) == K:
        dic[que[0]] -= 1
        que.pop(0)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
N, K = map(int, input().split())
A = list(map(int, input().split()))
S = [0]
# 累積和
for i in range(N):
    S.append(S[-1] + A[i] - (i+1))
    S[-1] %= K
    
B = dd(int)  # ここで範囲内のS[i]-iの個数を数えていく。
cnt = 0
for j in range(1,N):
    if j > K:
        B[S[j - 1 - K]] -= 1
    B[S[j]] += 1
    cnt += B[(-S[j]) % K]
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

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

N, K = rl()
A = np.array([0] + rl())
A_cum = A.cumsum()
A_cum = A_cum % K
answer = 0

for i in range(1, N):
    diff = (A_cum[i:] - A_cum[:-i]) % K
    answer += len(diff[diff==i])

print(answer)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math
import sys

m=10**9 + 7
sys.setrecursionlimit(1000010)
(N,K) = map(int,input().split())
A = list( map(int,input().split()))
# print(N,K,A)
B = list( map(lambda x: x % K, A))
C = [0]
x = 0
for b in B:
    x = (x + b ) % K
    C.append(x)

# print(B,C)

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

exit(0)

Submission status: Wrong Answer

Solution code:
import math
import sys

m=10**9 + 7 
sys.setrecursionlimit(1000010)
(N,K) = map(int,input().split())
A = list( map(int,input().split())) 
# print(N,K,A)
B = list( map(lambda x: x % K, A))
C = [0]
x = 0
for b in B:
    x = (x + b ) % K 
    C.append(x)
    
# print(B,C)

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

exit(0)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
from collections import defaultdict

N,K = map(int,input().split())
# 全要素を-1する
A = [0] + [int(i)-1 for i in input().split()]

# Acum[i]: A[1]からA[i]までの累積和
Acum = np.cumsum(A)
Acum = [i%K for i in Acum]

answer = 0
counter = defaultdict(int)

# iの範囲で探索
# j-K+1 <= i <= j-1
for j,x in enumerate(Acum):
    if j == 0:
        continue
    # (i-K+1)回目から(i-1)回目の探索において、xの出現回数
    answer += counter[x]
    # i回目の結果を辞書に追加
    counter[x] += 1
    # 辞書にK回追加した場合
    if j-K-1 >= 0:
        # 辞書から一番古い探索記録を削除
        counter[Acum[j-K+1]] -= 1

print(answer)

Submission status: Wrong Answer

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

print(n, k, a)

count = 0
for i in range(n):
    for j in range(n-i):
        part = 0
        for l in range(i+1):
            part += a[l+j]
        if part%k == i+1:

            count += 1

print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# coding: utf-8

# 整数 > 整数型
def I(): return int(input())

# 整数列 '1 2 3 4' > 整数型リスト
def IsIl(): return list(map(lambda x: int(x), input().split()))

# 改行挟む整数列　'1/n 2/n 3/n' > 整数型りすと
def InIl(n): return [input() for i in range(n)]

# 整数列 '1 2' > 整数型タプル
def IsIt(): return map(lambda x: int(x), input().split())

# 改行挟む整数列　'1\n 2\n 3\n' > 整数型たぷる
def InIl(n): return map(input() for i in range(n))

# 文字列 'abcd' > 文字型リスト
def SsSl(): return list(map(lambda x: x, input()))

# 整数 '1234' > 整数型リスト

# 文字列 'aba' > 辞書（文字型:個数）{'a':2,'b':1}
def SSd():
    from collections import defaultdict
    A = input() # [int(i) for i in input().split()]
    dd=defaultdict(int)
    for a in A:
        dd[a]+=1
    return dd

n,k=IsIt()

a = IsIl()

ans = 0

dp1 = []
les = 0
for num,item in enumerate(a):
    les = (les + item)%k
    if les == num+1: ans += 1
    dp1.append(les)
    

for num1 in range(n-1):
    dp2 = []
    for num, item in enumerate(dp1):
        if num-num1>=1:
            dp2.append(0)
            continue
        les = (item - a[num1])%k
        if les == num-num1:
            ans += 1
        dp2.append(les)

    dp1 = dp2[:]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

#+++++
		
def main():
	n, k = map(int, input().split())
	aal = list(map(int, input().split()))
	
	sss = [0]*(n+1)
	si=0
	for i, a in enumerate(aal):
		si+=a-1
		sss[i+1]=si
	
	count=0
	for j in range(n+1):
		sj=sss[j]
		for i in range(max(0, j-k), j):
			si=sss[i]
			if (sj - si) % k == 0:
				count+=1
	
	print(count)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import itertools
from collections import defaultdict

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

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

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

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: Wrong Answer

Solution code:

n,k = map(int, input().split())
a = [0] + list(map(int, input().split()))
for i in range(n):
    a[i+1] = (a[i] + a[i+1]-1)%k
from collections import defaultdict

d=defaultdict(int)
d[0]=1
ans=0
for i in range(1,n+1):
    ans+=d[a[i]]
    d[a[i]]+=1
    if i>=k:
        d[a[i-k]]-=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
if k==1:
    print(0)
    exit()
a=list(map(int,input().split()))
from itertools import accumulate
a=list(accumulate(a))
from collections import defaultdict

a=list(map(lambda x:x%k,a))
a=list(map(lambda x:x-1,a))
a=[0]+a
d=defaultdict(int)
d[0]=1
ans=0
for i in range(1,n+1):
    ans+=d[a[i]]
    d[a[i]]+=1
    if i>=k:
        d[a[i-k]]-=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
if k==1:
    print(0)
    exit()
a=list(map(int,input().split()))
from itertools import accumulate
a=list(accumulate(a))
#print(a)
from collections import defaultdict

a=list(map(lambda x:x%k,a))
a=list(map(lambda x:x-1,a))
a=[0]+a
#print(a)
d=defaultdict(int)
d[0]=1
ans=0
for i in range(1,n+1):
    ans+=d[a[i]]
    d[a[i]]+=1
    if i>=k:
        d[a[i-k]]-=1
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = [int(i)  for i in input().split()]
'''
W = [0] * (N + 1)

for i in range(N):
    W[i + 1] = W[i] + A[i]
'''
cnt = 0
for i in range(N):
    mod = 0
    for j in range(i, min(i + K, N)):
        mod = (mod + A[j]) %  K
        if mod == j-i:
             cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:

import numpy as np
N, K  = map(int, raw_input().split())
A = np.array(map(int, raw_input().split()))

A_cumsum = np.empty(N+1, dtype=int)
A_cumsum[0] = 0
A_cumsum[1:] = np.cumsum(A)
ans = 0
for i in xrange(1, K):
    seq_sum = A_cumsum[i:] - A_cumsum[:-i]
    ans += np.sum(seq_sum%K==1)
    
print ans

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
if k==1:
    print(n)
    exit()
nl=[]
for i in range(n):
    nl.append((l[i]-1)%k)
r=[0]*(n+1)
for i in range(n):
    r[i+1]=(r[i]+nl[i])%k
p=[]
for i in range(n+1):
    p.append([r[i],i])
p.sort()
s=0
e=0
ans=0
f=0
while e<n+1:
    if p[s][0]!=p[e][0]:
        ans+=f*(f-1)//2
        s=e
        f=0
    else:
        if p[s][1]+k-1>=p[e][1]:
            f+=1
            e+=1
        else:
            ans+=f-1
            f-=1
            s+=1
print(ans+f*(f-1)//2)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
if k==1:
    print(n)
    exit()
nl=[]
for i in range(n):
    nl.append((l[i]-1)%k)
r=[0]*(n+1)
for i in range(n):
    r[i+1]=(r[i]+nl[i])%k
p=[]
for i in range(n+1):
    p.append([r[i],i])
p.sort()
s=0
e=0
ans=0
f=0
while e<n+1:
    if p[s][0]!=p[e][0]:
        ans+=f*(f-1)//2
        s=e
        f=0
    else:
        if p[s][1]+k-2>=p[e][1]:
            f+=1
            e+=1
        else:
            ans+=f-1
            f-=1
            s+=1
print(ans+f*(f+1)//2)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
if k==1:
    print(n)
    exit()
nl=[]
for i in range(n):
    nl.append((l[i]-1)%k)
r=[0]*(n+1)
for i in range(n):
    r[i+1]=(r[i]+nl[i])%k
p=[]
for i in range(n+1):
    p.append([r[i],i])
p.sort()
s=0
e=0
ans=0
f=0
while e<n+1:
    if p[s][0]!=p[e][0]:
        ans+=f*(f-1)//2
        s=e
        f=0
    else:
        if p[s][1]+k-2>=p[e][1]:
            f+=1
            e+=1
        else:
            ans+=f-1
            f-=1
            s+=1
print(ans+f)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
if k==1:
    print(n)
    exit()
nl=[]
for i in range(n):
    nl.append((l[i]-1)%k)
r=[0]*(n+1)
for i in range(n):
    r[i+1]=(r[i]+nl[i])%k
p=[]
for i in range(n+1):
    p.append([r[i],i])
p.sort()
s=0
e=0
ans=0
f=0
while e<n+1:
    if p[s][0]!=p[e][0]:
        ans+=f*(f-1)//2
        s=e
        f=0
    else:
        if p[s][1]+k-2>=p[e][1]:
            f+=1
            e+=1
        else:
            ans+=f
            f-=1
            s+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
if k==1:
    print(n)
    exit()
nl=[]
for i in range(n):
    nl.append((l[i]-1)%k)
r=[0]*(n+1)
for i in range(n):
    r[i+1]=(r[i]+nl[i])%k
p=[]
for i in range(n+1):
    p.append([r[i],i])
p.sort()
s=0
e=0
ans=0
f=0
while e<n+1:
    if p[s][0]!=p[e][0]:
        s=e
        f=0
    else:
        if p[s][1]+k-2>=p[e][1]:
            f+=1
            e+=1
        else:
            ans+=f
            f-=1
            s+=1
print(ans)

Submission status: Wrong Answer

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

S, LUT, ans = [0], {0: 1}, 0
for a in A:
    S.append(S[-1] + a)

for i in range(1, N + 1):
    p = (S[i] - i) % K
    ans += LUT[p] if p in LUT else 0
    if p in LUT:
        LUT[p] += 1
    else:
        LUT[p] = 1
    if i - K + 1 >= 0:
        LUT[(S[i - K + 1] - i + K - 1) % K] -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
def examE():
    N, K = LI()
    A = LI()
    sumA = [0]*(N+1)
    for i in range(1,N):
        sumA[i] = sumA[i-1]+A[i-1]
    d = defaultdict(int)
    ans = 0
    #連想配列 先頭からの番号　余分な量
    que = deque()
    for i,a in enumerate(sumA):
        #K番目以降は一番左のやつ消していく
        if que and que[0][0] <= (i-K):
            d[que.popleft()[1]] -= 1
        cur = (a-i)%K
        ans +=d[cur]
        d[cur] +=1
        que.append((i,cur))
    print(ans)
    return

def examF():
    return

import sys,copy,bisect,itertools,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examE()