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

ans=0
right=1
array_sum = 0
for left in range(n+1):
    right = left+1
    while right<n+1 and right-left < k :
        if (accmodk[right] - accmodk[left])%k==right-left:
            ans+=1
        right+=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()))

from itertools import accumulate
acc = [0] + a
acc = list(accumulate(acc))

accmodk = [0]*(n+1)
for i in range(n+1):
    accmodk[i] = acc[i]%k

ans=0
right=1
array_sum = 0
for left in range(n+1):
    right = left+1
    while right<n+1 and right-left < k :
        if (accmodk[right] - accmodk[left])%k==right-left:
            ans+=1
        right+=1
print(ans)

Submission status: Time Limit Exceeded

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

N, K = map(int, input().strip().split(" "))
A = np.zeros(N + 1, dtype=np.int32)
A[1:] = np.array(list(map(int, input().strip().split(" "))), dtype=np.int32)
A = np.cumsum(A) - np.array(range(N + 1), dtype=np.int32)

rem_count = {}
rem_count[0] = 1
ans = 0
for i in range(1, N + 1):
    if i - K >= 0:
        rem_count[A[i - K] % K] -= 1
    if A[i] % K in rem_count:
        ans += rem_count[A[i] % K]
        rem_count[A[i] % K] += 1
    else:
        rem_count[A[i] % K] = 1

print(ans)

Submission status: Time Limit Exceeded

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

N, K = map(int, input().strip().split(" "))
A = np.zeros(N + 1, dtype=np.int32)
A[1:] = np.array(list(map(int, input().strip().split(" "))), dtype=np.int32)
A = np.cumsum(A) - np.array(range(N + 1), dtype=np.int32)

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

print(ans)

Submission status: Time Limit Exceeded

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

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

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

print(ans)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

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

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

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

print(ans)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,K=map(int,input().split())
s = np.array([int(x) for x in input().split()]).cumsum()
count=0

for j in range(0,N):
    for d in range(0,K):
        if d == 0:
            if s[j]%K == j+1:
                count+=1
            continue
        i = j-d
        if i < 0:
            break
        if (s[j] -s[i])%K == j-i:
            count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
from collections import Counter, defaultdict
import copy
n,k = map(int, input().split())
a = list(map(int, input().split()))
a = [0] + list(accumulate([(i-1) % k for i in a]))
a = [i % k for i in a]
ans = 0
start = defaultdict(int)
start[0] += 1
maps = [start]
for i in a[1:]:
  now = maps[-1].copy()
  now[i] += 1
  maps.append(now)
for i in range(n):
  v = a[i]
  ans += maps[min(n,i+k-1)][v]-maps[i][v]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# int(input()) # 入力が1つ
n, k = map(int, input().split()) # 入力が複数
nums = [int(i) for i in input().split()] # 配列で数字

nums = [0] + nums
for i in range(n):
    nums[i + 1] += nums[i]
