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: Wrong Answer

Solution code:
def examA():
    S = SI()
    if S=="AAA" or S=="BBB":
        print("No")
    else:
        print("Yes")
    return

def examB():
    N, A, B = LI()
    loop = N//(A+B)
    ans = loop*A + min(A,N%(A+B))
    print(ans)
    return

def examC():
    A, B = LI()
    ans = -1
    for i in range(1,20000):
        if i*8//100==A:
            if i*10//100==B:
                ans = i
                break
    print(ans)
    return

def examD():
    S = SI()
    Q = I()
    rev = 0
    L = ""; R = ""
    for _ in range(Q):
        q = LSI()
        if q[0]=="1":
            rev += 1
        else:
            c = int(q[1])
            if (c+rev)%2==1:
                L += q[2]
            else:
                R += q[2]
    ans = ""
    if rev%2==0:
        ans = L[::-1] + S + R
    else:
        ans = R[::-1] + S[::-1] + L
    print(ans)
    return

def examE():
    N, P = LI()
    S = SI()
    A = [0]*(N+1)
    cur = 0
    if P==5:
        ans = 0
        for i in range(N):
            if int(S[N-1-i])%5==0:
                ans += N-i
        print(ans)
        return
    elif P==2:
        ans = 0
        for i in range(N):
            if int(S[N-1-i])%2==0:
                ans += N-i
        print(ans)
        return

    for i in range(N):
        s = int(S[N-1-i])
        cur += s*pow(10,i,P)
        A[i+1] = cur%P
    D = [0]*P
    for a in A:
        D[a] += 1
    ans = 0
    print(A)
    for d in D:
        ans += d*(d-1)//2

    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
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 LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Wrong Answer

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

mod = p

cnt = [0]*mod

f = 1
ans = 0
cur = 0
for i in reversed(range(n)):
    cur += f*t[i]
    cur %= mod
    ans += cnt[cur]
    cnt[cur] += 1
    if cur == 0:
        ans += 1
    f *= 10
    f %= mod
print(ans)

Submission status: Wrong Answer

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

mods = [0] * n

for i,c in enumerate(reversed(s)):
    mods[i] = pow(10,i,p) * int(c) % p
mods.reverse()
ruiseki = [0] * (n+1)


for i,m in enumerate(mods):
    ruiseki[i+1] = (ruiseki[i] + m) % p

# log(mods)
# log(ruiseki)

ruiseki2 = list(sorted(ruiseki))
ruiseki2.append(999999999999999)

prev = ruiseki2[0]
prev_i = 0

# log(ruiseki2)

ans = 0

for i,r in enumerate(ruiseki2):
    if i==0:
        continue
    if r != prev:
        l = i-prev_i
        # log(i,r,l)
        ans += l*(l-1)//2
        prev = r
        prev_i = i
    # log(i, r, ans)

# for m in mods:
#     if m == 0:
#         ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N, P = map(int, input().split())
S = list(map(int, list(input())[: -1]))
cs = [0] * (N + 1)
for i in range(N): cs[i + 1] = (cs[i] * 10 + S[i]) % P
d = dd(list)
for i in range(N):d[cs[i + 1]].append(i)
#//10していくぞ
res = 0
for i in range(N):
  x = cs[i]
  revx = (x * pow(pow(10, i + 1, P), P - 2, P)) % P
  j = bl(d[revx], i)
  res += len(d[revx]) - j
  #print(res, i, j, x, revx)
print(res)

Submission status: Wrong Answer

Solution code:
def ext_gcd(a, b, x, y):
    if b == 0:
        x[0] = 1
        y[0] = 0
        return a
    
    d = ext_gcd(b, a % b, y, x)
    y[0] -= a // b * x[0]

    return d

def get_inv(n, p):
    x = [1]
    y = [1]
    ext_gcd(n, p, x, y)
    return x[0] % p

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

for i in range(n):
    s[i] = int(s[i]) % p

ls = [0]
p10 = [1]

for i in range(n):
    ls.append((ls[i] * 10 + s[i]) % p)
    p10.append(p10[i] * 10 % p)

mp = [0 for i in range(p)]
ans = 0

for i in range(n + 1):
    tmp = get_inv(p10[i], p)
    ans += mp[ls[i] * tmp % p]
    mp[ls[i] * tmp % p] += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
