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:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

N,K = m()

a = l()


aaa = [0 for i in range(N+1)]
aaa[1] = a[0] % K
for i in range(1,N):
    aaa[i+1] = aaa[i] + a[i]
    aaa[i+1] %= K


co = 0
rr = N
ll = N-1
while True:
    if rr == 0:
        break
    on = aaa[rr] - aaa[ll]
    if on < 0:
        on += K
    if on == rr-ll:
        co += 1
        if ll != 0:
            ll -= 1
        else:
            if rr != 0:
                rr -= 1
    else:
        if rr - ll == 1 and rr != 1:
            if ll != 0:
                ll -= 1
        else:
            rr -= 1
    if ll > rr:
        if ll != 0:
            ll -= 1
        else:
            if rr != 0:
                rr -= 1
print(co)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = [0] * (N+1)
for i, a in enumerate(A):
    B[i+1] = B[i] + a%K
for i in range(N+1):
    B[i] -= i
    B[i] %= K
ans = 0
tbl = [0] * min(K, N+1)
for i in range(min(K,N+1)):
    if B[i] > N:
        continue
    tbl[B[i]] += 1
    ans += tbl[B[i]] - 1
for i in range(K, N+1):
    tbl[B[i-K]] -= 1
    tbl[B[i]] += 1
    ans += tbl[B[i]] - 1
print(ans)

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
from collections import defaultdict
def main():
    N, K = map( int, input().split())
    A = list( map( int, input().split()));
    M = [0]*N
    d = defaultdict( int)
    d[0] = 1
    now = 0
    ans = 0
    if K == 1:
        print(sum( list( map(lambda x: x%2, A))))
        return
    for i in range(N):
        if i == K-1:
            d[0] -= 1
        if i >= K-1:
            d[M[i-(K-1)]] -= 1
#            print(i-(K-1), M[i-(K-1)], d)
        now = (now + A[i] - 1)%K
        M[i] = now
        ans += d[now]
        d[now] += 1

        # print(i, ans)

    print(ans)
        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from itertools import accumulate
read = sys.stdin.read

N, K, *A = map(int, read().split())
a = list(accumulate([0] + A))
print(a)
left = 0
right = 1
pair = []
while right <= N:
    r = (a[right] - a[left]) % K
    if r == right - left:
        pair.append((left, right))
        if right == left + 1:
            right += 1
        else:
            left += 1
    elif r > right - left and left + 1 < right:
        left += 1
    else:
        right += 1

right -= 1
while left < N:
    r = (a[right] - a[left]) % K
    if r == right - left:
        pair.append((left, right))
    left += 1

print(len(pair))

Submission status: Wrong Answer

Solution code:
n,k = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
dp = [[0 for _ in range(k+1)] for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1,k+1):
        if i >= 2:
            dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
        else:
            dp[i][j] = dp[i-1][j] + dp[i-1][j-1] - dp[i-2][j-1]
print(dp[n][k])

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce
def cmb(n,r):
    r=min(n-r,r)
    if r==0:
        return 1
    over=reduce(mul,range(n,n-r,-1))
    under=reduce(mul,range(1,r+1))
    return over//under

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

a.sort()
k=[1]
ans=0
for i in range(1,n):
    if a[i]==a[i-1]:
        k[-1]+=1
    else:
        if len(k)>=2:
            ans+=k[-1]*k[-2]
        k.append(1)
if len(k)>=2:
    ans+=k[-1]*k[-2]
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = [0] * (N+1)
for i, a in enumerate(A):
    B[i+1] = B[i] + a%K
for i in range(N+1):
    B[i] -= i
    B[i] %= K
ans = 0
tbl = [0] * min(K, N+1)
for i in range(min(K,N+1)):
    if B[i] > N+1:
        continue
    tbl[B[i]] += 1
    ans += tbl[B[i]] - 1
for i in range(K, N+1):
    tbl[B[i-K]] -= 1
    tbl[B[i]] += 1
    ans += tbl[B[i]] - 1