ans = 0
for i in range(n + 1):
    for j in range(i + 1, n + 1):
        left = nums[i]
        right = nums[j]
        if (left - i) % k == (right - j) % k and j - i < k:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import collections
    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]

    table = collections.defaultdict(set)
    for i, x in enumerate(s):
        table[x % K].add(i)
    ans = 0
    for x in table:
        for y in table:
            if x == y:
                continue
            else:
                for z in table[x]:
                    k = (x-y) % K
                    if z-k in table[y]:
                        ans += 1
                    k = (y-x) % K
                    if z+k in table[y]:
                        ans += 1
    print(ans//2)
main()

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = True

n, k = MAP()
a = LIST()
ans = 0
ss = 0
for i in range(1, n + 1): #要素の個数
    s = (ss + a[i - 1]) % k
    ss = s
    if s == i:
        ans += 1
    for j in range(1, n - i + 1): #開始
        s += a[j + i - 1] - a[j - 1]
        s %= k
        if s == i:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, k = map(int, input().split())
a = list(map(int, input().split()))
a = np.array(a) % k
cumsum = np.cumsum(a)
cumsum = np.hstack([[0], cumsum])

count = 0
for l in range(len(cumsum)):
    for r in range(l + 1, len(cumsum)):
        s = cumsum[r] - cumsum[l]
        if r - l == s % k:
            count += 1
#             print(cumsum[r] - cumsum[l])
print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate 
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
S=list(accumulate(A))
S.insert(0,0)

L=[ (s-i)%k  for i,s in enumerate(S)]
def f(l):
    return sum([x*(x-1)//2 for x in l])

from collections import Counter

ans=0
for i in range(n):
    #print(L[i+1:i+k],L[i])
    ans += (L[i+1:i+k].count(L[i]))
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import copy
n, k = map(int, input().split())
a = list(map(lambda x:int(x)%k, input().split()))
a2 = copy.deepcopy(a)
b = 0
c = 0
for i in range(1,min(n,k-1)+1):
  b += sum([1 for j in a2[:(n-i+1)] if j==i])
  if i < min(n,k-1):
    a2 = [(a[i+j]+a2[j])%k for j in range(n-i)]
print(b)

Submission status: Time Limit Exceeded

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

b = 0
c = 0
for i in range(1,min(n,k-1)+1):
  c = (c + a[i-1])%k
  c2 = c
  for j in range(n-i+1):
    c2 = c2%k
    if c2 == i:
      b += 1
    if i+j < n:
      c2 += a[i+j] - a[j]
print(b)

Submission status: Time Limit Exceeded

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

b = 0
c = 0
for i in range(1,min(n,k-1)+1):
  c += a[i-1]
  c2 = c
  for j in range(n-i+1):
    if c2%k == i:
      b += 1
    if i+j < n:
      c2 += a[i+j] - a[j]
print(b)

Submission status: Time Limit Exceeded

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

b = 0
c = 0
for i in range(1,min(n,k-1)+1):
  c += a[i-1]
  c2 = c
  for j in range(n-i+1):
    if c2%k == i:
      b += 1
    if i+j < n:
      c2 += a[i+j] - a[j]
print(b)

Submission status: Time Limit Exceeded

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):
  # 要素数の指定
  j = 1
  while j <= n-i:
    sum = 0
    for l in range(j):
      sum += a[i+l]
    if sum % k == j:
      count += 1
    j += 1
      
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

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

N, K = lr()
N += 1
A = np.array([0] + lr())
A %= K
Acum = A.cumsum()
answer = 0
for i in range(N):
    length = N-1-i
    B = (Acum[i+1:] - Acum[i]) % K - np.arange(1, length+1)
    x = len(B) - np.count_nonzero(B)
    answer += x

print(answer)
# 32

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
S = [0] + list(map(int,input().split()))

for i in range(1,N+1):
    S[i] += S[i-1]
for i in range(N+1):
    S[i] -= i
    S[i] %= K
cnt = 0
for i in range(N):
    cnt += S[i+1:min(N+1,i+K)].count(S[i])
print (cnt)

Submission status: Time Limit Exceeded

Solution code:
nagasa,waru = map(int,input().split())
value = input().split()
pairTotal = 0
count = 0
result = 0
for i in range(nagasa):
  for n in range(i,nagasa):
    pairTotal += int(value[n])
    count += 1
    if pairTotal % waru == count:
      result += 1
  count, pairTotal = 0,0
print(result)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

def main():
    dic = {}
    for i in range(1,N + 1):
        A[ i ] += A[ i - 1 ]
    for j in range(N + 1):
        if (A[j] - j)%K in dic:
            dic[(A[j] - j)%K].append(j)
        else:
            dic[(A[j] - j)%K] = [j]

    ans = 0
    
    for i in range(1,N + 1):
        tmp = dic[(A[i] - i)%K]
        for x in tmp:
            if i - K < x and x < i:
                ans += 1
    print(ans)
    return 

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N, K = map(int, input().split())
    A = [int(x) % K for x in input().split()]

    #print(N, K, A)

    s = 0
    S = []
    for a in A:
        s = (s + a) % K
        S.append(s)

    ans = 0

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

    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

#print(N, K, A)

s = 0
S = []
for a in A:
    s = (s + a) % K
    S.append(s)

ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

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

SUM = [0] # banpei
for Ai in A:
    SUM.append(Ai + SUM[-1])
    
total = 0
#ret = []
for i in range(1, len(SUM)):
    for j in range(i, len(SUM)):
        mysum = SUM[j] - SUM[i - 1]
        mynum = j - i + 1
        if mysum % K == mynum:
            total += 1
#            ret.append((i,j))
            
print(total)
#print(SUM)
#print(ret)

Submission status: Time Limit Exceeded

Solution code:
from itertools import *
from collections import defaultdict
def ints():
  return [int(x) for x in input().split()]
def readi():
  return int(input())

N, K = ints()
A = ints()
S = [0] + list(accumulate(A))

def f(i):
  return (S[i]-i)%K

s = 0
for j in range(1, N+1):
  fj = f(j)
  for i in range(max(0, j-K+1), j):
    if f(i)==fj:
      s += 1
print(s)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
a = inl()
h =defaultdict(int)
b = [0]*(n+1)
s = [0]*(n+1)
for i in range(n):
    s[i+1] = s[i]+a[i]
    b[i+1] = (s[i+1]-i-1)%k
ddprint(s)
ddprint(b)
acc = 0
for i in range(n+1):
    if i>=k:
        h[b[i-k]] -= 1
    acc += h[b[i]]
    h[b[i]] += 1
    ddprint("i {} acc {} h {}".format(i,acc,h))
print(acc)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()
n,k = map(int,input().split())
l = [int(i) for i in input().split()]
c = 0

def judge(l_,k):
    return len(l_) == sum(l_)%k

for i in range(n):
    for idx in range(n-i):
        if judge(l[idx:idx+i+1],k):
            c += 1

print(c)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

# input
n, k = map(int, list(input().split()))
a = list(map(lambda x: x%k, map(int, list(input().split()))))

# process
ans = a.count(1)

for i in range(n):
    t = a[i]

    j = i+1
    while j < n:
        t += a[j]
        if t%k == j-i+1:
            ans += 1
        j += 1

# output
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

# input
n, k = map(int, list(input().split()))
a = list(map(lambda x: x%k, map(int, list(input().split()))))

# process
ans = a.count(1)

for i in range(n-1):
    i += 2
    for j in range(n-i+1):
        if reduce(lambda x, y: x+y, a[j:i+j]) % k == i:
            ans += 1

# output
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

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

# process
ans = 0

for i in a:
    if i%k == 1:
        ans += 1

for i in range(n-1):
    i += 2
    for j in range(n-i+1):
        if reduce(lambda x, y: x+y, a[j:i+j]) % k == i:
            ans += 1

# output
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
ruisekiwa=[0]
for ai in a:
    ruisekiwa.append(ruisekiwa[-1]+ai)
# print(ruisekiwa)
ans=0
for i in range(n):
    for j in range(i,n):
        array_sum=ruisekiwa[j+1]-ruisekiwa[i]
        array_num_sum=j-i+1
        if array_sum%k==array_num_sum:
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

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

A = [x-1 for x in A]
#print(A)
S = [0]

for a in A:
    S.append(a + S[-1])

#print(S)
S = [s%K for s in S]
#print(S)

ret = 0
for i, s in enumerate(S):
    B = S[max(0, i-K+1):i+1]
#    print(B)
#    print(s)
    ret += B.count(s) - 1

print(ret)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
from collections import defaultdict
import sys
input=sys.stdin.readline
N,K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
A = [0]+[i-1 for i in A]
sumA = list(accumulate(A))
sumA = [i % K for i in sumA]
x = sumA[:K]
modmap = defaultdict(int)
ans = 0
if K==1:
  print(0)
  exit()
for i in x:
    modmap[i] += 1

for i in range(K):
    t = modmap[i]
    ans += t * (t-1) // 2

for i in range(N-K+1):
    modmap[sumA[K+i]] += 1
    modmap[sumA[i]] -= 1
    ans += modmap[sumA[K+i]]-1

print(ans)

Submission status: Time Limit Exceeded

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

N, K = map(int, input().split())
arr = list(map(int, input().split()))
# for simplicity, make mod
arr = [x%K for x in arr]
n = 0

for l in range(1,K):
    for i in range(len(arr)-l+1):
        p = arr[i:i+l]
        #print(p)
        if sum(p)%K == len(p):
            n += 1
    #print("--")
print(n)
#p = arr[tail:head]

Submission status: Time Limit Exceeded

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

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

count = 0
for i in range(1,N+1):
    A[i-1] %= K
    for j in range(1,N-i+2):
        if j == 1:
            s = sum(A[j-1:j-1+ i],0) % K
        else:
            s = s - A[j-2] + A[j-2+i]
        if s % K == i:
            count += 1

print(count)

Submission status: Time Limit Exceeded

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

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

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

print(count)

Submission status: Time Limit Exceeded

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

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

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

print(count)

Submission status: Time Limit Exceeded

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

a_acum=[0]
t=0
for i in range(n):
    t+=a[i]
    a_acum.append(t)

count=0
for x in range(n):
    for y in range(x+1,n+1):
        if (a_acum[y]-a_acum[x])%k==y-x:
            count+=1
print(count)

Submission status: Time Limit Exceeded

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

ans = 0
accum = []
ids = []
for i, a in enumerate(A):
  ids.append(i+1)
  accum = list(map(lambda x:x+a, accum))
  accum.append(a)
  ans += sum([1 if s%K == idx else 0 for s, idx in zip(accum, ids[::-1])])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

ans = 0
accum = np.array([], dtype=int)
for i, a in enumerate(A):
  accum += a
  accum = np.r_[accum, a]
  ans += sum((accum % K) == np.arange(i+1, 0, -1))

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys, os
import collections

MOD = 10 ** 9 + 7

def solve(input_stream):
  N, K  = read_ints(input_stream)
  numbers = [int(i) - 1 for i in input_stream.readline().strip().split()]
  cumulative_sum = [0 for i in range(N + 1)]
  mods = [0 for i in range(K)]
  ans = 0
  for index, number in enumerate(numbers):
    cumulative_sum[index + 1] = (cumulative_sum[index] + number) % K
  queue = []
  
  for index in range(N+1):
    ans += mods[cumulative_sum[index]]
    mods[cumulative_sum[index]] += 1
    queue.append(cumulative_sum[index])
    if len(queue) == K:
      target = queue.pop(0)
      mods[target] -= 1
  return [str(ans)]

  


def read_ints(input_stream):
  return [i for i in map(int, input_stream.readline().strip().split())]

def read_int(input_stream):
  return int(input_stream.readline().strip())


if __name__ == "__main__":
    outputs = solve(sys.stdin)
    for line in outputs:
      print(line)

Submission status: Time Limit Exceeded

Solution code:
import sys, os
import collections

MOD = 10 ** 9 + 7

def solve(input_stream):
  N, K  = read_ints(input_stream)
  numbers = [i - 1 for i in map(int, input_stream.readline().strip().split())]
  cumulative_sum = [0 for i in range(N + 1)]
  mods = [0 for i in range(K)]
  ans = 0
  for index, number in enumerate(numbers):
    cumulative_sum[index + 1] = (cumulative_sum[index] + number) % K
  queue = []
  
  for index in range(N+1):
    ans += mods[cumulative_sum[index]]
    mods[cumulative_sum[index]] += 1
    queue.append(cumulative_sum[index])
    if len(queue) == K:
      target = queue.pop(0)
      mods[target] -= 1
  return [str(ans)]

  


def read_ints(input_stream):
  return [i for i in map(int, input_stream.readline().strip().split())]

def read_int(input_stream):
  return int(input_stream.readline().strip())


if __name__ == "__main__":
    outputs = solve(sys.stdin)
    for line in outputs:
      print(line)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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)):
        for j in range(0, i):
            if (K + t[i] - t[j]) % K == i - j:
                res += 1
    print(res)


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

