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:
from collections  import Counter

def main():
    N,P = map(int,input().split())
    S = list(map(int, input()))[::-1]
    D = [0] * (N+1)
    exp = 0
    for i, s in enumerate(S):
        exp += 1
        D[i] =  s * pow(10, exp) % P
    C = Counter(D)

    ans = 0
    for i in range(2020):
        ans += c[i] * (c[i]-1)//2
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,P=map(int,input().split())
    A=list(map(int,list(input())[::-1]))
    MOD=P
    S=[0]*(N+1)
    for i in range(N):
        S[i+1]=(S[i]+A[i]*pow(10,i,MOD))%MOD
    l=[0]*2019
    ans=0
    for i in range(N+1):
        ans+=l[S[i]]
        l[S[i]]+=1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:

def resolve():
    l, P = map(int, input().split())
    S = input()[::-1]

    ans = 0
    # 10^r: 2^r * 5^r の為、10と同じ素数
    if P == 2 or P == 5:
        for i in range(l):
            s = int(S[i])
            if s % P == 0:
                ans += i + 1
        return print(ans)

    cnts = [0] * (l + 1)
    cnts[0] = 1
    num, d = 0, 1
    for i in range(l):
        s = int(S[i])
        num += s * d
        d *= 10
        num %= P
        d %= P
        cnts[num] += 1

    for cnt in cnts:
        ans += cnt * (cnt - 1) // 2
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
N,P=[int(s) for s in input().split()]
S=list(input())
if P!=2 and P!=5:
  ls=[0 for _ in range(N)]
  mod=[0 for _ in range(P)]
  d=10
  ls[0]=int(S[-1])
  mod[ls[0]]+=1
  for i in range(1,N):
    ls[i]=(ls[i-1]+d*int(S[-1-i]))%2019
    d=(d*10)%2019
    mod[ls[i]]+=1
  #print(ls)
  #print(mod)  
  ans=mod[0]
  for i in range(N):
    m=ls[i]
    mod[ls[i]]-=1
    ans+=mod[ls[i]]
else:
  ans=0
  for i in range(N):
    if int(S[i])%P==0:
      ans+=i+1
print(ans)

Submission status: Runtime Error

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

n, p = [int(x) for x in input().split()]
s = input().rstrip()[::-1]
ans = 0
if p == 2:
    for i in range(n):
        if s[i] % 2 == 0:
            ans += (n - i + 1)
    print(ans)
    sys.exit()
if p == 5:
    for i in range(n):
        if s[i] == 0 or s[i] == 5:
            ans += (n - i + 1)
    print(ans)
    sys.exit()
t = [0, int(s[0]) % p]
mul = 10
for i in range(1, n):
    t.append((t[-1] + int(s[i])*mul) % p)
    mul *= 10
    mul %= p
from collections import Counter
c = Counter(t)
for i in c.keys():
    ans += c[i]*(c[i] - 1) // 2
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

N, mod = mi()
S = list(map(int, list(input())))
ans = 0

if 10 % mod != 0:
    mod_list = [0]
    ten = 1
    for num in S[::-1]:
        yo = (num * ten + mod_list[-1]) % mod
        mod_list.append(yo)
        ten = (ten * 10) % mod

    cnt = [0]*2019
    for yo in mod_list:
        cnt[yo] += 1

    for i in range(2019):
        ans += cnt[i] * (cnt[i]-1) // 2

else:
    for i, num in enumerate(S):
        if num % mod == 0:
            ans += i+1

print(ans)

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,p = get_nums_l()
s = input()
X = list(map(int, list(s)))
n = len(s)

if p in (2,5):
    ans = 0
    for i,x in enumerate(X):
        if x%p == 0:
            ans += i+1
    print(ans)
else:
    ruiseki = [0] * (n+1)
    for i in (range(n-1, -1, -1)):
        ruiseki[i] = (X[i] * pow(10, (n-i-1), p) + ruiseki[i+1]) % p

    # log(ruiseki)

    ans = 0
    count = defaultdict(int)

    for x in ruiseki:
        # log(count[x])
        ans += count[x]
        count[x] += 1
    # log(count)
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dict

