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:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size

    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        i = 1
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i + step <= self.size and s + self.bit[i + step - 1] < x:
                i += step
                s += self.bit[i - 1]
            step >>= 1
        return i

    def __len__(self):
        return self.size
#solve
def solve():
    n, k = LI()
    a = LI_()
    ab = a[::1]
    a[0] = a[0] % k
    for i in range(n - 1):
        a[i + 1] = (a[i] + a[i + 1]) % k
    Bit = BinaryIndexedTree(k + 1)
    ans = 0
    d = deque([0])
    Bit.add(0, 1)
    for x, i in enumerate(a):
        d.append(i)
        if len(d) == k+1:
            x = d.popleft()
            Bit.add(x, -1)
        ans += Bit.sum(i) - Bit.sum(i - 1)
        Bit.add(i, 1)
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()

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):
    a = [A[i]]
    lsum = a[0]
    if lsum % K == len(a):
        ans += 1
    for j in range(i + 1, N):
        a.append(A[j])
        lsum += A[j]
        if lsum % K == len(a):
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import array

n, k = map(int, input().split())
inputs = map(int, input().split())
a_array = array.array("L")
a_array.append(0)
for a in inputs:
    a_array.append((a_array[-1] + a - 1) % k)

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

Submission status: Time Limit Exceeded

Solution code:


def get_input():

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

    return N, K, numbers


def main():

    N, K, numbers = get_input()
    numbers = list(numbers)

    sum_numbers = [sum(numbers[:i]) for i in range(len(numbers) + 1)]

    sj = {i:0 for i in range(K)}
    search = []
    res = 0

    for j, s in enumerate(sum_numbers):
        r = (s - j) % K
        res += sj[r]
        sj[r] += 1

        search.append(r)
        if len(search) == K:
            sj[search[0]] -= 1
            search = search[1:]


    print(res)


main()

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

Submission status: Time Limit Exceeded

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 = dict()
for i in range(min(K,N+1)):
    if B[i] not in tbl.keys():
        tbl[B[i]] = 1
    else:
        tbl[B[i]] += 1
        ans += tbl[B[i]] - 1
for i in range(K, N+1):
    tbl[B[i-K]] -= 1
    if B[i] not in tbl.keys():
        tbl[B[i]] = 1
    else:
        tbl[B[i]] += 1
        ans += tbl[B[i]] - 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input().split()
L = input().split()

N = int(S[0])
K = int(S[1])
A = list(L)
i = 0
j = 0
sum = 0
prin = 0

while i < len(A):
    while j < len(A):
        sum += int(A[j])
        if sum%K == j+1-i:
            prin += 1
        j += 1
    i += 1
    j = i
    sum = 0
print(prin)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

def main():
    N,K=map(int,input().split())
    ans=0
    
    A=list(map(int,input().split()))
    A=[A[j]%K for j in range(N)]
    ans += A.count(1)
    
    B=[(A[j]+A[j+1])%K for j in range(N-1)]
    ans += B.count(2)
    
    for i in range(2,min(K+1,N)):
        C = [(B[j]+B[j+1]-A[j+1])%K for j in range(N-i)]
        ans += C.count(i+1)
        A = B
        B = C
        
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    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]

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

    C=[[] for _ in range(max(n+1,k))]
    for i in range(n+1):
        if(S[i]>=max(n+1,k)): continue
        C[S[i]].append(i)

    ans=0
    for d in range(max(n+1,k)):
        n=len(C[d])
        if(n<=1): continue
        r=0
        for l in range(n):
            while(r+1<n and C[d][r+1]-C[d][l]<k):
                r+=1
            ans+=r-l
            if(r==l): r+=1
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a_array = list(map(lambda s: int(s) % k, input().split()))
count = 0
for i in range(n):
    for j in range(i, n):
        stock = 0
        for m in range(i, j + 1):
            stock += a_array[m]
            stock %= k
        if stock == j + 1 - i:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools

def read():
    N, K = list(map(int, input().strip().split()))
    A = list(map(int, input().strip().split()))
    return N, K, A