Submission status: Time Limit Exceeded

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('').split(' '))
    A = map(int, input('').split(' '))
    main(A, K)

Submission status: Time Limit Exceeded

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

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)   #累積和

ans=0
for l in range(N):
    for r in range(l+1,min(l+K,N+1)):
        if (S[r]-S[l])%K==0:
            ans+=1
print ans

Submission status: Time Limit Exceeded

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

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


S=[0]
for i,a in enumerate(A):
        S.append(S[-1]+a)
  
ans=0

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

print ans

Submission status: Time Limit Exceeded

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

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

print(count)

Submission status: Time Limit Exceeded

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

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

            if sum(A[i:j])%K==j-i:
                count+=1

print(count)

Submission status: Time Limit Exceeded

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

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

            if sum(A[i:j])%K==j-i:
                count+=1

print(count)

Submission status: Time Limit Exceeded

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

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
def rem_of_sum(n, k, arr):
    count = 0
    for i in range(n):
        for j in range(i + 1, min(n + 1, i + k)):
            part = arr[i:j]
            if sum(part) % k == len(part):
                count += 1
    return count
 
 
n, k = map(int, input().split())
arr = list(map(int, input().split()))
print(rem_of_sum(n, k, arr))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n,k = map(int,input().split())
A = np.array(list(map(int,input().split())))

