Problem:


Score : 500 points

Problem Statement

Takahashi has a string S of length N consisting of digits from 0 through 9.

He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S - there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.

Here substrings starting with a 0 also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.

Compute this count to help Takahashi.

Constraints

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

S consists of digits.

|S| = N

2 \leq P \leq 10000

P is a prime number.

Input

Input is given from Standard Input in the following format:

N P
S

Output

Print the number of non-empty (contiguous) substrings of S that are divisible by P when regarded as an integer written in base ten.

Sample Input 1

4 3
3543

Sample Output 1

6

Here S = 3543. There are ten non-empty (contiguous) substrings of S:

3: divisible by 3.

35: not divisible by 3.

354: divisible by 3.

3543: divisible by 3.

5: not divisible by 3.

54: divisible by 3.

543: divisible by 3.

4: not divisible by 3.

43: not divisible by 3.

3: divisible by 3.

Six of these are divisible by 3, so print 6.

Sample Input 2

4 2
2020

Sample Output 2

10

Here S = 2020. There are ten non-empty (contiguous) substrings of S, all of which are divisible by 2, so print 10.

Note that substrings beginning with a 0 also count.

Sample Input 3

20 11
33883322005544116655

Sample Output 3

68



Sample input:
4 3
3543


Sample output:
6

Submission status: Runtime Error

Solution code:
N, P = map(int, input().split())
S = input()
count = 0
S.reverse()
tmp = 0

for i in range(N):
    for j in range(i+1, N+1):
        pass
print(count)

Submission status: Runtime Error

Solution code:
s = input()
q = int(input())

r = 0
sort = 0
for i in range(q):
  List=list(input().split())
  if len(List) > 1 :
    if List[1] == '1' and r == 0 :
      s = s + List[2] 
    elif List[1] == '1' and r == 1 :
      s = List[2] + s 
    elif List[1] == '2' and r == 0 :
      s = List[2] + s 
    elif List[1] == '2' and r == 1 :
      s = s + List[2] 
    r = 0
  else:
    if r == 1 :
      r=0
    else:
      r=1
  if i == q-1 and len(List) == 1 :
    sort = 1


ans = ''
if sort == 0:
  print(s)
else:
  for j in range(len(s)):
    ans += s[len(s)-j-1:len(s)-j]

print(ans)

Submission status: Runtime Error

Solution code:
N, P = map(int, input().split())
num = input().strip()
dp = [0] * N
ans = 0
last = 0
for i in range(N):
    last = (10 * last + int(num[i])) % P
    if last == 0:
        ans += 1 + dp[last]
        dp[last] += 1
    else:
        ans += dp[last]
        dp[last] += 1
print(ans)

Submission status: Runtime Error

Solution code:


def main():
    N, P = map(int, input().split())
    S = input()

    def search(i, n):
        if i >= N:
            return 0
        n = n * 10 + int(S[i])
        cnt = 1 if n % P == 0 else 0
        cnt += search(i + 1, n)
        return cnt

    cnt = 0

    for i in range(N):
        cnt += search(i, 0)

    print(cnt)


main()

Submission status: Runtime Error

Solution code:
a, b = [int(c) for c in input().split(" ")]
S = input()
count = 0
for i in range(1, a):
  for j in range(0, a):
      if (j+i <= a+1):
          subStr = S[j:j+i]
          print(subStr)
          if (len(subStr) == i):
            if (int(subStr) % b == 0):
                count+=1
if (int(S) % b == 0):
    count+=1
print(count)

Submission status: Runtime Error

Solution code:
N, P = map(int, input().split())
S = list(map(int, input()))

lst = [[] for _ in range(10)]

# 0のときは調べなくてよい（無視）
for i in range(1, 10):
	warareru = i / 10
	for n in range(N):
		warareru *= 10
		lst[i].append(int(warareru % P))
		
ans = 0

