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

def examF():
    return

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

examE()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(lambda x: int(x)-1, input().split()))
sa = [0]
for a in A:
    sa.append((sa[-1] + a) % K)
d = {0: 1}
ans = 0
for i in range(1, N+1):
    v = d.get(sa[i], 0)
    ans += v
    d[sa[i]] = v + 1
    if i >= K-1:
        d[sa[i-(K-1)]] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

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

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

cnt = defaultdict(int)
for i, c in enumerate(cumA):
    cnt[i - c % K] += 1

ans = 0
for c in cnt.values():
    ans += c * (c - 1) // 2
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

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

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

ans = 0
cnt = defaultdict(int)
cnt[0] += 1
que = deque([])

for i, c in enumerate(cumA[1:], start=1):
    if i > K:
        cnt[que.popleft()] -= 1
    ans += cnt[c % K - i]
    cnt[-(-c % K) - i] += 1
    que.append(-(-c % K) - i)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

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

ans = 0
cnt = defaultdict(int)

for i, c in enumerate(cumA):
    diff = i - c % K
    ans += cnt[diff]
    cnt[diff] += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

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

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

ans = 0
cnt = defaultdict(int)
cnt[0] += 1
que = deque([])

for i, c in enumerate(cumA[1:], start=1):
    if i > K:
        cnt[que.popleft()] -= 1

    diff = i - c % K
    ans += cnt[diff]
    cnt[diff] += 1
    que.append(diff)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import accumulate
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

A_acc = [0]+list(accumulate(A))


ans = 0
D = defaultdict(int)
for l in range(N+1):
    t = (A_acc[l]-l) % K
    ans += D[t]
    D[t] += 1


print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import accumulate
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def nC2(n):
    if n == 0:
        return 0
    return n*(n-1)//2


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

A_acc = [0]+list(accumulate(A))


D = defaultdict(int)
for l in range(N+1):
    t = (A_acc[l]-l) % K
    D[t] += 1

ans = 0
for i in range(K):
    ans += nC2(D[i])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import accumulate
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def nC2(n):
    if n == 0:
        return 0
    return n*(n-1)//2


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

A_acc = [0]+list(accumulate(A))


D = defaultdict(int)
for l in range(N+1):
    t = (A_acc[l]-l) % K
    D[t] += 1
print(D)

ans = 0
for i in range(K):
    ans += nC2(D[i])
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n,k=LI()
a=LI()
b=[k-1]
for i in range(n):
    b.append((b[-1]+a[i])%k)
b=[(b[i]-i)%k for i in range(n+1)]
ans=0
dc=defaultdict(int)
show(a)
show(b)
for i in range(n+1):
    if i>=k:
        dc[b[i-k]]-=1
    ans+=dc[b[i]]
    #if dc[b[i]]>0:show(i,a[i],dc[b[i]],ans)
    #show(i,b[i],dc)
    dc[b[i]]+=1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, input().rstrip('\n').split()))
    ls = [0] + list(map(lambda x: int(x) - 1, input().rstrip('\n').split()))
    ls = [i % k for i in list(itertools.accumulate(ls))]
    print(ls)

    d = collections.defaultdict(int)
    t = 0
    for i, x in enumerate(ls):
        t += d[x]
        d[x] += 1
        if i >= k - 1:
            d[ls[i - k + 1]] -= 1
    print(t)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, input().rstrip('\n').split()))
    ls = list(map(int, input().rstrip('\n').split()))
    cnt = 0
    for i in range(k):
        t = sum(ls[:i+1])
        if t % k == i + 1:
            cnt += 1
        for j in range(i+1, n):
            t -= ls[j-i-1]
            t += ls[j]
            if t % k == i + 1:
                cnt += 1
    print(cnt)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a=list(map(lambda x:x-1 ,a))
s=[0]
for i in range(n):
    s.append(s[-1]+a[i])
s=list(map(lambda x:x%k,s))
from collections import defaultdict
d=defaultdict(int)
d[0]=1
ans=0

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from copy import deepcopy
import itertools
input = sys.stdin.readline
# 文字列の場合は普通のinput()を使うか下を使う
# input = sys.stdin.readline().rstrip()

