Problem:


Score : 500 points

Problem Statement

Given are a sequence of N positive integers A_1, A_2, \ldots, A_N, and a positive integer K.

Find the number of non-empty contiguous subsequences in A such that the remainder when dividing the sum of its elements by K is equal to the number of its elements. We consider two subsequences different if they are taken from different positions, even if they are equal sequences.

Constraints

All values in input are integers.

1 \leq N \leq 2\times 10^5

1 \leq K \leq 10^9

1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \cdots A_N

Output

Print the number of subsequences that satisfy the condition.

Sample Input 1

5 4
1 4 2 3 5

Sample Output 1

4

Four sequences satisfy the condition: (1), (4,2), (1,4,2), and (5).

Sample Input 2

8 4
4 2 4 2 4 2 4 2

Sample Output 2

7

(4,2) is counted four times, and (2,4) is counted three times.

Sample Input 3

10 7
14 15 92 65 35 89 79 32 38 46

Sample Output 3

8



Sample input:
5 4
1 4 2 3 5


Sample output:
4

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
for i in range(1,N):
  A[i]+=A[i-1]
A=[(A[i]-i-1)%K for i in range(N)]
A=[0]+A
from collections import Counter
if K>N:
  a=Counter(A)
  ans=0
  for v in a.values():
    ans+=v*(v-1)/2
  print(int(ans))
else:
  ans=0
  d={}
  for i in range(K):
    if A[i] in d:
      ans+=d[A[i]]
      d[A[i]]+=1
    else:
      d[A[i]]=1
  for i in range(K,N+1):
    d[A[i-K]]-=1
    if A[i] in d:
      ans+=d[A[i]]
      d[A[i]]+=1
    if A[i] not in d or d[A[i]]==0:
      d[A[i]]=1
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
for i in range(1,N):
  A[i]+=A[i-1]
A=[(A[i]-i-1)%K for i in range(N)]
A=[0]+A
from collections import Counter
if K>=N:
  a=Counter(A)
  ans=0
  for v in a.values():
    ans+=v*(v-1)/2
  print(ans)
else:
  ans=0
  d={}
  for i in range(K):
    if A[i] in d:
      ans+=d[A[i]]
      d[A[i]]+=1
    else:
      d[A[i]]=1
  for i in range(K,N+1):
    d[A[i-K]]-=1
    if A[i] in d:
      ans+=d[A[i]]
      d[A[i]]+=1
    if A[i] not in d or d[A[i]]==0:
      d[A[i]]=1
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


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

    dp = [0]
    for i in range(N):
        dp.append(dp[-1] + (A[i] - 1))

    dp = [d % K for d in dp]

    ans = 0
    d = defaultdict(int)
    d[0] = 1
    for i in range(1, N + 1):
        ans += d[dp[i]]
        d[dp[i]] += 1

        if i - K + 1 >= 0:
            d[dp[i - K + 1]] -= 1

    print(ans)


def main():
    solve()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


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

mp = defaultdict(int)

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

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))


"""
N^2なので素直に計算は無理，部分和を使いたいのでとりあえず累積和
[i+1:j]が条件を満たすとはS[j]-S[i]とj-iが合同．
移行して，S[j]-jとS[i]-iが合同
基本は個数だけ見れば良い

これだけだと，個数がKより大きい時にダメ
直近Kこの情報だけ持つ，今見てる数字が直近K個のものと何個組にできるか
"""
def main():

    mod=10**9+7
    N,K=MI()
    A=LI()
    from collections import defaultdict
    dd = defaultdict(int)
    
    S=[0]*(N+1)
    for i in range(N):
        S[i+1]=(S[i]+A[i])%K
        
    ans=0
    for i in range(min(K,N)):
        temp=(S[i]-i)%K
        ans+=dd[temp]
        dd[temp]+=1
        
    for i in range(K,N+1):
        temp=(S[i]-i)%K
        temp_m=(S[(i-K)]-(i-K))%K
        dd[temp_m]-=1
        ans+=dd[temp]
        dd[temp]+=1
        
    print(ans)
        
        
    

        