for i in reversed(range(N)):
	# スタート地点を設定
	mod = 0
	keta = 0
	for j in range(i, -1, -1):
		keta += 1
		if S[j] != 0:
			mod += lst[S[j]][keta - 1]
			mod %= P
		if mod == 0: ans += 1
			
print(ans)

Submission status: Runtime Error

Solution code:
N, P = map(int, input().split())
S = list(map(int, input()))

lst = [[] for _ in range(10)]

# 0のときは調べなくてよい（無視）
for i in range(1, 10):
	warareru = i / 10
	for n in range(N):
		warareru *= 10
		lst[i].append(int(warareru % P))
		
ans = 0

for i in range(N):
	for j in range(i, N):
		# ある1つの区間について調べる
		mod = 0
		len = j - i + 1 # 今回の桁数
		for k in range(i, j + 1):
			if S[k] == 0: continue
			mod += lst[S[k]][len - (k - i) - 1]
			mod %= P
		if mod == 0: # 割り切れたら
			ans += 1
			
# for i in range(N):
	# if S[i] == 0: continue
	# sum(lst[S[i]][0 : (N - i)]) % P 
			
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,P = inpl()
S = list(map(int,list(input())))

assert 10%P != 0


tmpl = [s*pow(10,N-1-i,P)%P for i,s in enumerate(S)]
xx = [tmpl[0]]
for t in tmpl[1:]:
    xx.append((xx[-1]+t)%P)

yy = [S[0]%P]
for s in S[1:]:
    yy.append((yy[-1]*10+s)%P)

nums = [0]*P
nums[0] += 1
ans = 0
for i,y in enumerate(yy):
    tmp = y*pow(10,N-1-i,P)%P
    ans += nums[tmp]
    nums[xx[i]] += 1


print(ans)

Submission status: Runtime Error

Solution code:
a, b = [int(c) for c in input().split(" ")]
S = input()
count = 0
for i in range(1, a):
  for j in range(a):
    if (j+i > a):
      if (j != a-1):
        if (int(S[j:]) % b == 0):
          count++;
    else:
      if (int(S[j:j+i]) % b == 0):
      	count++
print(count)

Submission status: Runtime Error

Solution code:
S = list(input())
Q = int(input())

flag = True

for i in range(Q):
    q = list(map(str, input().split()))
    if len(q) == 1:
        flag = not flag
    else:
        if (q[1] == '1' and flag == True) or (q[1] == '2' and flag == False):
            S.insert(0, q[2])
        else:
            S.append(q[2])

if flag == True:
    print(*S, sep="")
else:
    S.reverse()
    print(*S, sep="")

Submission status: Runtime Error

Solution code:
from collections import Counter
N, P = map(int, input().split())
S = input()
L = len(str(P))
M = []
for i in range(10 ** L):
    M.append(i % P)

q = Counter([int(S[i:L-1]) for i in range(L-1)])
q[0] += 1
ans = 0
for i in range(L-1, N):
    nq = Counter()
    n = int(S[i])
    for a, c in q.items():
        s = (a * 10 + n) % P
        if s == 0:
            ans += c
        nq[s] += c
    nq[0] += 1
    q = nq
print(ans)

Submission status: Runtime Error

Solution code:
S = input()
Q = int(input())
QUERY = []
for i in range(Q):
    # q = list(map(int, input().split()))
    q = input().split()
    if q[0] == '1':
        QUERY.append([int(q[0])])
    else:
        QUERY.append([int(q[0]), int(q[1]), q[2]])

st = []
en = []
rev = False
rev_c = 0
for q in QUERY:
    if q[0] == 1:
        if rev:
            rev = False
        else:
            rev = True
        rev_c += 1
    else:
        if q[1] == 1:
            if not rev:
                st.append(q[2])
            else:
                en.append(q[2])
        else:
            if not rev:
                en.append(q[2])
            else:
                st.append(q[2])

# print(st)
# print(en)

st_s = "".join(st)
st_s = st_s[::-1]
en_s = "".join(en)

ans = st_s + S + en_s
if rev_c % 2 == 0:
    pass