print(ans)

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
from collections import defaultdict
def main():
    N, K = map( int, input().split())
    A = list( map( int, input().split()));
    M = [0]*N
    d = defaultdict( int)
    d[0] = 1
    now = 0
    ans = 0
    if K == 1:
        print(sum( list( map(lambda x: x%2, A))))
        return
    for i in range(N):
        if i == K-1:
            d[0] -= 1
        if i >= K:
            d[M[i-K]] -= 1
#            print(i-(K-1), M[i-(K-1)], d)
        now = (now + A[i] - 1)%K
        M[i] = now
        ans += d[now]
        d[now] += 1

        # print(i, ans)

    print(ans)
        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

ans = 0
s = num[0]
l, r = 0, 1
while l < n and r < n:
    if s == r-l:
        ans += 1
    if r == n:
        l += 1
        s -= num[l]
    elif r-l == k:
        s -= num[l]
        l += 1
    elif s > k:
        s -= num[l]
        l += 1
    elif s + num[r-1 ]> k:
        s -= num[l]
        l += 1

    else:
        r += 1
        s += num[r-1]

print(ans)

Submission status: Wrong Answer

Solution code:

n, k = map(int, input().split())
a = list(map(int, input().split()))
count = 0
for i in range(1, 6):
    for j in range(n  - i + 1):
        subarr = a[j:j + i]
        if sum(subarr) % k == i:
            count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np

N,K=map(int,input().split())
A=np.array(input().split(),dtype=int)
A=A%K

Asum=np.cumsum(A)

# print(Asum)

ans=0
for i in range(0,min(len(Asum),K-1)):
  if Asum[i]==i+1:
    ans+=1
#     print("single:",i+1)

for L in range(len(Asum)):
  for R in range(L+1,min(L+K,len(Asum))):
    if (Asum[R]-Asum[L])%K==R-L:
#       print("pair:",L+2,R+1,Asum[L],Asum[R])
      ans+=1
      
print(ans)

Submission status: Wrong Answer

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

import numpy as np
from scipy.ndimage.interpolation import shift

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

array=np.array(res)
ans=0

for i in range(1,N):
    ans+=((array-shift(array,i,cval=0))%K==i).sum()
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = tuple(map(int, input().split()))
ruiseki = [0]
for i in range(n):
    ruiseki.append((ruiseki[i] + a[i])%k)

cnt = 0
for i in range(1, n+1):
    val = ruiseki[i-1]
    for j in range(i, n+1):
        num = j - i
        if num > k - 1:
            break
        if (ruiseki[j]-val)%k == num:
            cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
from collections import defaultdict
def main():
    N, K = map( int, input().split())
    A = list( map( int, input().split()));
    M = [0]*N
    d = defaultdict( int)
    d[0] = 1
    now = 0
    ans = 0
    if K == 1:
        print(sum( list( map(lambda x: x%2, A))))
        return
    for i in range(N):
        if i == K-1:
            d[0] -= 1
                    
        if i >= K-1:
            d[M[i-(K-1)]] -= 1
        #     print("aa", i-K, M[i-K])
        # print(Mod, M)
        now = (now + A[i] - 1)%K
        M[i] = now
        ans += d[now]
        d[now] += 1

        # print(i, ans)

    print(ans)
        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

import numpy as np
from scipy.ndimage.interpolation import shift

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

print(res)
array=np.array(res)
ans=0

for i in range(1,N):
    print(array-shift(array,i,cval=0))
    ans+=((array-shift(array,i,cval=0))%K==i).sum()
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap



@mt
def slv(N, K, A):
    ans = 0
    for i in range(N):
        s = 0
        for j in range(i, N):
            if j-i > K:
                break
            s += A[j]
            s %= K
            if s == j-i:
                ans += 1

    return ans