S=input()
a=0
l=[pow(10,i,P) for i in range(10)]
for i in range(-1,-11,-1):
    t=0
    c=[0]*P
    for k in range(i,-N-1,-1):
        if (i-k)%10==0:
            c[t%P]+=1
        t=(t+int(S[k])*l[(i-k)%10])%P
        a+=c[t%P]
print(a)

Submission status: Wrong Answer

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

d = {i:0 for i in range(p)}

for si in s:
    si = int(si)
    a = (pre * 10 + si) % p
    ans += d[a]
    if a == 0:
        ans += 1
    d[a] += 1
    pre = a
print(ans)

Submission status: Wrong Answer

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

if P==2 or P==5:
    ans = N*(N+1)//2
    for s in S:
        if s%P!=0: ans-=1
    print(ans)
    exit()

R = [None]*N
k = 1
for i in range(N-1, -1, -1):
    R[i] = S[i]*k%P
    k*=10

ans = 0
X = []
x = 0
for r in R:
    x  = (x+r)%P
    X.append(x)

D = [0]*P
D[0] = 1
for x in X:
    ans += D[x]
    D[x]+=1

print(ans)

Submission status: Wrong Answer

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

if p == 2:
    l = list(s)
    ans = 0
    for i in xrange(n):
        if s[i] in '02468':
            LEN = i + 1
            ans += ((LEN * (LEN + 1)) / 2)
    print ans
    exit()

if p == 5:
    l = list(s)
    ans = 0
    for i in xrange(n):
        if s[i] in '05':
            LEN = i + 1
            ans += ((LEN * (LEN + 1)) / 2)
    print ans
    exit()

n = len(s)
l = [0 for i in xrange(n + 1)]

l[n] = int(s[n - 1])
if l[n] >= p: l[n] %= p

p10 = 1
for i in xrange(n - 1, 0, -1):
    p10 *= 10
    if p10 >= p: p10 %= p
    l[i] = p10 * (ord(s[i - 1]) - ord('0'))
    if l[i] >= p: l[i] %= p

cnt = [0 for i in xrange(p)]
cnt[l[0]] += 1
for i in xrange(1, n + 1):
    l[i] += l[i - 1]
    if l[i] >= p: l[i] -= p

    cnt[l[i]] += 1

ans = 0
for i in xrange(p):
    ans += ((cnt[i] * (cnt[i] - 1)) / 2)

print ans

Submission status: Wrong Answer

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

if P in (2,5,10):
    ans = 0
    for i,c in enumerate(S):
        c = int(c)
        if c%P==0:
            ans += (i+1)
    print(ans)
else:
    a = [0]
    for c in S:
        c = int(c)
        a.append((a[-1]*10+c) % P)
    from collections import Counter
    ctr = Counter(a)
    ans = 0
    for k,v in ctr.items():
        ans += v*(v-1)//2
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N, P = map(int, input().split())
S = list(map(int, list(input())[: -1]))
cs = [0] * (N + 1)
for i in range(N): cs[i + 1] = (cs[i] * 10 + S[i]) % P
d = dd(list)
for i in range(N):d[cs[i + 1]].append(i)
#//10していくぞ
res = 0
for i in range(N):
  x = cs[i]
  revx = (x * pow(pow(10, i + 1), P - 2, P)) % P
  j = bl(d[revx], i)
  res += len(d[revx]) - j
  #print(res, i, j, x, revx)
print(res)

Submission status: Wrong Answer

Solution code:
import sys
N, P = sys.stdin.readline().split()
N = int(N)
P = int(P)
S = sys.stdin.readline()

counts = [0] * P
d = 0
r = 0
k = 1
answer = 0
for i in range(N - 1, -1, -1):
    c = int(S[i])
    r += c * k
    r %= P
    answer += counts[r]
    counts[r] += 1
    k *= 10
print(answer + counts[0])

Submission status: Wrong Answer

Solution code:
def examA():
    S = SI()
    if S=="AAA" or S=="BBB":
        print("No")
    else:
        print("Yes")
    return

def examB():
    N, A, B = LI()
    loop = N//(A+B)
    ans = loop*A + min(A,N%(A+B))
    print(ans)
    return

def examC():
    A, B = LI()
    ans = -1
    for i in range(1,20000):
        if i*8//100==A:
            if i*10//100==B:
                ans = i
                break
    print(ans)
    return