ans = 0
i = k-1
fil = np.array(range(1,i+1))
for j in range(i,n+k-1):
    cur = np.cumsum(A[j-i:j])
    if len(cur) != len(fil):
        fil = np.array(range(1,len(cur)+1))
    # print(cur)
    # print(cur%k == fil)
    ans += np.count_nonzero(cur%k == fil)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
ar = list(map(int,input().split()))
#ar = [e for e in a]
nsum = sum(ar)
count=0
if nsum%k == n:
  count += 1

for i in range(n-1,0,-1):
  #print('i={}'.format(i))
  nsum -= ar[i]
  if i >= k:
    continue
  if nsum%k == i:
    count += 1
  isum = nsum
  for j in range(n-i):
    #print('j={}'.format(j))
    isum += ar[j+i]-ar[j]
    if isum < i:
      continue
    if isum%k == i:
      count += 1
    
#print(ar)
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
ar = list(map(int,input().split()))
#ar = [e for e in a]
nsum = sum(ar)
count=0
if nsum%k == n:
  count += 1

for i in range(n-1,0,-1):
  #print('i={}'.format(i))
  nsum -= ar[i]
  if i >= k:
    continue
  if nsum%k == i:
    count += 1
  isum = nsum
  for j in range(n-i):
    #print('j={}'.format(j))
    isum += ar[j+i]-ar[j]
    if isum%k == i:
      count += 1
    