def main():
    N, K = read_int_n()
    A = read_int_n()
    print(slv(N, K, A))



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
from collections import defaultdict
def main():
    N, K = map( int, input().split())
    A = list( map( int, input().split()));
    M = [0]*N
    d = defaultdict( int)
    d[0] = 1
    now = 0
    ans = 0
    for i in range(N):
        if i == K-1:
            d[0] -= 1
        if i >= K-1:
            d[M[i-(K-1)]] -= 1
        #     print("aa", i-K, M[i-K])
        # print(Mod, M)
        now = (now + A[i] - 1)%K
        M[i] = now
        ans += d[now]
        d[now] += 1
        # print(i, ans)

    print(ans)
        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=0
for l in range(1,len(a)):
    for i in range(len(a)-l+1):
        if sum(a[i:i+l])%k==l:
            ans+=1
print(ans)

Submission status: Wrong Answer

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

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

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

# print(ss)

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

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

print(ans)

Submission status: Wrong Answer

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

Rw = [0]
for i in range(N):
    Rw.append((Rw[i] + As[i]) % K)

c = 0
for i in range(N):
    for j in range(i + 1, N + 1):
        Rwd = Rw[j] - Rw[i]
        if Rwd < 0:
            Rwd = Rwd + K
        if Rwd == j - i:
            c += 1

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = tuple(map(lambda x: int(x)%k, input().split()))
ruiseki = [0]
for i in range(n):
    ruiseki.append(ruiseki[i] + a[i])

cnt = 0
for i in range(1, n+1):
    for j in range(i, n+1):
        num = j -i
        if num > k:
            break
        if (ruiseki[j]-ruiseki[i-1])%k == num:
            cnt += 1

print(cnt)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N,K=map(int, input().split())
A=list(map(int, input().split()))
dp=[0 for i in range(N)]
count=0
for i in range(N):
    for j in range(N):
        if i==0:
            dp[j]=A[j]%K
        elif j-i>=0 and i>0:
            #print(dp[j],dp[j-1])
            dp[j]=(dp[j]+A[j-i])%K
            #print('A')
        if dp[j]==i+1:
            count+=1
            #print(dp[j],count)
    #print(dp)
        

print(count)

Submission status: Wrong Answer

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

import itertools
al_ac = list(itertools.accumulate(al))

for i,a in enumerate(al_ac):
    al_ac[i] = a % k

al_ac.insert(0,0)

ans = 0
for i in range(1,k+1):
    for j in range(n+1-i):
        a = (al_ac[j+i] - al_ac[j]) % k
        if a == i:
            print(i,j)
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n - 1):
  a[i] -= 1
  a[i + 1] += a[i]
a[n - 1] -= 1

memo = {0 : []}
for i in range(n):
  if a[i] % k not in memo.keys():
    memo[a[i] % k] = [i]
  else:
    memo[a[i] % k].append(i)

ans = bisect.bisect_left(memo[0], k - 1)

for i in memo.keys():
  for j in range(len(memo[i]) - 1):
    ans += bisect.bisect_left(memo[i], memo[i][j] + k) - 1 - j

print(memo)
print(ans)

Submission status: Wrong Answer

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 = sum([s for s in range(i,i+t) ])
  #  for s in range(i,i+t):
 #     sum+=int(list2[s])
    if Sum%int(list1[1]) == t:
      count+=1
print(count)

Submission status: Wrong Answer

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(1,N):
        if i+j>=N:
            break
        if (R[i+j]-R[i])%K==(j):
            ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
n,k = map(int,input().split( ))
a = list(map(int, input().split( )))
ans = 0
for i in range(n):
    a[i] -= 1
sm= 0
a_sm = [0]
for i in range(n):
    sm += a[i]
    sm%=k
    a_sm.append(sm)

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

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

       
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter
input = sys.stdin.readline
INF = 10**9

n, k = [int(item) for item in input().split()]
a = [int(item) - 1 for item in input().split()]
cumsum = [0] * (n + 1)
for i in range(n):
    cumsum[i+1] = cumsum[i] + a[i]
    cumsum[i+1] %= k