def solve(N, K, A):
    S = [0 for _ in range(N+1)]
    for i in range(N):
        S[i+1] = (S[i] + A[i]) % K
    count = 0
    for j in range(N+1):
        for i in range(j):
            if (S[j] - S[i]) % K == (j - i):
                count += 1
    return count
    
if __name__ == '__main__':
    inputs = read()
    output = solve(*inputs)
    print("%d" % output)

Submission status: Time Limit Exceeded

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

A=list(map(int,input().split()))
A=[A[j]%K for j in range(N)]
ans += A.count(1)

B=[(A[j]+A[j+1])%K for j in range(N-1)]
ans += B.count(2)

for i in range(2,min(K+1,N)):
    C = [(B[j]+B[j+1]-A[j+1])%K for j in range(N-i)]
    ans += C.count(i+1)
    A = B
    B = C
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n,k=MI()
    aa=LI()
    cs=[0]*(n+1)

    s=0
    for i,a in enumerate(aa,1):
        s+=a%k
        cs[i]=s-i
    #print(cs)
    ans=0
    for r in range(n+1):
        for l in range(max(0,r-k+1),r):
            if (cs[r]-cs[l])%k==0:
                #print(l,r)
                ans+=1
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

def main():
    N,K = map(int, input().split())
    As = [int(s) for s in input().split()]
    As_sum = [0]

    #累積和を用意する
    for i in range(N):
        As_sum.append(As[i] + As_sum[i])
    
    #累積和のAs_sum[index]から、s0,s1,s2...si-1までをループしてそれぞれKで割った余りは、要素数index - iと等しいかどうか？
    result = 0
    for i, s in enumerate(As_sum):
        for ii in reversed(range(i)):
            if i - ii > K:
                break
            if ((s - As_sum[ii]) % K) == i - ii:
                result += 1
    print(result)