n, p = map(int, input().split())
s = input()
a = []
for x in s:
    a.append(int(x))

def solve():
    l = [0]*p
    ans = 0
    for x in a:
        l_ = [0] * p
        for i in range(p):
            l_[(i * 10 + x) % p] += l[i]
        l, l_ = l_, l
        l[x % p] += 1
        ans += l[0]
    print(ans)
if p <= 5:
    solve()
    exit()
exit(1)
x = 0
mem = dict(int)
mem[0] = 1
ans = 0
for y in a:
    x = (x * 10 + y) % p
    ans += mem[x]
    mem[x] += 1
    # print(mem)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dict

n, p = map(int, input().split())
s = input()
a = []
for x in s:
    a.append(int(x))

def solve():
    l = [0]*p
    ans = 0
    for x in a:
        l_ = [0] * p
        for i in range(p):
            l_[(i * 10 + x) % p] += l[i]
        l, l_ = l_, l
        l[x % p] += 1
        ans += l[0]
    print(ans)
if p <= 5:
    solve()
    exit()

x = 0
mem = dict(int)
mem[0] = 1from collections import defaultdict as dict

n, p = map(int, input().split())
s = input()
a = []
for x in s:
    a.append(int(x))

def solve():
    l = [0]*p
    ans = 0
    for x in a:
        l_ = [0] * p
        for i in range(p):
            l_[(i * 10 + x) % p] += l[i]
        l, l_ = l_, l
        l[x % p] += 1
        ans += l[0]
    print(ans)
if p <= 5:
    solve()
    exit()

exit(1)
x = 0
mem = dict(int)
mem[0] = 1
ans = 0
for y in a:
    x = (x * 10 + y) % p
    ans += mem[x]
    mem[x] += 1
    # print(mem)
print(ans)
ans = 0
for y in a:
    x = (x * 10 + y) % p
    ans += mem[x]
    mem[x] += 1
    # print(mem)
print(ans)

Submission status: Runtime Error

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

cnt = defaultdict(int)
ans = 0
if p == 2:
    # 右端が偶
    for i, v in enumerate(s):
        if int(v) % 2 == 0:
            ans += 1 + i
    print(ans)
elif p == 5:
    for i, v in enumerate(s):
        if v == "0" or v == "5":
            ans += 1 + i
    print(ans)
else:
    s = list(s[::-1])
    for i in range(n-1):
        s[i+1] += s[i]
    a = [0] + list(map(lambda x: int(x) % p, s))
    for a_i in a:
        cnt[a_i] += 1

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

Submission status: Runtime Error

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

cnt = defaultdict(int)
ans = 0
if p == 2:
    # 右端が偶
    for i, v in enumerate(s):
        if int(v) % 2 == 0:
            ans += 1 + i
    print(ans)
elif p == 5:
    for i, v in enumerate(s):
        if v == "0" or v == "5":
            ans += 1 + i
    print(ans)
else:
    s = list(s[::-1])
    for i in range(n-1):
        s[i+1] = s[i+1] + s[i]
    a = [0] + list(map(lambda x: int(x) % p, s))
    for a_i in a:
        cnt[a_i] += 1

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

Submission status: Runtime Error

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

cnt = defaultdict(int)
ans = 0
if p == 2:
    # 右端が偶
    for i, v in enumerate(s):
        if int(v) % 2 == 0:
            ans += 1 + i
    print(ans)
elif p == 5:
    for i, v in enumerate(s):
        if v == "0" or v == "5":
            ans += 1 + i
    print(ans)
else:
  	s = s[::-1]
    for i in range(n-1):
        s[i+1] = s[i+1] + s[i]
    a = [0] + list(map(lambda x: int(x) % p, s))
    for a_i in a:
        cnt[a_i] += 1

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n, p = map(int, input().split())
s = list(input()[::-1])