cnt = [0] * n
num = 0
ans = 0
for i, item in enumerate(cumsum):
    if item <= n - 1:
        ans += cnt[item]
        cnt[item] += 1
        num += 1
    else:
        num += 1
    if num >= k:
        left = cumsum[i - k + 1]
        if left <= n - 1 and cnt[left] > 0:
            cnt[left] -= 1
        num -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)
from itertools import count
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
mlmis = lambda: [-int(x) for x in input().split()]
INF = float('inf')
def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#


def main():
    N, K = mis()
    A = lmis()
    B = [None]*(N+1)
    s = 0
    for i, a in enumerate([0] + A):
        s += a
        B[i] = s
    ans = 0
    for length in range(1, min(len(A), K+1)):
        for left in count():
            if left + length > N:
                break
            if (B[left+length]-B[left]) % K == length:
                ans += 1
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
def num():
    return int(input())

def nums():
    return list(map(int,input().split(" ")))

#A
"""
date = {"SUN":7,"MON":6,"TUE":5,"WED":4,"THU":3,"FRI":2,"SAT":1}
print(date[input()])
"""
#B
"""
import string as s
N,S = num(),input()
letters = s.ascii_uppercase
ans = ""
for i in S:
    ans += letters[(letters.index(i)+N)%len(letters)]
print(ans)
"""

#C ???
"""
A,B,X = nums()
N = int(X / A)
keta = len(str(N))
ans = 0
if A * N + B * keta <= X:
    ans = N
else:
    while A * N + B * keta > X:
        N -= 1
        keta = len(str(N))
    ans = N
if ans > 1000000000:ans = 1000000000
if ans < 0:ans = 0
print(ans)
"""
#D 木って何　飛ばすわ
#E
import pprint as p
N,K = nums()
A = nums()
cursor = 0
ans = {}
def cond(bubun_):
    global K
    return (sum(bubun_) % K) == len(bubun_)
for i in range(N):
    for j in range(N):
        if cursor + j > N:break
        bubun = A[cursor:cursor+j]
        if cond(bubun) and len(bubun):
            ans[(cursor,cursor+j)] = 0
            #print(cursor,"~",cursor+j,":",bubun)
    cursor += 1
print(len(ans))

Submission status: Wrong Answer

Solution code:

N, K = list(map(int, input().split()))
An = list(map(int, input().split()))
An = [elem//K for elem in An]
count = 0
for i in range(len(An)-1):
    for j in range(1, len(An)):
        if i - j == sum(An[i:j])//K:
            count += 1

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
c = 0
for i in range(1, n):
    for j in range(n - i + 1):
        sum = 0
        for p in range(j, j + i):
            sum += a[p]
        if sum % k == i:
            c += 1
print(c)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
count = 0
for i in range(1, N):
    for j in range(N-i+1):
        B = A[j:i+j]
        if sum(B) % K == len(B):
            count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N, K = list(map(int, input().split()))
An = list(map(int, input().split()))
An = [elem//K for elem in An]
count = 0
for i in range(len(An)-1):
    for j in range(1, len(An)):
        if i - j == sum(An[i:j]):
            count += 1

Submission status: Wrong Answer

Solution code:
#E
import numpy as np
N,K=map(int,input().split())
A=np.array([int(x) for x in input().split()])
A=A%K

count=0
for i in range(N-1):
  for j in range(i+1,N+1):
    if sum(A[i:j])%K==j-i:
      count +=1
    if j-i>K:
      break
print(count)

Submission status: Wrong Answer

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

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)):
    for s in range(0, len(As)-l + 1):
        if As[s:s+l].sum() % K == l:
            c += 1

print(c)

Submission status: Wrong Answer

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

cnt = {0:1}

ans = 0

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

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys

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 = [[] for _ in range(K)]
    for i in range(N + 1):
        indices[csum[i]].append(i)

    ans = 0
    for vec in indices:
        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: Time Limit Exceeded

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 i in range(K):
            if not i in u: continue
            c = u[i]
            ans += c*(c-1)//2
        
        print(ans)
            
    


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

ans = 0
sums = [0] + sums
for i in range(n+1):  # 2e5 ** 2 なので TLE...
    for j in range(i+1, n+1):
        hoge = (sums[j] - sums[i]) % k
        ans += (hoge == j - i)