if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, k, v):
        '''
        あたいの初期化
        '''
        self.data[k+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        list[k]=aに更新する。
        更新ぶんをrootまで更新
        '''
        k += self.n-1
        self.data[k] = a

        while k > 0:
            k = (k-1)//2
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret


N, K = map(int, input().split())
A = list(map(int, input().split()))
Seg = SegmentTree(N, lambda a, b: (a+b) % K, 0)
for i, a in enumerate(A):
    Seg.set(i, a)
Seg.build()

ans = 0
for l in range(N):
    for r in range(l+1, N+1):
        if Seg.query(l, r) == r-l:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = map(int, input().split())
A = [0]
B = [int(x) for x in input().split()]
for x in B:
    A.append(x)
cumsum = np.cumsum(np.array(A))%K
c = 0
for n in range(N+1):
    for m in range(n+1, min(n+1+K,N+1)):
        if (cumsum[m]-cumsum[n])%K == m-n:
            c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, K = map(int,input().split())
A = list(map(int,input().split()))
count = 0
for n, m in itertools.product(range(len(A)+1),range(len(A)+1)):
    if n >= m:
        continue
    else:
        if sum(A[n:m]) % K == m-n:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, K = inpl()
A = inpl()
if K == 1:
    print(0)
    exit()
C = [[] for _ in range(K)]
m = 0
C[0].append(-1)
for i in range(N):
    m = (m + A[i] - 1) % K
    C[m].append(i)

ans = 0
for k in range(K):
    L = len(C[k])
    if L <= 1:
        continue
    l = r = 0
    while r < L:
        r = bisect_left(C[k], C[k][l]+K-1, l)
        if r == L:
            ans += (L-l)*(L-l-1)//2
        else:
            ans += r - l - 1
            if C[k][r] == C[k][l]+K-1:
                ans += 1
            l += 1
print(ans)

Submission status: Time Limit Exceeded

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


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

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

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

  print(count)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

def main():
    N,K = map(int, input().split())
    As = [int(s) for s in input().split()]
    As_sum = [0]

    #累積和を用意する
    for i in range(N):
        As_sum.append(As[i] + As_sum[i])
    
    #累積和のAs_sum[index]から、s0,s1,s2...si-1までをループしてそれぞれKで割った余りは、要素数index - iと等しいかどうか？
    result = 0
    for i, s in enumerate(As_sum):
        for ii in range(i):
            if i - ii > K:
                continue
            if ((s - As_sum[ii]) % K) == i - ii:
                result += 1
    print(result)





if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
r = 0
s = {0: [0]}
for i in range(n):
    r = (r + a[i] - 1) % k
    s[r] = s.get(r, []) + [i + 1]
ret = 0
for key in s:
    a = s[key]
    en = 0
    for st in range(len(a)):
        while en < len(a) and a[en] - a[st] < k:
            en += 1
        ret += en - st - 1
print(ret)

Submission status: Time Limit Exceeded

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

count = 0
for a in range(0,N):
    for b in range(a+1,N+1):
        if K <= b-a: break
        if (sum_A[b] - sum_A[a])%K == b-a:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    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]

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

    C=[[] for _ in range(k)]
    for i in range(n+1):
        C[S[i]].append(i)

    ans=0
    for d in range(k):
        n=len(C[d])
        if(n<=1): continue
        r=0
        for l in range(n):
            while(r+1<n and C[d][r+1]-C[d][l]<k):
                r+=1
            ans+=r-l
            if(r==l): r+=1
    print(ans)
resolve()

Submission status: Time Limit Exceeded

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

sumA = [0]

for i in range(N):
    if i == 0:
        sumA.append(A[i] % K)
    else:
        sumA.append((sumA[-1] + A[i]) % K)
ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
s = [0 for _ in range(n + 1)]
for i in range(n):
    s[i + 1] = s[i] + a[i]

ans = 0
for i, si in enumerate(s[:-1]):
    for j in range(i, min(i + k, n)):
        if (s[j + 1] - si) % k == j - i + 1:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
c=0
S=[0 for _ in range(n+1)]
for i in range(n):
  S[i+1]=S[i]+A[i]
for l in range(n):
  for r in range(l+1,n+1):
    if r-l==k:
      break
    elif (S[r]-S[l])%k==r-l:
      c+=1
print(c)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
chache = []
tmp = []
answer = 0
for i in range(len(a)):
    d = 1
    pre = 0
    z = []
    for b in a[i:]:
        z.append(b)
        if z in chache:
            pre = tmp[chache.index(z)]
            answer += pre==d
        else:
            c = b % k
            pre = (pre + c) % k
            chache.append(pre)
            tmp.append(pre==d)
            answer += pre==d
        d += 1

print(answer)

Submission status: Time Limit Exceeded

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

count = 0
for a in range(0,N):
    for b in range(1,N+1):
        if K <= b-a: break
        if a!=b and (sum_A[b] - sum_A[a])%K == b-a:
            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
rem=list(list(0 for _1 in range(n)) for _2 in range(n))
rem[0][0]=a[0]%k
if rem[0][0]==1:
  count+=1
for i in range(1,n):
  rem[0][i]=(rem[0][i-1]+a[i])%k
  if rem[0][i]==i+1:
    count+=1
  for j in range(1,i+1):
    rem[j][i]=(rem[j-1][i]-a[j-1])%k
    if rem[j][i]==i+1-j:
      count+=1
print(count)

Submission status: Time Limit Exceeded

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

for i in range(n):
    tmp += a[i]
    sums.append(tmp)

for i in range(1, n + 1):
    tmp1 = sums[i]
    for j in range(i):
        if (tmp1 - sums[j]) % k == i - j:
            count += 1

print(count)

Submission status: Time Limit Exceeded

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

A=list(map(int,input().split()))
for j in range(N):
    A[j] %= K
ans += A.count(1)

B=[]
for j in range(N-1):
    B.append((A[j]+A[j+1])%K)
ans += B.count(2)

for i in range(2,min(K+1,N)):
    C=[]
    for j in range(N-i):
        C.append((B[j]+B[j+1]-A[j+1])%K)
    ans += C.count(i+1)
    A = B
    B = C
    
print(ans)

Submission status: Time Limit Exceeded

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


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

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

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

  print(count)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

for i in range(n):
    tmp += a[i]
    sums.append(tmp)

for i in range(1, n + 1):
    for j in range(i):
        if (sums[i] - sums[j]) % k == i - j:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = input().split()
N = int(N)
K = int(K)
A = input().split()
A = np.hstack([int(A[i]) for i in range(N)])

out = 0
for i in range(N):
  for j in np.arange(i+1, N+1):
    data = np.sum(A[i:j])
    if (j - i) == int(data % K):
      out += 1

print(out)

Submission status: Time Limit Exceeded

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

moda = []
for i in a:
    moda.append(i%k)

ans = 0
for i in range(n):
    #print(f'i : {i}')
    tem = 0
    num = 0
    for j in range(i,n):
        #print(f'j : {j}')
        tem += a[j]
        num += 1
        if tem%k == num:
            #print(f'i : {i}')
            #print(f'num : {num}')
            ans +=1


print(ans)

Submission status: Time Limit Exceeded

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

sumA = [0]

for i in range(N):
    if i == 0:
        sumA.append(A[i])
    else:
        sumA.append(sumA[-1] + A[i])
ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

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

count = 0
for a in range(0,N):
    for b in range(1,N+1):
        if a!=b and (sum_A[b] - sum_A[a])%K == b-a:
            count += 1

print(count)

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())))
A %= K

ans = 0
sum_from_right = np.zeros(N)

for i in range(N):
    sum_from_right[:i+1] += A[i]
    sum_from_right %= K
    ans += i + 1 - np.count_nonzero(sum_from_right[:i+1] - np.arange(i+1, 0, -1))

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int ,input().split()))
A = [A[i]%K for i in range(N)]
t = 0
AA = [0]
for i in range(N):
	t += A[i]
	AA.append(t)
ans = 0
for i in range(1,min(K,N+1)):
	for j in range(i,N+1):
		if (AA[j] - AA[j-i]) % K == i:
			ans += 1

print(ans)

Submission status: Time Limit Exceeded

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):
        Rwj = Rw[j]
        if Rwj < Rw[i]:
            Rwj = Rwj + K
        if Rwj - Rw[i] == j - i:
            c += 1
print(c)

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(N):
    for j in range(i+1, N+1):
        if sum(A[i:j])%K==j-i:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import sys
f = sys.stdin
n, k = map(int, f.readline().split(' '))
a = list(map(int, f.readline().split(' ')))

prefix = [0] * (n+1)
for i in range(1, n+1):
    prefix[i] = prefix[i-1] + a[i-1]

def sum_fragment(p, q, prefix):
    return prefix[q+1] - prefix[p]

count = 0
for i in range(n):
    for j in range(i, n):
        tmp = sum_fragment(i, j, prefix)
        if tmp % k == (j - i + 1):
            count += 1
print(count)

Submission status: Time Limit Exceeded

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

for i in range(n):
    tmp += a[i]
    sums.append(tmp)

if sums[0] % k == 1:
    count += 1

for i in range(1, n):
    if sums[i] % k == i + 1:
        count += 1
    for j in range(i):
        if (sums[i] - sums[j]) % k == i - j:
            count += 1

print(count)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

ans = 0
T = min(N,K)
for l in range(1,T+1):
    f = sum(A[:l])
    if f % K == l:
        ans += 1
    for j in range(l,N):
        f = f - A[j-l] + A[j]
        if f % K == l:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

A=list(map(int,input().split()))
for j in range(N):
    A[j] %= K
ans += A.count(1)

B=[]
for j in range(N-1):
    B.append((A[j]+A[j+1])%K)
ans += B.count(2)

for i in range(2,N):
    C=[]
    for j in range(N-i):
        C.append((B[j]+B[j+1]-A[j+1])%K)
    ans += C.count(i+1)
    A = B
    B = C
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
import os
import os
import sys
from collections import deque, defaultdict

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, K = list(map(int, sys.stdin.buffer.readline().split()))
A = list(map(int, sys.stdin.buffer.readline().split()))

A = np.array(A, dtype=int) % K

if K == 1:
    print(0)
    exit()
if K == 2:
    ans = (A % 2 == 1).sum()
    print(ans)
    exit()

def test():
    ans = 0
    for i, a in enumerate(A):
        if a % K == 1:
            ans += 1
        j = 1
        while i - j >= 0 and j + 1 < K:
            if (sum(A[i - j: i]) + a) % K == j + 1:
                ans += 1
            j += 1
    print(ans)


# 和-長さ を覚える
counts = defaultdict(int)
hist = deque()
offset = 0
ans = 0
for i, a in enumerate(A):
    if a % K == 1:
        ans += 1
    ans += counts[(K - a + 1 - offset) % K]
    offset += a - 1
    offset %= K
    counts[(a - 1 - offset) % K] += 1
    if len(hist) >= K - 2:
        counts[hist.popleft()] -= 1
    hist.append((a - 1 - offset) % K)
    # print(ans, counts, offset)
print(ans)
# test()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, K = map(int, input().split())
A = np.array([0] + list(map(int, input().split())))
mod = A % K
mod_cum = mod.cumsum()
#print(mod_cum)
answer = 0
for i in range(1, N+1):
    #print(i, (mod_cum[i:] - mod_cum[:-i]) % K)
    answer += ((mod_cum[i:] - mod_cum[:-i]) % K == i).sum()
#Anをチェック
print(answer)

Submission status: Time Limit Exceeded

Solution code:
def get_input():

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

    return N, K, numbers


def main():

    N, K, numbers = get_input()

    numbers = [a % K for a in numbers]

    res = 0
    for k in range(1, K):
        for i in range(N - k + 1):
            if sum(numbers[i : i + k]) % K == k:
                res += 1

    print(res)


main()

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a=[x%k for x in a]
a=tuple(a)
ans=a.count(1)
for l in range(2,n+1):
  for i in range(n-l+1):
    s=sum(a[i:i+l])%k
    if s==l:
      ans+=1
      #print(a[i:i+l])
print(ans)

Submission status: Time Limit Exceeded

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

A = input().split()


def create_all_sub_arrays(A):
    length = len(A)
    return [A[i:j+1] for i in range(length) for j in range(i, length)]


# def find_digits_sum(A):
#     return [sum(list(map(int, s))) for s in A]
#

all_substrings = create_all_sub_arrays(A)
counter = 0

for substring in all_substrings:
    len_s = len(substring)
    digits_sum = sum(list(map(int, substring)))

    if digits_sum % K == len_s:
        counter += 1

print(counter)

Submission status: Time Limit Exceeded

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

def sliding(n, xs):
    for i in range(len(xs) - n + 1):
        yield xs[i:i+n]

count = 0
for i in range(1, N + 1):
    for xs in sliding(i, A):
        if sum(xs) % K == len(xs):
            count += 1
print count

Submission status: Time Limit Exceeded

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
answer = 0
for i in range(len(a)):
    d = 1
    pre = 0
    for b in a[i:]:
        c = b % k
        pre = (pre + c) % k
        answer += (pre == d)
        d += 1

print(answer)

Submission status: Time Limit Exceeded

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

for i in range(n):
    tmp = 0
    length = 0
    for j in range(i, n):
        tmp += a[j]
        length += 1
        num_list.append([tmp, length])

for ans in num_list:
    if ans[0] % k == ans[1]:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
s = [0 for _ in range(n + 1)]
for i in range(n):
    s[i + 1] = s[i] + a[i]

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

def main():
    N,K = map(int, input().split())
    As = [int(s) for s in input().split()]
    As_sum = [0]

    #累積和を用意する
    for i in range(N):
        As_sum.append(As[i] + As_sum[i])
    
    #累積和のindex+1から、s0,s1,s2...si-1までをループしてKで割った時、要素数index+1 - iと等しいかどうか？
    result = 0
    for i, s in enumerate(As_sum):
        for ii in range(i):
            if ((s - As_sum[ii]) % K) == i - ii:
                result += 1
    print(result)




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = map(int, input().split())
A = [0]
B = [int(x) for x in input().split()]
for x in B:
    A.append(x)
cumsum = np.cumsum(np.array(A))
c = 0
for n in range(N+1):
    for m in range(n+1, N+1):
        if (cumsum[m]-cumsum[n])%K == m-n:
            c += 1
print(c)