cnt = defaultdict(int)
ans = 0
if p == 2:
    # 右端が偶
    for i, v in enumerate(s):
        if int(v) % 2 == 0:
            ans += 1 + i
    print(ans)
elif p == 5:
    for i, v in enumerate(s):
        if v == "0" or v == "5":
            ans += 1 + i
    print(ans)
else:
    for i in range(n-1):
        s[i+1] = s[i+1] + s[i]
    a = [0] + list(map(lambda x: int(x) % p, s))
    for a_i in a:
        cnt[a_i] += 1

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

Submission status: Runtime Error

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

cnt = defaultdict(int)
ans = 0
if p == 2:
    # 右端が偶
    for i, v in enumerate(s):
        if int(v) % 2 == 0:
            ans += 1 + i
    print(ans)
elif p == 5:
    raise RuntimeError
    for i, v in enumerate(s):
        if v == "0" or v == "5":
            ans += 1 + i
    print(ans)
else:
    for i in range(n+1):
        a_i = int(s[-i:])
        cnt[a_i % p] += 1

    for k, v in cnt.items():
        ans += v * (v - 1)//2
    print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, P = list(map(int,_in[0].split(' ')))  # type:list(int)
    S =     _in[1]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cand_arr = []
    for i in range(N):
        for j in range(N-i):
            cand_arr.append(int(S[j:j+i]))
    cnt = 0
    for cand in cand_arr:
        if cand % P == 0:
            cnt += 1
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

Submission status: Runtime Error

Solution code:
from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, P = list(map(int,_in[0].split(' ')))  # type:list(int)
    S =     _in[1]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cand_arr = []
    for i in range(len(str(P))-1,N+1):
        for j in range(N-i+1):
            cand_arr.append(int(S[j:j+i]))
    cnt = 0
    for cand in cand_arr:
        if cand % P == 0:
            cnt += 1
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

Submission status: Runtime Error

Solution code:
def main():
    n, p = map(int, input().split())
    s = input()
    mu = [None]*n
    ans = 0
    c = [0]*p
    ss = map(int, s)
    if 10%p == 0:
        for i in range(n):
            if ss[i]%p == 0:
                ans += i+1
        print(ans)
        return
    num = int(s)
    keta = n-1
    for i, si in enumerate(ss):
        v = num%p
        mu[i] = v
        c[v] += 1
        num -= si*10**keta
        keta -= 1
    c[0] += 1
    for i in mu:
        c[i] -= 1
        ans += c[i]
        
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, p = map(int, input().split())
    s = input()
    mu = [None]*n
    ans = 0
    c = [0]*p
    if 10%p == 0:
        for i in range(n):
            if int(s[i])%p == 0:
                ans += i+1
        print(ans)
        return
    num = int(s)
    keta = n-1
    for i in range(n):
        v = num%p
        mu[i] = v
        c[v] += 1
        num -= si*10**keta
        keta -= 1
    c[0] += 1
    for i in mu:
        c[i] -= 1
        ans += c[i]
        
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3

(n, p) = map(int, input().split())
s = input()

c = 0
if p == 2 or p == 5:
    for i in range(n - 1, -1, -1):
        if int(s[i]) % p == 0:
            c += i + 1

else:
    mm = {}
    for i in range(n - 1, -1, -1):
        u = int(s[i:])
        r = u % p
        if r in mm:
            c += l
            mm[r] += 1
        else:
            mm[r] = 1

        if r == 0:
            c += 1
        
print(c)

Submission status: Runtime Error

Solution code:
from collections import Counter
n, p = map(int, input().split())
s = input()
s += '0'
p_cnt = 0
div_list = []

if p == 2 or p == 5:
    for i in range(n):
        if s[i] % p == 0:
            p_cnt += i+1
else:
    for i in range(n+1):
        num = int(s[i:])
        div_list.append(num % p)

    div_ol = Counter(div_list)
    for v in div_ol.values():
        p_cnt += v * (v - 1) / 2