N, K = map(int, input().split())
A = list(map(int, input().split()))
S = [0] + list(itertools.accumulate(A))
"""
「iからjまで」--->「0からjまで」-「0から(i - 1)まで」
に分解すれば、求める条件は
(S[j] - S[i]) % K = j - i
と書ける。これを式変形して
S[j] - j = S[i] - i mod K "with j - i < K"
とすれば、次を示せばよい：

For 1 <= j <= N, count the number of j - K < i < j
such that S[j] - j = S[i] - i mod K
"""

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

d = defaultdict(int)
d[(S[0] - 0) % K] = 1

ans = 0
for j in range(1, N + 1):
    x = (S[j] - j) % K
    ans += d[x]
    d[x] += 1
    if j - K >= -1:
        y = (S[j - K + 1] - (j - K + 1)) % K
        d[y] -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from collections import Counter
n, k, *a = map(int, open(0).read().split())
a = [x % k - 1 for x in a]
a = [0] + [x % k for x in accumulate(a)]
d = Counter()
ans = 0
for l, r in zip([k] * min(k, n) + a, a):
	d[l] -= 1
	ans += d[r]
	d[r] += 1
print(ans)

Submission status: Wrong Answer

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

if K==1:
    print(0)
    exit(0)

A=list(map(int,input().split()))
S=[0]+list(numpy.cumsum(A)) #累積和
S2=[(S[i]-i)%K for i in range(N+1)]
print(A,S,S2)

d = {}
ans = 0
for j in range(1,N+1):
    if j>K-1:
        if S2[j-K] in d:
            d[S2[j-K]] -= 1
        
    if S2[j-1] in d:
        d[S2[j-1]] += 1
    else:
        d[S2[j-1]] = 1
        
    if S2[j] in d:
        ans += d[S2[j]]
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy
N,K=map(int,input().split())
A=list(map(int,input().split()))
S=[0]+list(numpy.cumsum(A)) #累積和
S2=[(S[i]-i)%K for i in range(N+1)]

d = {}
ans = 0
for j in range(1,N+1):
    if j>K-1 and S2[j-K] in d:
        d[S2[j-K]] -= 1
        
    if S2[j-1] in d:
        d[S2[j-1]] += 1
    else:
        d[S2[j-1]] = 1
        
    if S2[j] in d:
        ans += d[S2[j]]
print(ans)

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,K = MI()
    A=LI_()
    ans = 0
    before = defaultdict(int)
    *A,=accumulate(A)
    for i,a in enumerate(A):
        A[i] = a%K
    # print(A)
    for i,a in enumerate(A):
        if i >= K:
            before[A[i-K]]-=1
        ans += before[A[i]]
        before[A[i]]+=1

    ans += A.count(0)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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
    print(a)
    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: Wrong Answer

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

N, K, *A = map(int, read().split())
a = list(accumulate([0] + A))
a = [(a[i] - i) % K for i in range(N + 1)]


def cmb(x):
    return x * (x - 1) // 2


answer = 0
if N < K:
    for i in Counter(a).values():
        answer += cmb(i)
else:
    dic = Counter(a[:K])
    for i in dic.values():
        answer += cmb(i)
    print([0] + A)
    print(a)
    print(dic)
    here = K
    for i, x in enumerate(a[K:]):
        dic[a[i]] -= 1
        answer += dic[x]
        dic[x] += 1

print(answer)

Submission status: Wrong Answer

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

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

d = defaultdict(int)
for i in range(min(k, n)):
    d[(a_cs[i] - i) % k] += 1

ans = 0
for l in range(n):
    d[(a_cs[l] - l) % k] -= 1

    # print(l, d)
    ans += d[(a_cs[l] - l) % k]
    if l + k <= n:
        d[(a_cs[l + k] - (l + k)) % k] += 1

print(ans)

Submission status: Wrong Answer

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

N, K, *A = map(int, read().split())
a = list(accumulate([0] + A))
a = [(a[i] - i) % K for i in range(N + 1)]

answer = 0
dic = defaultdict(int)

for i, x in enumerate(a):
    answer += dic[x]
    dic[x] += 1
    if i >= K - 1:
        dic[a[i - K + 1]] -= 1