def examD():
    S = SI()
    Q = I()
    rev = 0
    L = ""; R = ""
    for _ in range(Q):
        q = LSI()
        if q[0]=="1":
            rev += 1
        else:
            c = int(q[1])
            if (c+rev)%2==1:
                L += q[2]
            else:
                R += q[2]
    ans = ""
    if rev%2==0:
        ans = L[::-1] + S + R
    else:
        ans = R[::-1] + S[::-1] + L
    print(ans)
    return

def examE():
    N, P = LI()
    S = SI()
    A = [0]*(N+1)
    cur = 0
    for i in range(N):
        s = int(S[N-1-i])
        cur += s*pow(10,i,P)
        A[i+1] = cur%P
    D = [0]*P
    for a in A:
        D[a] += 1
    ans = 0
    #print(A)
    for d in D:
        ans += d*(d-1)//2

    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
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 LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Wrong Answer

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

mods = [0] * n

for i,c in enumerate(reversed(s)):
    mods[i] = pow(10,i,p) * int(c) % p
mods.reverse()
ruiseki = [0] * (n+1)


for i,m in enumerate(mods):
    ruiseki[i+1] = (ruiseki[i] + m) % p

# log(mods)
# log(ruiseki)

ruiseki2 = list(sorted(ruiseki[1:]))
ruiseki2.append(999999999999999)
ans = 0

prev = ruiseki2[0]
prev_i = 0

# log(ruiseki2)

if prev == 0:
    ans += 1

for i,r in enumerate(ruiseki2):
    if i==0:
        continue
    if r == 0:
        ans += 1
    if r != prev:
        l = i-prev_i
        # log(i,r,l)
        ans += l*(l-1)//2
        prev = r
        prev_i = i
    # log(i, r, ans)



print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

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

acc = [0] * N
cur = S[0] % P
acc[0] = cur
for i in range(1, N):
    cur *= 10
    cur += S[i]
    cur %= P
    acc[i] = cur
acc = [0] + acc

C = Counter(acc)
ans = 0
for v in C.values():
    ans += v * (v-1) // 2
print(ans)

Submission status: Wrong Answer

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

rem=[0]*p
remls=[0]*n
remnow=0
for i in range(n-1,-1,-1):
    remnow = (remnow+int(s[i])*pow(10, n-1-i, p))%p
    rem[remnow]+=1
    remls[i]=remnow

ans=0
remnow2=0
for i in range(n-1,-1,-1):
    ans+=rem[remnow2]
    remnow2-=int(s[i])
    remnow2%=p
    remnow2*=pow(10,p-2,p)
    remnow2%=p
    rem[remls[i]]-=1

print(ans)

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
l=list(input())
for i in range(n):
    l[i]=int(l[i])
r=[0]
rt=0
z=[0]*p
for i in range(n):
    rt+=l[n-1-i]*(10**i)%p
    rt%=p
    z[rt]+=1
ans=z[0]
w=0
for i in range(n):
    w-=l[n-1-i]
    w%=p
    ans+=z[w]
print(ans)

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=input()[::-1]
l=[int(c) for c in s]
ll=[0 for i in range(p)]
now=0
for i in l:
    now*=10
    now+=i
    now%=p
    ll[now]+=1
res=0
for i in range(p):
    res+=ll[i]*(ll[i]-1)//2
res+=ll[0]
print(res)

Submission status: Wrong Answer

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

count = 0