main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N, K = map(int, input().split())
A = list(map(lambda x: int(x) - 1, input().split()))
A_accsum = [0] * (N+1)
for i, a in enumerate(A):
    A_accsum[i+1] = (A_accsum[i]+a)%K

count = defaultdict(lambda: 0)
piv = A_accsum[0]
count[piv] += 1
ans = 0
for i in range(1, min(K, N)):
    a = A_accsum[i]
    count[a] += 1
for i in range(K, N+1):
    a = A_accsum[i]
    piv = A_accsum[i-K]
    count[piv] -= 1
    ans += count[piv]
    count[a] += 1
for i in range(max(0, N - K+1), N+1):
    piv = A_accsum[i]
    count[piv] -= 1
    ans += count[piv]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

mp = defaultdict(int)
ans = 0
for j in range(N + 1):
    ans += mp[acc[j]]
    mp[acc[j]] += 1
    if j >= K:
        mp[acc[j - K]] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,K = LI()
    A = LI()

    c = 0
    d = collections.Counter()
    d[0] = 1
    ans = 0
    r = [0] * (N+1)
    for i,x in enumerate(A):
        c = (c + x - 1) % K
        ans += d[c]
        d[c] += 1
        r[i+1] = c
        if i >= (K-1) - 1:
            d[r[i-(K-1) + 1]] -= 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n, k = map(int, input().split())
a = list(map(int, input().split()))
d = defaultdict(int)
sa = [0] * (n + 1)
d[0] = 1
for i in range(n):
    sa[i + 1] = sa[i] + a[i]
    sa[i + 1] %= k
ans = 0
for i in range(1, n + 1):
    v = sa[i] - i
    v %= k
    ans += d[v]
    d[v] += 1
    if 0 <= i - k + 1:
        vv = sa[i - k + 1] - (i - k + 1)
        vv %= k
        d[vv] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = [int(x) for x in input().split()]

values = dict()
valuelist = [0]*(n+1)
values[0] = 1
s = 0
ans = 0

for i in range(n):
  s += a[i]-1
  s %= k
  if s in values:
    ans += values[s]
    values[s] += 1
  else:
    values[s] = 1
  
  valuelist[i+1] = s
  if i >= k-2:
    values[valuelist[i-k+2]] -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def main():
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    S = [0] * (N + 1)  # 累積和
    for i in range(1, N + 1):
        S[i] = S[i - 1] + A[i - 1]
    T = [(s - i) % K for i, s in enumerate(S)]
    counter = defaultdict(int)
    counter[0] = 1
    ans = 0
    for j in range(1, N + 1):
        ans += counter[T[j]]
        counter[T[j]] += 1
        if j - K + 1 >= 0:
            counter[T[j - K + 1]] -= 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

val_cnt = {}
val_cnt[0] = 1
val_q = deque([0])
if k == 1:
    val_q.popleft()

ans = 0
curr_sum = 0
for i in range(n):
    curr_sum += al[i]
    curr_sum %= k
    val = (curr_sum - (i+1))%k
    val_cnt.setdefault(val,0)
    ans += val_cnt[val]
    val_cnt[val] += 1
    val_q.append(val)
    if len(val_q) >= k:
        poped = val_q.popleft()
        val_cnt[poped] -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

val_cnt = {}
val_cnt[0] = 1
val_q = deque([0])

ans = 0
curr_sum = 0
for i in range(n):
    curr_sum += al[i]
    curr_sum %= k
    val = (curr_sum - (i+1))%k
    val_cnt.setdefault(val,0)
    ans += val_cnt[val]
    val_cnt[val] += 1
    val_q.append(val)
    if len(val_q) >= k:
        poped = val_q.popleft()
        val_cnt[poped] -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys 