print(answer)
'''
import sys
from collections import Counter
from itertools import accumulate
read = sys.stdin.read

N, K, *A = map(int, read().split())
a = list(accumulate([0] + A))
a = [(a[i] - i) % K for i in range(N + 1)]


def cmb(x):
    return x * (x - 1) // 2


answer = 0
if N <= K:
    for i in Counter(a).values():
        answer += cmb(i)
else:
    dic = Counter(a[:K])
    for i in dic.values():
        answer += cmb(i)

    here = K
    for i, x in enumerate(a[K:]):
        dic[a[i]] -= 1
        answer += dic[x]
        dic[x] += 1

    print(answer)

Submission status: Wrong Answer

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

N, K, *A = map(int, read().split())
a = list(accumulate([0] + A))
a = [(a[i] - i) % K for i in range(N + 1)]


def cmb(x):
    return x * (x - 1) // 2


answer = 0
if N <= K:
    for i in Counter(a).values():
        answer += cmb(i)
else:
    dic = Counter(a[:K])
    for i in dic.values():
        answer += cmb(i)

    here = K
    while here <= N:
        if here >= K:
            dic[a[here - K]] -= 1
        if a[here] in dic:
            answer += dic[a[here]]
            dic[a[here]] += 1
        else:
            dic[a[here]] = 1
        here += 1
    print(answer)

Submission status: Wrong Answer

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

N, K, *A = map(int, read().split())
a = list(accumulate([0] + A))
a = [(a[i] - i) % K for i in range(N + 1)]


def cmb(x):
    return x * (x - 1) // 2


answer = 0
if N <= K:
    for i in Counter(a).values():
        answer += cmb(i)
else:
    dic = Counter(a[:K])
    for i in dic.values():
        answer += cmb(i)

    here = K
    while here <= N:
        if here >= K - 1:
            dic[a[here - K - 1]] -= 1
        if a[here] in dic:
            answer += dic[a[here]]
            dic[a[here]] += 1
        else:
            dic[a[here]] = 1
        here += 1
    print(answer)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(lambda x:(int(x)-1)%k,input().split()))
s=[0]
#print(a)
for i in a:
    s.append((s[-1]+i)%k)
s.append(0)
s=s[1:-1]
#print(s)
mp={}
ans=0
for i in range(len(s)):
    if i-k>=0:
        mp[s[i-k]]-=1
    if s[i] in mp:
        ans+=mp[s[i]]
    if s[i] in mp:
        mp[s[i]]+=1
    else:
        mp[s[i]]=1
    #print(i,ans)
ans+=sum(list(map(lambda x: x==0,s)))
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

N, K, *A = map(int, read().split())
a = list(accumulate([0] + A))
a = [(a[i] - i) % K for i in range(N + 1)]


def cmb(x):
    return x * (x - 1) // 2


answer = 0
if N <= K:
    for i in Counter(a).values():
        answer += cmb(i)
else:
    dic = Counter(a[:K])
    for i in dic.values():
        answer += cmb(i)

    here = K
    while here <= N:
        if here - K > -1:
            dic[a[here - K]] -= 1
        if a[here] in dic:
            answer += dic[a[here]]
            dic[a[here]] += 1
        else:
            dic[a[here]] = 1
        here += 1
    print(answer)

Submission status: Wrong Answer

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

N, K, *A = map(int, read().split())
a = list(accumulate([0] + A))
a = [(a[i] - i) % K for i in range(N + 1)]


def cmb(x):
    return x * (x - 1) // 2


answer = 0
if N < K:
    for i in Counter(a).values():
        answer += cmb(i)
else:
    dic = Counter(a[:K])
    for i in dic.values():
        answer += cmb(i)

    here = K
    while here <= N:
        if here - K > -1:
            dic[a[here - K]] -= 1
        if a[here] in dic:
            answer += dic[a[here]]
            dic[a[here]] += 1
        else:
            dic[a[here]] = 1
        here += 1
    print(answer)

Submission status: Wrong Answer

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

hm = {}
hm[A[0]] = 1
out = 0
for i in range(1,N):
  A[i] += A[i-1]
  A[i] %= K

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

print(int(out))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
results = list()
for i in range(1, n):
    for j in range(n - i + 1):
        seq = a[j:j + i]
        remainder = sum(seq) % k
        if (remainder == len(seq)):
            temp_seq = tuple(seq)
            results.append(temp_seq)
print(len(results))

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 A[i]%K == 1:
    #         ans += 1
#            print(i-(K-1), M[i-(K-1)], d)
        now = (now + A[i] - 1)%K
        M[i] = now
        ans += d[now]
        if i >= K-1:
            d[M[i-(K-1)]] -= 1

        d[now] += 1
        #print(ans)        
        # 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()))

results = list()

for i in range(1, n):
    for j in range(n - i + 1):
        seq = a[j:j + i]
        remainder = sum(seq) % k
        if (remainder == len(seq)):
            temp_seq = tuple(seq)
            results.append(temp_seq)

print(len(results))

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
S = [[] for i in range(K)]
S[0].append(0)
A = list(map(int,input().split()))
s = 0
ans = 0
for i in range(1,N+1):
    s = (s+A[i-1])%K
    k = (s-i)%K
    ans += len(S[k])
    S[k].append(i)
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 A[i]%K == 1:
            ans += 1
        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:
S = []
N,K = map(int,input().split())
A = list(map(int,input().split()))
s = 0
ans = 0
for i in range(1,N+1):
    s = (s+A[i-1])%K
    k = (s-i)%K
    ans += S.count(k)
    if k == 0:
        ans += 1
    S.append(k)
print(ans)

Submission status: Wrong Answer

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

L = [-1] * N
D = {}
D[A[0] % K] = 1
t = A[0] % K
L[0] = t
for i in range(1, min(K - 1, N)):
  t = (t + A[i] - 1) % K
  if t < 0:
    t += K
  if t in D:
    D[t] += 1
  else:
    D[t] = 1
  L[i] = t

n = 1
if n in D:
  ans = D[n]
else:
  ans = 0
for i in range(N):
  if L[i] != -1:
    D[L[i]] -= 1
  if i + K - 1 < N:
    t = (t + A[i + K - 1] - 1) % K
    if t < 0:
      t += K
    if t in D:
      D[t] += 1
    else:
      D[t] = 1
    L[i + K - 1] = t
  n = (n - 1 + A[i]) % K
  #n -= 1
  if n < 0:
    n += K
  if n in D:
    ans += D[n]
  
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

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+=((np.roll(array,-i)-array)%K==i)[0:N-i+1].sum()
print(ans)

Submission status: Wrong Answer

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(n+1)]
    for i in range(n+1):
        if(S[i]>=n+1): continue
        C[S[i]].append(i)

    ans=0
    for d in range(n+1):
        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: Wrong Answer

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

Submission status: Wrong Answer

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

results = list()

for i in range(n):
    for j in range(n):
        seq = a[j:j + i + 1]
        remainder = sum(seq) % k
        if (remainder == len(seq)):
            temp_seq = tuple(seq)
            if (temp_seq not in results):
                results.append(tuple(seq))

print(results)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
S=[0]
for i in range(N):
    S.append(S[-1]+A[i])
ans=0
for j in range(N+1): #j番目の要素から始まって
    for k in range(1,N-j+1): #連続するk項の和を見る
        if (S[j+k]-S[j])%K==k%K:
            ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
def main():

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

    prefix = [0]
    d = collections.defaultdict(int)
    ans = 0
    for i in range(N):
        v = (prefix[-1]+A[i]) % K
        prefix.append(v)
        ans += d[v]
        d[(i + v) % K] += 1
        # print(ans)

    # print(d)
    # if 0 in d:
    #     ans += d[0]

    return ans - 1

    # ans = 0
    # for v in d:
    #     ans += d[v] * (d[v] - 1)//2
    # return ans

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

Submission status: Wrong Answer

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


class BIT:
    """
    Binary Index Tree

    add :L[i]+=x
    sum: sum(L[:l])
    range_sum : sum(L[l:r])
    """

    def __init__(self, N, init_val=0):
        self.size = N
        self.L = [init_val]*(N+1)

    def sum(self, r):
        """
        calc sum from L[0] to L[r-1]
        """
        ret = 0
        while r > 0:
            ret += self.L[r]
            r -= r & (-r)

        return ret

    def range_sum(self, l, r):
        """
        calc sum from L[l] to L[r-1]
        """
        return (self.sum(r)-self.sum(l)+K) % K

    def add(self, i, x):
        """
        L[i] += x
        """
        while i < self.size:
            self.L[i] += x
            self.L[i] %= K
            i += i & (-i)


N, K = map(int, input().split())
A = list(map(int, input().split()))
B = BIT(N)
for i, a in enumerate(A):
    B.add(i+1, a)
ans = 0
for l in range(N):
    for r in range(l+1, N):
        if B.range_sum(l, r+1) == r-l:
            ans += 1
print(ans)

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))
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:
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(min(n+1,k))]
    for i in range(n+1):
        if(S[i]>=min(n+1,k)): continue
        C[S[i]].append(i)

    ans=0
    for d in range(min(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()