for left in range(N//2):
    for right in range(left+1, N-left):
        # print(left, right, S[left:right], S[right:N-left])
        if int(S[left:right]) % P == 0:
            count += 1
        if int(S[right:N-left]) % P == 0:
            count += 1
    if int(S[left:N-left]) % P == 0:
        count += 1
    # print(S[left:N-left])

        # if int(S[left:right]) % P == 0:
        #     count += 1
print(count)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

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

mods = []
s = s[::-1]
mod = 0
for i, ch in enumerate(s):
    mod = (mod + int(ch) * pow(10, i, p))  % p
    mods.append(mod)

cnt = [0] * p
cnt[0] += 1
for item in mods:
    cnt[item] += 1
ans = 0
for item in cnt:
    ans += item * (item - 1) // 2
print(ans)

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = input()
C = [0]*p
now = 0
for num, i in enumerate(s):
  a = int(i)
  now = (now+pow(10, num, p)*a)%p
  C[now] += 1
ans = C[0]
for c in C:
  ans += c*(c-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=input()
pmod=[0]*p
buf=0
for i in range(n):
    buf*=10
    buf%=p
    buf+=int(s[i])
    buf%=p
    pmod[buf]+=1
count=0
for i in range(p):
    if pmod[i]==0:
        continue
    if i==0:
        count+=pmod[i]*(pmod[i]+1)//2
    else:
        count+=pmod[i]*(pmod[i]-1)//2
#print(pmod)
print(count)

Submission status: Wrong Answer

Solution code:
import itertools
import os
import sys
from collections import defaultdict

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

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

N, P = list(map(int, sys.stdin.buffer.readline().split()))
S = sys.stdin.buffer.readline().decode().rstrip()
MOD = P


def test():
    ans = 0
    counts = defaultdict(int)
    for l, r in itertools.combinations_with_replacement(range(N), 2):
        ans += int(S[l:r + 1]) % P == 0
        counts[r] += int(S[l:r + 1]) % P == 0
    print(counts)
    s = 0
    for r in reversed(range(N)):
        s += counts[r]
        print(s)
    print()
    print(ans)
    print()


# test()

div10 = pow(10, P - 2, P)
mod_counts = [0] * P
n = 0
for c in S[::-1]:
    n = (n * 10 + int(c)) % P
    mod_counts[n] += 1

ans = 0
offset = 0
for i in reversed(range(N)):
    ans += mod_counts[offset % P]
    mod_counts[(int(S[i]) - offset) % P] -= 1
    offset += -int(S[i])
    offset *= div10
    offset %= P
print(ans)

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = input()
K = int(S)
s = P
ans = 0
while s <= K:
    ans += S.count(str(s))
    s += P
print(ans)

Submission status: Wrong Answer

Solution code:
n, p = map(int, raw_input().strip().split())
s = raw_input().strip()
n = len(s)
l = [0 for i in xrange(n + 1)]

l[n] = int(s[n - 1])
if l[n] >= p: l[n] %= p

p10 = 1
for i in xrange(n - 1, 0, -1):
    p10 *= 10
    if p10 >= p: p10 %= p
    l[i] = p10 * (ord(s[i - 1]) - ord('0'))
    if l[i] >= p: l[i] %= p

cnt = [0 for i in xrange(p)]
cnt[l[0]] += 1
for i in xrange(1, n + 1):
    l[i] += l[i - 1]
    if l[i] >= p: l[i] -= p

    cnt[l[i]] += 1

ans = 0
for i in xrange(p):
    ans += ((cnt[i] * (cnt[i] - 1)) / 2)

print ans

Submission status: Wrong Answer

Solution code:
from collections import Counter

N,P = map(int,input().split())
S = list(reversed(input()))
A = [0]*N

h = 1

for _ in range(N):
    A[_] = int(S[_]) * h
    A[_] %= P
    h *= 10
    h %= P

B = [0]*(N+1)

for _ in range(N):
    B[_+1] = (A[_] + B[_])%P

#print(''.join(map(str,S)))
#print(B)

su = 0

for k,v in Counter(B).items():
    if v != 1:
        su += v * (v - 1) // 2

print(su)

Submission status: Wrong Answer

Solution code:
def examA():
    S = SI()
    if S=="AAA" or S=="BBB":
        print("No")
    else:
        print("Yes")
    return

def examB():
    N, A, B = LI()
    loop = N//(A+B)
    ans = loop*A + min(A,N%(A+B))
    print(ans)
    return

def examC():
    A, B = LI()
    ans = -1
    for i in range(1,20000):
        if i*8//100==A:
            if i*10//100==B:
                ans = i
                break
    print(ans)
    return

def examD():
    S = SI()
    Q = I()
    rev = 0
    L = ""; R = ""
    for _ in range(Q):
        q = LSI()
        if q[0]=="1":
            rev += 1
        else:
            c = int(q[1])
            if (c+rev)%2==1:
                L += q[2]
            else:
                R += q[2]
    ans = ""
    if rev%2==0:
        ans = L[::-1] + S + R
    else:
        ans = R[::-1] + S[::-1] + L
    print(ans)
    return

def examE():
    N, P = LI()
    S = SI()
    A = [0]*(N+1)
    cur = 0
    for i in range(N):
        cur += int(S[N-1-i])*(10**i)
        A[i+1] = cur%P
    C = Counter(A)
    #print(A)
    #print(C)
    ans = 0
    for i,j in C.items():
        ans += j*(j-1)//2

    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
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 LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Wrong Answer

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

S = input()

d = 1

counts = [0] * P
counts[0] = 1
h = 0
total = 0

for s in reversed(S):
	m = int(s) * d % P
	h += m
	total += counts[h % P]
	counts[h % P] += 1
	d = (d * 10) % P

print(total)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate,chain
from collections import defaultdict

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

n = 1
T = [None]*N
for i in reversed(range(N)):
    T[i] = (n*S[i])%P
    n *= 10
    n %= P
T = tuple(chain((0,),accumulate(T, lambda a,b: (a+b)%P)))



cnt = 0
c = defaultdict(int)
for t in T:
    cnt += c[t%P]
    c[t] += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
n,p = (int(num) for num in input().split())
s = input()
s = s[::-1]

dec = [1] * n
for i in range(1,n):
    dec[i] = (dec[i-1] * 10) % p
s_mod = [0] * n
for i in range(n):
    s_mod[i] = (int(s[i]) * dec[i]) % p
    
#print(dec)
#int(s_mod)
    
cumsum = [0] * (n + 1)
cnt = [1] + [0] * (p - 1)
for i in range(n):
    cumsum[i + 1] = (cumsum[i] +  s_mod[i]) % p
    cnt[cumsum[i+1]] += 1
#print(cumsum)
    
ans = 0
for i in range(p):
    ans += cnt[i] * (cnt[i] - 1) // 2
print(ans)

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = input()
C = [0]*p
now = 0
for num, i in enumerate(s):
  a = int(i)
  now = (now+pow(10, num, p)*a)%p
  C[now] += 1
ans = C[0]
now = 0
for num, i in enumerate(s[:-1]):
  a = int(i)
  now = (now+pow(10, num, p)*a)%p
  C[now] -= 1
  ans += C[now]
print(ans)

Submission status: Wrong Answer

Solution code:
def modpow(x, n, p):
    res = 1
    while n > 0:
        if n & 1:
            res = res * x % p
        x = x * x % p
        n >>= 1
    return res

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

for i in range(n):
    s[i] = int(s[i]) % p

ls = [0]
p10 = [1]

for i in range(n):
    ls.append((ls[i] * 10 + s[i]) % p)
    p10.append(p10[i] * 10 % p)

mp = [0 for i in range(p)]
ans = 0

for i in range(n + 1):
    ans += mp[ls[i] * modpow(p10[i], p - 2, p) % p]
    mp[ls[i] * modpow(p10[i], p - 2, p) % p] += 1

print(ans)

Submission status: Wrong Answer

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

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)

# print(xx)
# print(yy)

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


print(ans)

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
L=list(input())
A=[]
AMARI=0
for i in range(N):
    A.append((AMARI*10+int(L[i]))%P)
    AMARI=A[-1]
#print(A)
ZERO=0
D={}
ans=0
for i in range(N):
    if A[i] not in D:
        D[A[i]]=1
        if A[i]==0:
            ans+=1
    else:
        if A[i]==0:
            ans+=D[A[i]]+1
        else:
            ans+=D[A[i]]
        D[A[i]]+=1
#print(D)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N, P = sys.stdin.readline().split()
N = int(N)
P = int(P)
S = sys.stdin.readline()

counts = [0] * P
d = 0
k = 1
answer = 0
for i in range(N - 1, -1, -1):
    c = int(S[i])
    d = c * k + d
    k *= 10
    r = d % P
    answer += counts[r]
    counts[r] += 1
    if r == 0:
        answer += 1
print(answer)

Submission status: Wrong Answer

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

L = [0 for i in range(P)]
ans = 0

for i in range(N):
  s = int(S[i])
  nL = [0 for i in range(P)]
  for j in range(P):## ADD s
    nj = (j * 10 + s) % P
    nL[nj] += L[j]
  L = nL.copy()
  ans += L[0]
print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,p = LI()
    s = list(map(int, input()))
    if p in [2,5]:
        ans = 0
        for i in range(n):
            si = s[i]
            ans += i
            if si%p == 0:
                ans += 1
        print(ans)
        return
    a = [0]
    k = pow(10,p-2,p)
    K = k
    for i in range(n):
        si = s[i]
        a.append((a[-1]+si*K)%p)
        K *= k
        K %= p
    ans = 0
    d = defaultdict(lambda : 0)
    for i in a:
        ans += d[i]
        d[i] += 1
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n,p = nm()
s = list(map(int, list(ns())))
g = [0]*(n+1)
d = [0]*p
d[0] = 1
ans = 0
for i in range(n):
    g[i+1] = (g[i]*10 + s[i])%p
    ans += d[g[i+1]]
    d[g[i+1]] += 1
print(ans)

Submission status: Wrong Answer

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

ans = 0
data = [0 for _ in range(p)]
now = 0
data[0] = 1
for i in range(n):
    now = 10*now + s[i]
    now %= p
    data[now] += 1

for x in range(p):
    ans += (data[x]*(data[x]-1))//2
print(ans)

Submission status: Wrong Answer

Solution code:
n, p = map(int, raw_input().strip().split())
s = raw_input().strip()
n = len(s)
l = [0 for i in xrange(n)]

l[n - 1] = int(s[n - 1])
if l[n - 1] >= p: l[n - 1] %= p

p10 = 1
for i in xrange(n - 2, -1, -1):
    p10 *= 10
    if p10 >= p: p10 %= p
    l[i] = p10 * (ord(s[i]) - ord('0'))
    if l[i] >= p: l[i] %= p

l.append(0)

cnt = [0 for i in xrange(p)]
cnt[l[0]] += 1
for i in xrange(1, n + 1):
    l[i] += l[i - 1]
    if l[i] >= p: l[i] -= p

    cnt[l[i]] += 1

ans = 0
for i in xrange(p):
    ans += ((cnt[i] * (cnt[i] - 1)) / 2)

print ans

Submission status: Wrong Answer

Solution code:
def examA():
    S = SI()
    if S=="AAA" or S=="BBB":
        print("No")
    else:
        print("Yes")
    return

def examB():
    N, A, B = LI()
    loop = N//(A+B)
    ans = loop*A + min(A,N%(A+B))
    print(ans)
    return

def examC():
    A, B = LI()
    ans = -1
    for i in range(1,20000):
        if i*8//100==A:
            if i*10//100==B:
                ans = i
                break
    print(ans)
    return

def examD():
    S = SI()
    Q = I()
    rev = 0
    L = ""; R = ""
    for _ in range(Q):
        q = LSI()
        if q[0]=="1":
            rev += 1
        else:
            c = int(q[1])
            if (c+rev)%2==1:
                L += q[2]
            else:
                R += q[2]
    ans = ""
    if rev%2==0:
        ans = L[::-1] + S + R
    else:
        ans = R[::-1] + S[::-1] + L
    print(ans)
    return

def examE():
    N, P = LI()
    S = SI()
    A = [0]*(N+1)
    cur = 0
    for i in range(N):
        cur += int(S[i])*(10**i)
        A[i+1] = cur%P
    C = Counter(A)
    #print(C)
    ans = 0
    for i,j in C.items():
        ans += j*(j-1)//2

    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
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 LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Wrong Answer

Solution code:
import sys, collections
range = xrange
input = raw_input

n, p = [int(x) for x in input().split()]
A = [ord(x) - 48 for x in input()]

DP = [0]*p
ans = 0
POW = 1
ind0 = 0
for a in reversed(A):
    DP[ind0] += 1
    #DP = [DP[(a * POW + i) % p] for i in range(p)]
    ind0 = (a * POW + ind0) % p
    ans += DP[ind0]
    POW = POW * 10 % p
print ans

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,p = LI()
    s = list(map(int, input()))
    a = [0]
    k = pow(10,p-2,p)
    if p == 5:
        k = 1
    K = k
    for i in range(n):
        si = s[i]
        a.append((a[-1]+si*K)%p)
        K *= k
        K %= p
    ans = 0
    d = defaultdict(lambda : 0)
    for i in a:
        ans += d[i]
        d[i] += 1
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
N, P = sys.stdin.readline().split()
N = int(N)
P = int(P)
S = sys.stdin.readline()

counts = [0] * P
d = 0
k = 1
answer = 0
for i in range(N - 1, -1, -1):
    c = int(S[i])
    d = c * k + d
    k *= 10
    r = d % P
    answer += counts[r]
    counts[r] += 1
answer += counts[0]
print(answer)

Submission status: Wrong Answer

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

s2 = s[::-1]
rems = [0]
tmp = 0
for i in range(n):
    tmp = tmp * 10 + int(s2[i])
    tmp %= p
    rems.append(tmp)

if p == 2 or p == 5:
    ans = 0
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    from collections import Counter
    counter = Counter(rems)
    ans = 0
    for key in counter.keys():
        v = counter[key]
        ans += v * (v - 1) // 2
print(ans)