import numpy as np
from collections import defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K = map(int, readline().split())
A = [0] + list(map(int,readline().split()))
S = np.cumsum(A)
dic = defaultdict(int)
ans = 0
SS = [0] * (N+1)
for i in range(1,N+1):
    rem = (S[i]-i) % K
    SS[i] = rem
for i in range(1,N+1):
    if i >= K:
        dic[SS[i-K+1]] -= 1
    else:
        if SS[i] == 0:
            ans += 1
    ans += dic[SS[i]]
    dic[SS[i]] += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
DP=dict()
if K==1:
  print(0)
  exit()
DP[0]=1
P=0
Y=[0]*(N+1)
for i in range(N):
  Y[i+1]=(Y[i]+A[i]-1)%K
  P+=DP.get(Y[i+1],0)
  DP[Y[i+1]]=DP.get(Y[i+1],0)+1
  if i>=K-2:
    DP[Y[i-K+2]]-=1

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
current=0
dic={}
dic[0]=1
for i in range(n):
  current=(current+a[i]-1)%k
  if current in dic:
    dic[current]+=1
  else:
    dic[current]=1
ans=0
for i in dic:
  ans+=(dic[i]*(dic[i]-1))//2
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s=input()[::-1]
ans=[]
now=0
while n>m-1:
  x=s[now+1:now+m+1][::-1]
  x=m-x.find('0')
  if x<0:
    print(-1)
    quit()
  n-=(x)
  now+=(x)
  ans.append(x)
if n>0:
  ans.append(n)
print(*ans[::-1])

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,k = LI()
    aa = LI()

    c = collections.defaultdict(int)
    c[0] = 1
    t = [0]
    r = 0
    for i in range(n):
        a = aa[i]
        tt = (t[-1] + a - 1) % k
        t.append(tt)
        r += c[tt]
        if i >= k-2:
            # print("k", t[i-k+2],i-k+2)
            c[t[i-k+2]] -= 1
        c[tt] += 1
        # print("ar", a,tt,r,sorted(c.items()), t)

    return r

print(main())

Submission status: Wrong Answer

Solution code:
from collections import Counter

N, K = map(int, input().split())
*A, = map(int, input().split())
MOD = 10**9+7
ac = [0]*(N+1)

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

c = Counter()
for i in range(1, min(N, K)):
    c[ac[i]] += 1
ans = 0
for i in range(N):
    ans += max(0, c[ac[i]])
    if i+K<=N:
        c[ac[i+K]] += 1
    c[ac[i+1]] -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N, K = map(int, input().split())
*A, = map(int, input().split())
MOD = 10**9+7
ac = [0]*(N+1)

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

c = Counter()
for i in range(min(N, K)):
    c[ac[i]] += 1
ans = 0
for i in range(N+1):
    ans += c[ac[i]]-1
    if i+K<=N:
        c[ac[i+K]] += 1
    c[ac[i]] -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N, K = map(int, input().split())
*A, = map(int, input().split())
MOD = 10**9+7
ac = [0]*(N+1)

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

c = Counter()
for i in range(min(N, K)-1):
    c[ac[i]] += 1
ans = 0
for i in range(N+1):
    if i+K-1<=N and N>K:
        c[ac[i+K-1]] += 1
    ans += c[ac[i]]-1
    c[ac[i]] -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N, K = map(int, input().split())
*A, = map(int, input().split())
MOD = 10**9+7
ac = [0]*(N+1)

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

c = Counter()
for i in range(min(N, K)-1):
    c[ac[i]] += 1
ans = 0
for i in range(N+1):
    if i+K-1<=N:
        c[ac[i+K-1]] += 1
    ans += c[ac[i]]-1
    c[ac[i]] -= 1

print(ans)

Submission status: Wrong Answer

Solution code:

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

res, cumul,cc = 0,0,collections.Counter()

q = collections.deque()
for j,e in enumerate(elems):
	cumul += e
	res += cc[(cumul - j) % k]
	if cumul % k == j + 1 and j + 1 <= k: res += 1
	cc[(cumul -j) % k] += 1
	
	if len(q) == k:
		u = q.popleft()
		cc[u] -=1
	q.append((cumul -j ) % k)
	