print(ans)

Submission status: Time Limit Exceeded

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():
    for i in range(len(ls)):
        for j in range(i+1, len(ls)):
            if ls[j] - ls[i] < K:
                ans += 1
            else:
                break
        
print(ans)

Submission status: Time Limit Exceeded

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

moda=[]

for aa in a:
    moda.append(aa%k)

cnt=0
for i in range(n):
    if moda[i]==1:
        cnt+=1
        #print(a[i])
    tmp=moda[i]
    for j in range(1,n-i):
        tmp+=moda[i+j]
        tmp=tmp%k
        #print(tmp)
        if j+1==tmp:
            #print(a[i:i+j+1])
            cnt+=1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
r = [0 for _ in range(n+1)]
for i in range(n):
    r[i+1] = (r[i] + a[i]) % k
ans = 0
for i in range(1,n+1):
    for j in range(n-i+1):
        if (r[i+j] - r[j]) % k == i:
            ans += 1
            #print(sum())

print(ans)

Submission status: Time Limit Exceeded

Solution code:

import collections
n,k  = map(int,raw_input().split(' '))
elems = map(int ,raw_input().split(' '))

c = 0
dp = []
for e in elems:
	dp = [(el+e)%k for el in dp] + [e % k]
	for j in range(len(dp)):
		if dp[-1-j] == j+1:
			c +=1
print c

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(lambda x:(int(x)-1)%k,input().split()))
a_=0
cs_a=[0]
for ai in a:
  a_+=ai
  a_%=k
  cs_a.append(a_)
jouyo=[[]for _ in range(k)]
for i,cs in enumerate(cs_a):
  jouyo[cs].append(i)
import bisect
def func(arg):
  if len(arg)<2:
    return 0
  ret=0
  for i in range(len(arg)):
    idx=bisect.bisect_right(arg,arg[i]+k-1)
    ret+=idx-i-1
  return ret
ans=0
for j in jouyo:
  ans+=func(j)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

n,k = map(int,readline().split())
if k == 1:
  print(0)
  exit()
  
a = np.array([0]+[int(i) for i in readline().split()])
np.cumsum(a,out=a)
a = list(a)
a = [(ai-i)%k for i,ai in enumerate(a)]

from collections import Counter,deque
c = Counter({a[0]:1})
d = deque([a[0]])
ans = 0
cnt = 1
for j,aj in enumerate(a[1:]):
  ans += c[aj]
  d.append(aj)
  c.update({aj:1})
  cnt += 1
  if cnt >= k:
    p = d.popleft()
    c.update({p:-1})
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

n,k = map(int,readline().split())
if k == 1:
  print(0)
  exit()
  
a = np.array([0]+[int(i) for i in readline().split()])
np.cumsum(a,out=a)
  
a = [(ai-i)%k for i,ai in enumerate(a)]

from collections import Counter,deque
c = Counter({a[0]:1})
d = deque([a[0]])
ans = 0
cnt = 1
for j,aj in enumerate(a[1:]):
  ans += c[aj]
  d.append(aj)
  c.update({aj:1})
  cnt += 1
  if cnt >= k:
    p = d.popleft()
    c.update({p:-1})
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

accmodk = [0]*(n+1)

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

from collections import defaultdict
amp = defaultdict(list)

for i in range(n+1):
    key = (accmodk[i] - i)%k
    amp[key].append(i)

ans = 0
import itertools
for v in amp.values():
    right=0
    l = len(v)
    for left in range(l):
        right=left+1
        while right<l and v[right] - v[left] < k:
            right+=1
            ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

accmodk = [0]*(n+1)

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


from collections import defaultdict
amp = defaultdict(list)

for i in range(n+1):
    key = (accmodk[i] - i)%k
    amp[key].append(i)

ans = 0
import itertools
for v in amp.values():
    for l,r in itertools.combinations(v, 2):
        if r-l<k:
            ans+=1

print(ans)