print(int(p_cnt))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n,p = [int(i) for i in input().split()]
s = input()
ans = 0

if p == 2 or p == 5:
  s = list(s)
  for i,si in enumerate(s):
    if int(si)%p == 0:
      ans += i+1
  print(int(ans))
else:
  chk = [0]*p
  chk[0] = 1
  m = 0
  for i in range(n)[::-1]:
    m = (int(s[i])*pow(10,n-1-i)+m)%p
    chk[m] += 1
  for i in chk:
    ans += i*(i-1)/2
  print(int(ans))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n,p = [int(i) for i in input().split()]
s = input()
ans = 0

if p == 2 or p == 5:
  s = list(s)
  for i,si in enumerate(s):
    if int(si)%p == 0:
      ans += i+1
  print(int(ans))

else:
  chk = [0]*p
  chk[0] = 1
  m = 0
  for i in range(n)[::-1]:
    m = (int(s[i])*(10**(n-1-i))+m)%p
    #print(i,m)
    chk[m] += 1
  for i in chk:
    ans += i*(i-1)/2
  print(int(ans))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n,p = [int(i) for i in input().split()]
s = input()
ans = 0
if p == 2:
  s = list(s)
  for i,si in enumerate(s):
    if int(si)%2 == 0:
      ans += i+1
  print(int(ans))
  exit()

elif p == 5:
  s = list(s)
  for i,si in enumerate(s):
    if int(si)%5 == 0:
      ans += i+1
  print(int(ans))
  exit()

chk = [0]*p
chk[0] = 1

for i in range(1,n):
  m = s[:-i]
  k = int(int(m)%p)
  chk[k] += 1
r = int(int(s)%p)
chk[r] += 1
for i in chk:
  ans += i*(i-1)/2
print(int(ans))

Submission status: Runtime Error

Solution code:
def main(): 
  import sys
  input = sys.stdin.readline
  n,p = [int(i) for i in input().split()]
  s = input()
  ans = 0
  if p == 2:
    s = list(s)
    for i,si in enumerate(s):
      if int(si)%2 == 0:
        ans += i+1
    print(ans)
    exit()

  elif p == 5:
    s = list(s)
    for i,si in enumerate(s):
      if int(si)%5 == 0:
        ans += i+1
    print(ans)
    exit()

  chk = [0]*p
  chk[0] = 1

  for i in range(1,n):
    m = s[:-i]
    k = int(int(m)%p)
    chk[k] += 1
  r = int(int(s)%p)
  chk[r] += 1
  for i in chk:
    ans += i*(i-1)/2
  print(int(ans))
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N,P = map(int,input().split())
S = input()
lenS = len(S)
ans = 0
ten = 1
lis = [0]*lenS
if P == 2 or P == 5:
  for i in range(lenS):
    if S[i] == "2" or S[i] == "5":
      ans += i + 1
      
else:
  for i in range(lenS):
    lis[i+1] = lis[i] + (int(S[lenS-i-1])*ten) % P
  t = [0] * P
  for i in lis: 
    t[i] += 1
  for i in t:
    ans += i * (i-1) // 2
print(ans)

Submission status: Runtime Error

Solution code:
n, p = map(int, input().split())
s = list(map(int, input()))
ans = 0

if p == 2 or p == 5:
    for i, x in enumerate(s):
        if (p == 2 and not x % 2) or (p == 5 and (x == 0 or x == 5)):
            ans += i+1
    print(ans)
    exit()

s.reverse()
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = (cum[i] + s[i] * pow(10, i, p)) % p
t = [0] * 10
for x in cum: t[x] += 1

for x in t:
    ans += x * (x-1) // 2
print(ans)

Submission status: Runtime Error

Solution code:
n, p = input().split()
s = input()

len_p = len(p)
n, p = int(n), int(p)

num = 2
if p == num:
    count = 0
    for i in range(len(s)):
        current = int(s[i])
        if current == num or current == 0:
            count += i + 1
    print(count)