print res

Submission status: Wrong Answer

Solution code:

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

res, cumul,cc = 0,0,collections.Counter()

q = collections.deque()
for j,e in enumerate(elems):
	cumul += e
	res += cc[(cumul - j) % k]
	if cumul % k == j+1: res += 1
	

	cc[(cumul -j) % k] += 1
	
	if len(q) == k:
		u = q.popleft()
		cc[u] -=1
	q.append((cumul -j ) % k)
	
print res

Submission status: Wrong Answer

Solution code:

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

res, cumul,cc = 0,0,collections.Counter()

q = collections.deque()
for j,e in enumerate(elems):
	cumul += e
	res += cc[(cumul - j) % k]
	if cumul % k == j+1: res += 1
	if len(q) == k:
		u = q.popleft()
		cc[u] -=1
	q.append((cumul -j ) % k)
		
	cc[(cumul -j) % k] += 1

print res

Submission status: Wrong Answer

Solution code:

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

res, cumul,cc = 0,0,collections.Counter()

q = collections.deque()
for j,e in enumerate(elems):
	cumul += e
	q.append((cumul -j ) % k)
	if len(q) == k:
		u = q.popleft()
		cc[u] -=1
	res += cc[(cumul - j) % k]
	if cumul % k == j+1:
		res +=1
	cc[(cumul -j) % k] += 1

print res

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n, k = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
shukei = defaultdict(int)
# AiからAjまでの和→SA[j]-SA[i-1]
# SA[j]-SA[i-1]=j-(i-1)
# 今回はkで割ったあまりなのでaccumulateは使わず自力
S = [0] * (n + 1)
T = [0] * (n + 1)
for i in range(1, n + 1):
    S[i] = S[i - 1] + A[i - 1]
    S[i] %= k
    T[i] = S[i] - i
    T[i] %= k
    shukei[T[i]] += 1
# i>=1, i<jで同じ値になっている組み合わせを探せば良い。
# kで割ったあまりなので、要素数j−(i-1)がkより小さくないといけない
ans = 0
if k > n + 1:
    for key, num in shukei.items():
        if key == 0:
            ans += num - 1
        ans += num * (num - 1) // 2
else:
    shukei = defaultdict(int)
    for i in range(k):
        shukei[T[i]] += 1
    for key, num in shukei.items():
        ans += num * (num - 1) // 2
    for i in range(k, n + 1):
        j = i - k
        shukei[T[j]] -= 1
        temp = T[i]
        num = shukei[temp]
        ans += num
        shukei[temp] += 1
print(ans)

Submission status: Wrong Answer

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

n,k = map(int,readline().split())
a = [0]+[int(i) for i in readline().split()]
for i in range(1,n+1):
  a[i] = a[i-1]+a[i]
  
a = [(ai-i)%k for i,ai in enumerate(a)]
#print(a)
from collections import Counter,deque
c = Counter({a[0]:1})
d = deque([a[0]])
ans = 0
cnt = 1
for j,aj in enumerate(a[1:]):
  ans += c[aj]
  d.append(aj)
  c.update({aj:1})
  cnt += 1
  if cnt >= k:
    p = d.popleft()
    c.update({p:-1})
  
print(ans)

Submission status: Wrong Answer

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

n,k = map(int,input().split())
a = np.array([0]+[int(i) for i in input().split()])
np.cumsum(a,out=a)
a = [(ai-i)%k for i,ai in enumerate(a)]
print(a)
from collections import Counter,deque
c = Counter({a[0]:1})
d = deque([a[0]])
ans = 0
for j,aj in enumerate(a[1:]):
  ans += c[aj]
  if j-k >= -2:
    p = d.popleft()
    c.update({p:-1})
  d.append(aj)
  c.update({aj:1})
  
print(ans)

Submission status: Wrong Answer

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