else:
    ans = ans[::-1]

print(ans)

Submission status: Runtime Error

Solution code:
import math
from collections import deque
def main():
    n,p = tuple([int(t)for t in input().split()])

    s = input()
    counter =0
    for i in range(n):
        for j in range(i,n):
            subs = s[i:j]
            counter += 1 if int(subs)%p ==0 else 0

    print(counter)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter
n, p = map(int, input().split( ))
s = input()
#n,p = 10000,7
#s = "1"*10000
#p=2,5は例外
#例外でなければ累積和
if p==2:
    ans = 0
    for i in range(n):
        if int(s[i])%2==0:
            ans += i+1
    print(ans)
    exit()
if p==5:
    for i in range(n):
        if int(s[i])%5==0:
            ans += i+1
    print(ans)
    exit()


accm = [0]
s = s[::-1]
sm = 0
beki_p = 1
for i in range(n):
    sm += int(s[i])*beki_p
    sm %=p
    accm.append(sm)
    beki_p *=10
    beki_p%=p

aC = Counter(accm)
ans = 0
for k in aC:
    ans += aC[k]*(aC[k]-1)//2
print(ans)

Submission status: Runtime Error

Solution code:
n,p = map(int, input().split())
s = input()
t = 0
for i,j in n-1:
  if i <= j:
    s1 = s[i,j]
    if s1 % p:
      t = t + 1
print(t)

Submission status: Runtime Error

Solution code:
S = input()
n= int(input())

for i in range(n):
  Q = [i for i in input().split()]
  if Q[0] =='1':
    S = S[::-1]
    #print(S)
  else:
    if Q[1]=='1':
      S = Q[2]+S
    else:
      S =S+Q[2]
    #print(S)
print(S)

Submission status: Runtime Error

Solution code:
from collections import deque
s = input()
q = int(input())
flag = True
atama = deque()
osiri = deque()
for i in range(q):
    inp = input()
    if inp == '1':
        flag = not flag

    else:
        _, f, c = map(str, inp.split())
        if f == '1':
            if flag:
                atama.appendleft(c)
            else:
                osiri.append(c)
        else:
            if flag:
                osiri.append(c)
            else:
                atama.appendleft(c)

if flag:
    while(atama):
        tmp = atama.popleft()
        print(tmp, end='')
    print(s, end='')
    while(osiri):
        tmp = osiri.popleft()
        print(tmp, end='')
else:
    while(osiri):
        tmp = osiri.pop()
        print(tmp, end='')
    print(s[::-1], end='')
    while(atama):
        tmp = atama.pop()
        print(tmp, end='')

Submission status: Runtime Error

Solution code:
from collections import Counter
n, p = map(int, input().split( ))
s = input()

#p=2,5は例外
#例外でなければ累積和
if p==2:
    ans = 0
    for i in range(n):
        if int(s[i])%2==0:
            ans += i+1
    print(ans)
    exit()
if p==5:
    for i in range(n):
        if int(s[i])%5==0:
            ans += i+1
    print(ans)
    exit()
s = int(s)

accm = [0]

for i in range(n):
    si = s%(10**(i+1))
    sip = si%p
    accm.append(sip)

aC = Counter(accm)
ans = 0
for k in aC:
    ans += aC[k]*(aC[k]-1)//2
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
from itertools import accumulate
import sys
input = sys.stdin.readline
n,p = map(int,input().split())
s = input().rstrip()
if p == 2:
  ans = 0
  for i in range(n):
    if int(s[i])%2 == 0:
      ans += i+1
  print(ans)
elif p == 5:
  for i in range(n):
    if int(s[i])%5 == 0:
      ans += i+1
  print(ans)
else:
  ls = [0]
  prev = 0
  for i in range(n):
    x = int(s[n-i-1])
    y = (prev+x*pow(10,i,p))%p
    ls.append(y)
    prev = y
  c = Counter(ls)
  ans = 0
  for x in c.values():
    ans += x*(x-1)//2
  print(ans)