#print(ar)
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))
ar = [e%k for e in a]
nsum = sum(ar)
count=0
if nsum%k == n:
  count += 1

for i in range(n-1,0,-1):
  #print('i={}'.format(i))
  nsum -= ar[i]
  if i >= k:
    continue
  if nsum%k == i:
    count += 1
  isum = nsum
  for j in range(n-i):
    #print('j={}'.format(j))
    isum += ar[j+i]-ar[j]
    if isum%k == i:
      count += 1
    
#print(ar)
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))
ar = [e for e in a]
nsum = sum(ar)
count=0
if nsum%k == n:
  count += 1

for i in range(n-1,0,-1):
  #print('i={}'.format(i))
  nsum -= ar[i]
  if i >= k:
    continue
  if nsum%k == i:
    count += 1
  isum = nsum
  for j in range(n-i):
    #print('j={}'.format(j))
    isum += ar[j+i]-ar[j]
    if isum%k == i:
      count += 1
    
#print(ar)
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))
ar = [e%k for e in a]

count=0
for i in range(n,0,-1):
  if i > k:
    continue
  for j in range(n-i+1):
    if sum(ar[j:j+i])%k == i:
      count += 1
    
#print(ar)
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))
ar = [e%k for e in a]

count=0
for i in range(n,0,-1):
  for j in range(n-i+1):
    if sum(ar[j:j+i])%k == i:
      count += 1
    
#print(ar)
print(count)

Submission status: Time Limit Exceeded

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

n += 1
ans = 0
m = dict()
temp = 0
b = []
for i in range(min(n, k)):
    temp = (temp + a[i]) % k
    c = (temp - (i % k) + k) % k
    b.append(c)
    if c in m.keys():
        ans += m[c]
        m[c] += 1
    else:
        m[c] = 1

for i in range(k, n):
    x = i % k
    m[b[x]] -= 1
    temp = (temp + a[i]) % k
    c = (temp - (i % k) + k) % k
    b[x] = c
    if c in m.keys():
        ans += m[c]
        m[c] += 1
    else:
        m[c] = 1

print(ans)

Submission status: Time Limit Exceeded

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

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

count = 0
for i in range(n):
    width = k-1
    if i + width > n - 1:
        width = n - i
    for j in range(1, width + 1):
        if sum(a[i:i+j]) % k == j:
            count += 1

print(count)