n,k = map(int,input().split())
a = np.array([0]+[int(i) for i in input().split()])
np.cumsum(a,out=a)
a = [(ai-i)%k for i,ai in enumerate(a)]
#print(a)
from collections import Counter
c = Counter(a[1:min(n+1,1+k)])
ans = 0
for j,aj in enumerate(a[:n]):
  ans += c[aj]
  if k+1+j <= n:
    c.update({a[k+1+j]:1})
  c.update({a[j+1]:-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 = [a-1 for a in A]
B = [0]+[b%K for b in accumulate(A)]
if K>N:
  Cnt = Counter(B)
  ans = sum(v*(v-1)//2 for v in Cnt.values())
else:
  Cnt = Counter(B[:K])
  ans = sum(v*(v-1)//2 for v in Cnt.values())
  for i in range(N-K):
    Cnt[B[i]] -= 1
    ans += Cnt[B[i+K]]
    Cnt[B[i+K]] += 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 = [a-1 for a in A]
B = [b%K for b in accumulate(A)]
if K-1>N:
  Cnt = Counter(B)
  ans = Cnt[0]+sum(v*(v-1)//2 for v in Cnt.values())
else:
  Cnt = Counter(B[:K-1])
  ans = Cnt[0]+sum(v*(v-1)//2 for v in Cnt.values())
  for i in range(N-K+1):
    Cnt[B[i]] -= 1
    ans += Cnt[B[i+K-1]]
    Cnt[B[i+K-1]] += 1
print(ans)

Submission status: Wrong Answer

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

sa = dict()
ans = 0
now = (0-a2[0]) % k
nowidx = 0
sa[now] = 1
for i in range(1,n+1):
    saadd = (i-a2[i]) % k
    try:
        sa[saadd] += 1
    except:
        sa[saadd] = 1
    if i < k-1:
        continue
    try:
        ans += sa[now]-1
    except:
        pass
    nowidx += 1
    sa[now] -= 1
    now = (nowidx-a2[nowidx])% k




for val,cnt in sa.items():
    ans += cnt*(cnt-1)//2


print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=0
d=defaultdict(int)
sum_a=[0]*(n+1)
tmp=[0]*(n+1)
tmp[0]=0-0%k

sum_a[0]=0
sum_a[1]=a[0]

d[tmp[0]]+=1

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

for i in range(1,n+1):
    sum_a[i]=sum_a[i-1]+a[i-1]
    tmp[i]=i-sum_a[i]%k
    ans+=d[tmp[i]]
    d[tmp[i]]+=1
    if i>=k:
        d[tmp[(i-k)%k]]-=1

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
X = [0 for _ in range(N)]
D = {0: [-1]}
E = {0: 1}
X[0] = (A[0] - 1) % K
if X[0] in D:
  D[X[0]].append(0)
  E[X[0]] += 1
else:
  D[X[0]] = [0]
  E[X[0]] = 1
for i in range(1, N):
  X[i] = (X[i-1] + A[i] - 1) % K
  if X[i] in D:
    D[X[i]].append(i)
    E[X[i]] += 1
  else:
    D[X[i]] = [i]
    E[X[i]] = 1
S = 0
for i in D:
  n = E[i]
  if n > 1:
    L = D[i][:]
    m = L[-1]
    for j in range(n-1):
      x = L[j]
      if m - x < K:
        S += n - 1 - j
      else:
        l, r = j, n
        d = (l + r) // 2
        tmp = 2 * n
        while tmp != 0:
          if L[d] - x <= K - 1:
            l = d
            d = (l + r) // 2
          else:
            r = d
            d = (l + r) // 2
          tmp //= 2
          print(L[j], L[d], l, d, r)
        S += d - j
print(S)

Submission status: Wrong Answer

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 + 1] + nums[i])
ans = 0
for i in range(1, n + 1):
    for j in range(i, n + 1):
        left = nums[i - 1]
        right = nums[j]
        c = j - i
        if (right - left) % k == c and c < k:
            ans += 1
print(ans)

Submission status: Wrong Answer

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 + 1] + nums[i])
ans = 0
for i in range(1, n + 1):
    for j in range(i, n + 1):
        left = nums[i - 1]
        right = nums[j]
        c = j - i
        if (right - left) % k == c:
            ans += 1
print(ans)

Submission status: Wrong Answer

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 + 1] + nums[i]) % k
ans = 0
for i in range(1, n + 1):
    for j in range(i, n + 1):
        left = nums[i - 1]
        right = nums[j]
        c = j - i
        if (right - left) % k == c:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import numpy as np