num = 5
if p == num or s[i] == 0:
    count = 0
    for i in range(len(s)):
        current = int(s[i])
        if current == num or current == 0:
            count += i + 1
    print(count)

if p != 2 and p != 5:
    count = 0
    for i in range(len_p - 1, n):
        i += 1
        for j in range(i - len_p + 1):
            number = int(s[j:i])
            if int(number % p) == 0:
                count += 1

    print(count)

Submission status: Runtime Error

Solution code:
import sys
INPUT=input().split()
N=int(INPUT[0])
P=int(INPUT[1])
S=str(input())
"""
constant:N: 文字列Sの長さ
constant:P: 素数 2~10000
constant:S: 0~9からなる文字列
"""
ans=0
"""
variable:ans: Pで割り切れるものの個数
"""
for _ in range(1,N+1):
    """
    variable:_: 部分列の長さ。1~Nまで
    """
    for _a in range(N+1-_):
        """
        variable:_a: 部分列の頭のSにおける位置
        """
        x=int(S[_a:_+_a])
        ans+= 1- (x%P+P-1)//P
print(ans)
print("flag=",flag)

Submission status: Runtime Error

Solution code:
 n,p = map(int,input().split())
    s = input()
    l = [0 for i in range(p)]
    l[0] = 1
    ten = 1
    cnt = 0
 
    ans = 0
    if p == 2 or p == 5:
        for i in range(n):
            if int(s[i]) % p == 0:
                ans += i+1
    else:
        for i in range(n):
            cnt = (cnt + int(s[-i-1]) * ten) % p
            l[cnt] += 1
            ten = (ten * 10) % p
        for i in l:
            if i > 1:
                ans += i * (i - 1) // 2
 
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

def solMin():
  dp=[[0]*P for i in range(N+1)]
  
  for i,s in enumerate(map(int,S), start=1):
    dp[i][s%P]+=1
    for p in range(P):
      dp[i][(p*10+s)]+=dp[i-1][p]
  
  return sum(dp[i][0] for i in range(N+1))

def solLarge():
  cnt=defaultdict(int)
  ret=0
  now=0
  
  for d,s in enumerate(map(int, S[::-1])):
    now+=pow(10,d,P)*s
    now%=P
    ret+=cnt[(now-P)%P]
    if now==0:
      ret +=1
    cnt[now]+=1
  
  return ret

print(solMin() if P*N<=10**6 else solLarge())

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n, p = [int(c) for c in input().split()]
s = input()    

if p in (2,5):
    a = tuple(int(c)%p for c in s)
    out = 0
    for i,x in enumerate(a):
        if x==0:
            out += (i + 1)
else:
    a = [0]*n
    tmp = 0
    for i in reversed(range(n)):
        tmp = (tmp + pow(10, n-i-1) * int(s[i])) % p
#         tmp = (tmp + 10**(n-i-1) * int(s[i])) % p
        a[i] = tmp
    d = {i: 0 for i in range(p)}
    d[0] = 1
    out = 0
    for x in a[::-1]:
        out += d[x]
        d[x] += 1
print(out)

Submission status: Runtime Error

Solution code:
input = _input().__next__
n, p = [int(c) for c in input().split()]
s = input()    

if p in (2,5):
    a = tuple(int(c)%p for c in s)
    out = 0
    for i,x in enumerate(a):
        if x==0:
            out += (i + 1)
else:
    a = [0]*n
    tmp = 0
    for i in reversed(range(n)):
        tmp = (tmp * 10 + int(s[i])) % p
        a[i] = tmp
    d = {i: 0 for i in range(p)}
    d[0] = 1
    out = 0
    for x in a[::-1]:
        out += d[x]
        d[x] += 1
print(out)

Submission status: Runtime Error

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

query = [""]*q
f = [""]*q
c = [""]*q

for i in range(q):
    query[i] = input()
    if query[i]=="1":
        s = s[::-1]
    else:
        r = query[i].split()
        if r[1]=="1":
            s = r[2]+s
        elif r[1]=="2":
            s += r[2]