n,k=map(int,input().split())
a=[0]+list(np.cumsum(list(map(int,input().split()))))

dic = defaultdict(int)
c = 0
for i in range(len(a)):
    p = (a[i] - i) % k
    c += dic[p]
    dic[p] += 1
    if i >= k - 1:
        dic[(a[i - k - 1] - (i - k - 1)) % k] -= 1
print(c)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import numpy as np
n,k=map(int,input().split())
a=[0]+list(np.cumsum(list(map(int,input().split()))))

dic = defaultdict(int)
c = 0
for i in range(len(a)):
    c += dic[(a[i] - i) % k]
    dic[(a[i] - i)% k] += 1
    if i >= k - 1:
        dic[(a[i - k - 1] - (i - k - 1)) % k] -= 1
print(c)

Submission status: Wrong Answer

Solution code:
# %%time
import numpy as np
n, k = map(int, input().split())
a = list(map(int, input().split()))

# a = np.random.randint(0, 100, 20000)
a = np.array(a) % k

cumsum = np.cumsum(a)
cumsum = np.hstack([[0], cumsum])

count = 0
for i in range(1, len(cumsum) - 1):
    count += np.sum(((cumsum[i : ] - cumsum[: -i]) % k) == i)

# 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(count)

Submission status: Wrong Answer

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

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

N, K = lr()
A = np.array([1] + lr())
A = (A-1) % K
N += 1
# 累積和が同じになっている箇所に注目、要素がK-1離れている組み合わせは無理
Acum = (A.cumsum() % K).tolist()
answer = 0
dic = defaultdict(int)
for i in range(N):   
    cur = Acum[i]
    answer += dic[cur]
    dic[cur] += 1
    if i >= K-1:
        vanish = A[i-(K-1)]
        dic[vanish] -= 1

print(answer)
# 10

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from collections import Counter
from math import factorial

def combinations_count(n, r): # 組み合わせ
    if r > n:
        return 0
    return factorial(n) // (factorial(n - r) * factorial(r))

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

# 累積和
N, K = lr()
A = np.array(lr())
A %= K
A -= 1
answer = (A==0).sum()
Acum = A.cumsum().tolist()
counter = Counter(Acum)
for v in counter.values():
    answer += combinations_count(v, 2)

print(answer)

Submission status: Wrong Answer

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()
A = np.array(lr())
A %= K
A -= 1
Acum = A.cumsum()
answer = 0
for i in range(N):
    a = Acum[i]
    count = (Acum - a == 0).sum() - 1
    answer += count
    if A[i] == 0:
        answer += 2

answer //= 2
print(answer)

Submission status: Wrong Answer

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()
A = np.array(lr())
A %= K
A -= 1
Acum = A.cumsum()
answer = 0
for i in range(N):
    a = A[i]
    count = (Acum[i+1:] - a == 0).sum()
    answer += count
    if a == 0:
        answer += 1

print(answer)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
s=[0]*n
for i in range(n):
  s[i]=(s[i-1]+a[i]-1)%k
s.sort()
s+=[-1]
cnt=1
chk=s[0]
ans=0
for i in range(1,n+1):
  if s[i]!=chk:
    chk=s[i]
    ans+=cnt*(cnt-1)//2
    cnt=1
  else:
    cnt+=1
print(ans+s.count(0))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
s=[0]*n
for i in range(n):
  s[i]=(s[i-1]+a[i]-1)%k