print(s)

Submission status: Runtime Error

Solution code:
def main():
    n,p=map(int,input().split())
    s=input()
    cnt,ans=0,0
    m=[0]*p

    if p==2 or p==5:
        for i in s:
            if i%p==0:
                cnt+=1
        print(cnt*(cnt+1)//2)
        exit()

    for i in range(n):
        m[int(s[i:])%p]+=1
    
    for i in m:
        ans+=i*(i-1)//2
    ans+=m[0]

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
_, p = map(int,input().split())
s = input()
ss = []
for b in range(len(s)):
    for e in range(1,len(s)-b+1):
        ss.append(s[b:b+e])
print(len([int(i) for i in ss if int(i) % p==0]))

Submission status: Runtime Error

Solution code:
_, p = map(int,input().split())
s = input()
ss = []
for b in range(len(s)):
    for e in range(len(s)-b+1):
        ss.append(s[b:b+e])
print(len([int(i) for i in ss if i != '' and int(i) % p==0]))

Submission status: Runtime Error

Solution code:
_, p = input().split()
s = input()
ss = []
for b in range(len(s)):
    for e in range(len(s)-b+1):
        ss.append(s[b:b+e])
filtered = [int(i) for i in ss if i != '']
print(len([i for i in filtered if i % int(p) == 0]))

Submission status: Runtime Error

Solution code:
n, p = input().split()
s = input()
print(s)
ss = []
for b in range(len(s)):
    for e in range(len(s)-b+1):
        ss.append(s[b:b+e])
filtered = [int(i) for i in ss if i != '']
print(len([i for i in filtered if i % int(p) == 0]))

Submission status: Runtime Error

Solution code:
import numpy as np
N, P = map(int, input().split())
S = input()
ss = [0] * N
for i,s in enumerate(S):
  ss[i] = int(s)

vv = [0] * int((N*(N+1))/2)
cnt = 0
for i in range(N):
  for j in range(N-i):
    vv[cnt] = 0
    for k in range(j+1):
      vv[cnt] += ss[i+k]*pow(10,j-k)
    cnt += 1

count = 0
for i in range(int((N*(N+1))/2)):
  if vv[i] % P ==0:
    count += 1
print(count)

Submission status: Runtime Error

Solution code:
from collections import deque

n, p = map(int, input().split())
s = deque(list(input()))

def is_prime(p, s):
    if s % p == 0:
        return 1
    else:
        return 0

def str_num(s):
    return int(''.join(s))
  
  
cnt = 0
tmp = deque()
while len(s) >= 2:
    tmp.appendleft(s.pop())

    for i in range(len(s)):
        cnt += is_prime(p, str_num(s))
        cnt += is_prime(p, str_num(tmp))
        tmp.appendleft(s.pop())
    cnt += is_prime(p, str_num(tmp))
    tmp.pop()
    tmp.popleft()
    s, tmp = tmp, s


if n == 1:
    cnt += is_prime(str_num(s))

print(cnt)

Submission status: Runtime Error

Solution code:
N, P = map(int,input("").split(" "))
S = input("")
count = 0
for i in range(N):
  for j in range(N-i+1):
    tmp = int(S[j:j+i]) if i > 0 else int(S[j])
    if tmp % P == 0:
      count += 1
 
print(count)

Submission status: Runtime Error

Solution code:
N, P = map(int,input("").split(" "))
S = input("")
count = 0
for i in range(N):
  for j in range(N-i):
    tmp = int(S[j:j+i])
    if tmp % P == 0:
      count += 1

print(count)

Submission status: Runtime Error

Solution code:
n, p = list(map(int, input().split()))
s = input()
cnt = 0
for i in range(n):
    for j in range(i,n):
        s_ = int(s[i:j+1])
        if s_==0:
            cnt += 1
            continue
        elif p > s_:
            continue
        elif s_%p == 0:
            cnt += 1
            l.append(s_)
print(cnt)

Submission status: Runtime Error

Solution code:
from collections import deque

s=input()
q=int(input())

t=deque(s)
reverse=False

for i in range(q):
  query=input()
  if query[0]=='1':
    reverse=not reverse
  elif query[0]=='2':
    i,f,c=query.split()
    if f=='1':
      if reverse:
        t.append(c)
      else:
        t.appendleft(c)
    elif f=='2':
      if reverse:
        t.appendleft(c)
      else:
        t.append(c)
result=''.join(t)
if reverse:
  result=result[::-1]
print(result)

Submission status: Runtime Error

Solution code:
N,P=map(int,input().split())
S=str(input())
ans=0

if 10%P==0:
    for i in range(N):
        if int(S[i])%P==0:
            ans+=i+1
else:
    rem = [0]*P
    mod = 0
    ten = 1
    rem[mod]=1
    for i in range(N):
        mod=(mod+S[N-i-1]*ten)%P
        ten=ten*10%P
        rem[mod]+=1
    for j in rem:
        ans+=(j*(j-1))//2
print(ans)

Submission status: Runtime Error

Solution code:
n,p = list(map(int,input().split()))
S = input()

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,s,pre):
  return (s*i +pre)%p
 