s.sort()
s+=[-1]
cnt=1
chk=s[0]
ans=0
for i in range(1,n+1):
  if s[i]!=chk:
    chk=s[i]
    ans+=cnt*(cnt-1)//2
  else:
    cnt+=1
print(ans+s.count(0))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
s=[0]*n
for i in range(n):
  s[i]=(s[i-1]+a[i]-1)%k
s.sort()
s+=[-1]
cnt=1
chk=s[0]
ans=0
for i in range(1,n+1):
  if s[i]!=chk:
    chk=s[i]
    ans+=cnt*(cnt-1)//2
  else:
    cnt+=1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import *
import copy
N,K=map(int,input().split())
A=list(map(int,input().split()))
if K==1:
    print(N)
    exit()

lst=[0]
for i in range(0,N):
    lst.append((A[i]%K+lst[i])%K)
for i in range(len(lst)):
    lst[i]-=i
    lst[i]%=K

dic={}
count=0
for i in range(0,len(lst)):
    if lst[i] in dic:
        count+=dic[lst[i]]
        dic[lst[i]]+=1
    else:
        dic.update({lst[i]:1})
    a=i-K+1
    if a>=0:
        dic[lst[a]]-=1
print(count)

Submission status: Wrong Answer

Solution code:
from collections import *
import copy
N,K=map(int,input().split())
A=list(map(int,input().split()))

lst=[0]
for i in range(0,N):
    lst.append((A[i]%K+lst[i])%K)
for i in range(len(lst)):
    lst[i]-=i
    lst[i]%=K

dic={0:1}
count=0
for i in range(1,len(lst)):
    if lst[i] in dic:
        count+=dic[lst[i]]
        dic[lst[i]]+=1
    else:
        dic.update({lst[i]:1})
    a=i-K+1
    if a>=0:
        dic[lst[a]]-=1
print(count)

Submission status: Wrong Answer

Solution code:
from collections import *
import copy
N,K=map(int,input().split())
A=list(map(int,input().split()))

lst=[0]
for i in range(0,N):
    lst.append((A[i]%K+lst[-1])%K)
for i in range(len(lst)):
    lst[i]-=i
    lst[i]%=K

dic={0:1}
count=0
for i in range(1,len(lst)):
    if lst[i] in dic:
        count+=dic[lst[i]]
        dic[lst[i]]+=1
    else:
        dic.update({lst[i]:1})
    a=i-K+1
    if a>=0:
        dic[lst[a]]-=1
print(count)

Submission status: Wrong Answer

Solution code:
from collections import *
import copy
N,K=map(int,input().split())
A=list(map(int,input().split()))

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

dic={0:1}
count=0
for i in range(1,len(lst)):
    if lst[i] in dic:
        count+=dic[lst[i]]
        dic[lst[i]]+=1
    else:
        dic.update({lst[i]:1})
    a=i-K+1
    if a>=0:
        dic[lst[a]]-=1
print(count)

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,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
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
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()
    for i in range(N):
        A[i]-=1
    *cumsum, = accumulate(A)
    for i in range(N):
        cumsum[i]%=K

    cnt = defaultdict(int)
    ans = 0
    for i,c in enumerate(cumsum):
        if i>=K-1:
            cnt[cumsum[i-K+1]]-=1
        if c==0 and i<K-1:
            ans += 1
        if cnt[c]:
            ans += cnt[c]
        cnt[c]+=1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, K = map(int, input().split())
A = [(int(c)%K)-1 for c in input().split()]
B = [0]
for c in A:
  B += [B[-1]+c]
dic = defaultdict(int)
ldic = defaultdict(int)
for i in range(min(K,N)):
  c = B[i]
  dic[c%K] += 1
ans = 0
#print(dic)
for i in range(1,N+1):
  x = B[i-1]
  ldic[x%K] += 1
  ans += dic[x%K]-ldic[x%K]
  if K+i-1<=N:
    dic[B[K+i-1]%K] += 1
  """
  print('###############')
  print(i,x, ans)
  print(dic)
  print(ldic)
  """
print(ans)