M = [0]*p
M[0] = 1
t = 1
pre = 0
for s in S[::-1]:
  pre += (int(s)*t)%p
  M[pre] += 1
  t *= 10

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

Submission status: Runtime Error

Solution code:
n,p = list(map(int,input().split()))
S = input()

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

M = [0]*p
pre = 0
ans = 0
i = 1
for s in S[::-1]:
  pre += s*i
  pre %= p
  M[pre] += 1
  i *= 10

M[0] += 1
ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

Submission status: Runtime Error

Solution code:
N,P=map(int,input().split());S,a,i,j,c=[*map(int,input())],0,0,1,[1]+[0]*P
if 10%P:
	for v in S[::-1]:i=(i+v*j)%P;j=j*10%P;a+=c[i];c[i]+=1
else:
	for i,v in enumerate(S):
		if v%P<1:a+=i+1
print(a)

Submission status: Runtime Error

Solution code:
n, p = map(int, input().split())
s = input()

dic = {}
def calc_score(s):
    try:
        return dic[s]
    except:
        pass
    if len(s) == 0:
        return 0
    d = int(s)%p == 0
    if len(s) == 1:
        return d
    a = calc_score(s[1:])
    b = calc_score(s[:-1])
    c = calc_score(s[1:-1])
    score = a + b - c + d
    dic[s] = score
    return  score

print(calc_score(s))

Submission status: Runtime Error

Solution code:
n, p = map(int, input().split())
s = input()

ma = 2 * 10**5
ar = np.arange(ma)
ar = ar[ar%p == 0]
count = 0
for k in ar:
    count += s.count(str(k))
print(count)

Submission status: Runtime Error

Solution code:
n,p=input().split()
s=input()
def check(k):
  sbstr=""
  for i in range(k,n):
    sbstr+=s[i]
    if int(sbstr)%p==0:
      ans+=1

for k in range(n):
  check(k)
print(ans)

Submission status: Runtime Error

Solution code:
a = input()
b = input()
c = input()


def stack2(a, b):
    max_reduce = min(len(a), len(b))
    reduce = 0
    stacked = a + b
    for i in reversed(range(max_reduce)):
        a_end = a[len(a)-i-1:]
        b_begin = b[:i+1]
        flag = True
        for j in range(len(a_end)):
            if a_end[j] != b_begin[j] and a_end[j] != '?' and b_begin[j] != '?':
                flag = False
                break
        if flag == True:
            reduce = len(a_end)
            a_begin = a[:len(a) - i - 1]
            b_end = b[i+1:]
            mid = ''
            for k in range(i+1):
                if a_end[k] != '?':
                    letter = a_end[k]
                else:
                    letter = b_begin[k]
                mid = mid + letter
            stacked = a_begin + mid + b_end
            break
    return stacked, reduce

S = len(a) + len(b) + len(c)

r1 = stack2(a, b)[1] + stack2(stack2(a, b)[0], c)[1]
r2 = stack2(a, c)[1] + stack2(stack2(a, c)[0], b)[1]
r3 = stack2(b, a)[1] + stack2(stack2(b, a)[0], c)[1]
r4 = stack2(b, c)[1] + stack2(stack2(b, c)[0], a)[1]
r5 = stack2(c, a)[1] + stack2(stack2(c, a)[0], b)[1]
r6 = stack2(c, b)[1] + stack2(stack2(c, b)[0], a)[1]

r = max(r1, r2, r3, r4, r5, r6)

print(S-r)

Submission status: Runtime Error

Solution code:
a = input()
b = input()
c = input()


def stack2(a, b):
    max_reduce = min(len(a), len(b))
    reduce = 0
    stacked = a + b
    for i in reversed(range(max_reduce)):
        a_end = a[len(a)-i-1:]
        b_begin = b[:i+1]
        flag = True
        for j in range(len(a_end)):
            if a_end[j] != b_begin[j] and a_end[j] != '?' and b_begin[j] != '?':
                flag = False
                break
        if flag == True:
            reduce = len(a_end)
            a_begin = a[:len(a) - i - 1]
            b_end = b[i+1:]
            mid = ''
            for k in range(i+1):
                if a_end[k] != '?':
                    letter = a_end[k]
                else:
                    letter = b_begin[k]
                mid = mid + letter
            stacked = a_begin + mid + b_end
            break
    return stacked, reduce

S = len(a) + len(b) + len(c)

r1 = stack2(a, b)[1] + stack2(stack2(a, b)[0], c)[1]
r2 = stack2(a, c)[1] + stack2(stack2(a, c)[0], b)[1]
r3 = stack2(b, a)[1] + stack2(stack2(b, a)[0], c)[1]
r4 = stack2(b, c)[1] + stack2(stack2(b, c)[0], a)[1]
r5 = stack2(c, a)[1] + stack2(stack2(c, a)[0], b)[1]
r6 = stack2(c, b)[1] + stack2(stack2(c, b)[0], a)[1]

r = max(r1, r2, r3, r4, r5, r6)

print(S-r)

Submission status: Runtime Error

Solution code:

n,p = list(map(int,input().split()))
s = input()

M = [s[-n:] for n in range(1,n+1)]
M = list(map(lambda x:int(x)%p, M))

ans = 0
U = set(M)

for u in U:
  cnt = M.count(u)
  if u == 0:
    ans += (cnt*(cnt+1))//2
  else:
    ans += (cnt*(cnt-1))/2

print(int(ans))

Submission status: Runtime Error

Solution code:
n, p = map(int, input().split())
s = input()

res = 0

if p == 2 or p == 5:
	for i in range(n, 0, -1):
		if s[i-1]%p == 0:
			res += i
else:
	l = [0]*p
	l[0] = 1
	for i in range(n):
		l[int(s[i:])%p] += 1

	for e in l:
		res += e*(e-1)//2
  
print(res)

Submission status: Runtime Error

Solution code:
n,p = map(int, input().split())
s = input()
x = 0
if(p == 5):
    for i in range(n):
        if(s[i]%5 == 0):
            x += i+1
else:
    for j in range(1,n+1):
        if(int(s[-j:])%p == 0):
            x += 1
        #print(s[-j:])
    for i in range(1,n):
        for j in range(1,n-i+1):
            if(int(s[-i-j:-i])%p == 0):
                x += 1
            #print(s[-i-j:-i])
print(x)

Submission status: Runtime Error

Solution code:
n, p = map(int, input().split())
s = input()

res = 0

if p == 2 or p == 5:
  for i in range(n, 0, -1):
    if s[i-1]%p == 0:
      res += i
else:
  l = [0]*p
  l[0] = 1
  for i in range(n):
    l[int(s[i:])%p] += 1

  for e in l:
    res += e*(e-1)//2
  
print(res)