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 main():
    N, P = map( int ,input().split())
    S = [ int(s) for s in list(input())]
    if P == 2 or P == 5:
        ans = 0
        for i in range(N-1,-1,-1):
            if S[i]%P == 0:
                ans += N-i
        print(ans)
        return
    L = [0]*P
    L[0] = 1
    t = 0
    s = 1
    for i in range(N-1,-1,-1):
        t = (S[i]*s+t)%P
        L[t] += 1
        s = s*10%P
    ans = 0
    for l in L:
        ans += l*(l-1)//2
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, P = map( int ,input().split())
    S = [ int(s) for s in list(input())][::-1]
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if S[i]%P == 0:
                ans += N-i
        print(ans)
        return
    L = [0]*P
    L[0] = 1
    t = 0
    s = 1
    for i in range(N):
        t = (S[i]*s+t)%P
        L[t] += 1
        s *= 10
        s %= 10
    ans = 0
    for l in L:
        ans += l*(l-1)//2
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, P = map( int ,input().split())
    S = [ int(s) for s in list(input())][::-1]
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if S[i]%P == 0:
                ans += N-i
        print(ans)
        return

    
    L = [0]*P
    L[0] = 1
    t = 0
    for i in range(N):
        t = (S[i]*pow(10,i,P)+t)%P
        print(t)
        L[t] += 1
    ans = 0
    for l in L:
        ans += l*(l-1)//2
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
np = input().split(" ")
sdata = input() 

n = int(np[0])
p = int(np[1])
cnt = 0
for pick_size in range(1, n ):
  for id in range( n - pick_size + 1 ): 
    val = int(sdata[id:id+pick_size+1])
    if( val % p == 0 ):
      cnt+=1
      
print( cnt )

Submission status: Wrong Answer

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

d = [0]*(N+1)
# d[N-1] = 1

if 10%P == 0:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i + 1
    print(ans)
else:
    ## 10の何乗か
    ten = 1
    ## 一桁目から、Pの余りを累積和
    for i in range(N-1,-1,-1):
        a = int(S[i]) * ten % P
        d[i] = (d[i+1]+a)%P
        ten *= 10
        ten %= P

    ## dの値を累積カウントする
    counter = [0]*P
    print(d)
    for j in range(N, -1, -1):
        ans += counter[d[j]]
        print(ans)
        counter[d[j]] += 1

    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import copy
import queue
def LI(): return [int(x) for x in input().split()]
n,p = LI()
s = input()
cnt = 0
if p == 2 or p == 5:
    for i in range(n-1,-1,-1):
       if int(s[i]) % p == 0:
           cnt += (i+1)
else:
    num = 0
    p_cnt = [1] + [0 for _ in range(p-1)]
    for i in range(n-1,-1,-1):
        num = num * 10 + int(s[i])
        m = num % p
        p_cnt[m] += 1
        num %= p
    for i in range(p):
        cnt += p_cnt[i] * (p_cnt[i]-1) // 2
print (cnt)

Submission status: Wrong Answer

Solution code:
import sys
import math
import copy
import queue
def LI(): return [int(x) for x in input().split()]
n,p = LI()
s = input()
cnt = 0
if p == 2 or p == 5:
    for i in range(n-1,-1,-1):
       if int(s[i]) % p == 0:
           cnt += (i+1)
else:
    num = 0
    p_cnt = [0 for _ in range(p)]
    for i in range(n-1,-1,-1):
        num = num * 10 + int(s[i])
        m = num % p
        p_cnt[m] += 1
    for i in range(p):
        cnt += p_cnt[i] * (p_cnt[i]-1) // 2
    cnt += p_cnt[0]
print (cnt)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")
MOD = 10**9+7


def div(a, b, mod=MOD):
    return (a * pow(b, mod-2, mod)) % mod


def solve(N: int, P: int, S: str):

    if P == 2 or P == 5:
        count = 0
        for i in range(N):
            if int(S[i]) % P == 0:
                count += i+1
        print(count)
        return
    else:
        ans = 0
        DP = [0]*P
        zero = 0
        cnal = int(S[0]) % P
        for i in range(N):
            if i != 0:
                c = int(S[i]) % P
                cnal = zero
                zero = div((zero-c) % P, 10, P)
            # print(zero, cnal)
            # print(DP)
            DP[cnal] += 1
            ans += DP[zero]

        print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = str(next(tokens))  # type: int
    solve(N, P, S)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
S=list(map(int,list(input())))
L=[s%P for s in S]
ans=L.count(0)
for i in range(1,N):
  L=[(L[j+1]+(S[j]*10**i))%P for j in range(N-i)]
  ans+=L[:-i].count(0)
print(ans)

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
S=list(map(int,list(input())))
from collections import defaultdict
d = defaultdict(int)
_=0
ans=0
for i in range(N):
  _+=S[N-1-i]*10**i
  x=_%P
  ans+=d[x]
  if x==0:
    ans+=1
  d[x]+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import copy
import queue
def LI(): return [int(x) for x in input().split()]
n,p = LI()
s = [int(x) for x in list(input())]
cnt = 0
if p == 2 or p == 5:
    for i in range(n-1,-1,-1):
       if s[i] % p == 0:
           cnt += (i+1)
else:
    num = 0
    s.append(0)
    p_cnt = [0 for _ in range(p)]
    for i in range(n,-1,-1):
        num = num * 10 + s[i]
        m = num % p
        p_cnt[m] += 1
    for i in range(p):
        cnt += p_cnt[i] * (p_cnt[i]-1) // 2

print (cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

s = input()

if 10 % p == 0:
    ans = sum(i + 1 for i, x in enumerate(s))
    print(ans)
else:
    li = [0] * (n + 1)
    for i, x in enumerate(s[::-1]):
        li[i+1] = (li[i] + (int(x) * (10**(i+1)) % p)) % p

    ans = 0
    c = Counter(li[1:])
    ans = sum(v * (v - 1) for v in c.values()) // 2
    ans += c[0]
    print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")
MOD = 10**9+7


def div(a, b, mod=MOD):
    return (a * pow(b, mod-2, mod)) % mod


def solve(N: int, P: int, S: str):

    if P == 2 or P == 5:
        count = 0
        for i in range(N):
            if int(S[i]) % P == 0:
                count += i+1
        print(count)
        return
    else:
        ans = 0
        DP = [0]*P
        zero = 0
        cnal = 0
        for i in range(N):
            c = int(S[i]) % P
            DP[zero] += 1
            cnal = zero
            zero = div(zero - c, 10, P)
            ans += DP[zero]

        print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = str(next(tokens))  # type: int
    solve(N, P, S)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def solve(N: int, P: int, S: str):
    ans = 0
    DP = [0]*P
    for i in range(N):
        c = int(S[i]) % P
        nDP = [0]*P
        nDP[c % P] += 1
        for p in range(P):
            nDP[(10*p + c) % P] += DP[p]
        DP = nDP
        print(DP)
        ans += DP[0]
    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = str(next(tokens))  # type: int
    solve(N, P, S)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from collections import defaultdict

def main():
    N, P = map(int, input().split())
    S = input()
    S_rev = S[::-1]
    ans = 0
    if P == 2:
        for i in range(N):
            if int(S_rev[i]) % 2 == 0:
                ans += N - i
        print(ans)
        exit()
    elif P == 5:
        for i in range(N):
            if int(S_rev[i]) % 5 == 0:
                ans += N - i
        print(ans)
        exit()
    S_mod = [0] * N
    ten = 1
    for i in range(N):
        S_mod[i] = (int(S[i]) * ten) % P
        ten *= 10
        ten % P

    C = [0] + list(accumulate(S_mod))
    d = defaultdict(int)
    for i in range(N+1):
        C[i] %= P
        d[C[i]] += 1

    for i, j in d.items():
        ans += j * (j - 1) // 2

    print(ans)





if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from collections import defaultdict

def main():
    N, P = map(int, input().split())
    S = input()
    S_rev = S[::-1]
    ans = 0
    if P == 2:
        for i in range(N):
            if int(S_rev[i]) % 2 == 0:
                ans += N - i
        print(ans)
        exit()
    elif P == 5:
        for i in range(N):
            if int(S_rev[i]) % 5 == 0:
                ans += N - i
        print(ans)
        exit()
    S_mod = [0] * N
    tmp = ""
    for i in range(N):
        tmp = S_rev[i] + tmp
        S_mod[i] = int(tmp) % P

    C = list(accumulate(S_mod))
    d = defaultdict(int)
    for i in range(N):
        C[i] %= P
        d[C[i]] += 1

    for i, j in d.items():
        ans += j * (j - 1)

    print(ans)





if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split(' '))
S =list(map(int,list(input()[::-1])))
ans = 0
cnt = [0]*P
cnt[0]=1
tmp = 0
for n,i in enumerate(S):
    d=i*pow(10,n,P)
    tmp =(tmp+d)%P
    cnt[tmp] += 1
if P==2 or P==5:
    if P==2:
        check=[0,2,4,6,8]
    else:
        check=[0,5]
    for n,i in enumerate(S[::-1]):
        if i in check:
            ans += N-n
else:
    for i in cnt:
        ans += i*(i-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split(' '))
S =list(map(int,list(input()[::-1])))
ans = 0
cnt = [0]*P
cnt[0]=1
tmp = 0
for n,i in enumerate(S):
    tmp +=i*pow(10,n,P)
    tmp %=P
    cnt[tmp] += 1
if P==2 or P==5:
    if P==2:
        check=[0,2,4,6,8]
    else:
        check=[0,5]
    for n,i in enumerate(S[::-1]):
        if int(i) in check:
            ans += N-n
else:
    for i in cnt:
        ans += i*(i-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split(' '))
S =list(map(int,list(input()[::-1])))
ans = 0
cnt = [0]*P
cnt[0]=1
tmp = 0
for n,i in enumerate(S):
    tmp +=i*pow(10,n)
    tmp %=P
    cnt[tmp%P] += 1
if P==2 or P==5:
    if P==2:
        check=[0,2,4,6,8]
    else:
        check=[0,5]
    for n,i in enumerate(S[::-1]):
        if int(i) in check:
            ans += N-n
else:
    for i in cnt:
        ans += i*(i-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, P = map(int, input().split())
S = input()

def smallSol():
    T = [0] * (N + 1)
    for i, s in enumerate(map(int, S[:: -1])):
        T[i + 1] = (s * pow(10, i, P) + T[i]) % P

    ans = 0
    cnt = Counter(T[1:])
    for p in range(P):
        x = cnt[p]
        ans += x * (x - 1) // 2
    ans += cnt[0]
    return ans

def largeSol():
    dp = [0] * P
    ans = 0
    for s in map(int, S):
        newDp = [0] * P
        for p in range(P):
            newDp[(s * 10 + p) % P] += dp[p]
        dp = newDp
        ans += dp[0]
    return ans

print(smallSol() if N * P <= 10**7 else largeSol())

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, P = map(int, input().split())
S = input()

def smallSol():
    T = [0] * (N + 1)
    for i, s in enumerate(map(int, S[:: -1])):
        T[i + 1] = (s * pow(10, i, P) + T[i]) % P

    ans = 0
    cnt = Counter(T[1:])
    for p in range(P):
        x = cnt[p]
        ans += x * (x - 1) // 2
    ans += cnt[0]
    return ans

def largeSol():
    dp = [0] * P
    ans = 0
    for s in map(int, S):
        newDp = [0] * P
        for p in range(P):
            newDp[(s * 10 + p) % P] += dp[p]
        ans += dp[0]
    return ans

print(smallSol() if N * P <= 10**7 else largeSol())

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split(' '))
S =list(map(int,list(input()[::-1])))
ans = 0
cnt = [0]*P
cnt[0]=1
tmp = 0
for n,i in enumerate(S):
    tmp +=i*10**n
    tmp %=P
    cnt[tmp] += 1
if P==2 or P==5:
    if P==2:
        check=[0,2,4,6,8]
    else:
        check=[0,5]
    for n,i in enumerate(S[::-1]):
        if int(i) in check:
            ans += N-n
else:
    for i in cnt:
        ans += i*(i-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split(' '))
S =list(map(int,list(input()[::-1])))
ans = 0
cnt = [0]*P
cnt[0]=1
tmp = 0
for i in S:
    tmp =tmp*10+i
    cnt[tmp%P] += 1
if P==2 or P==5:
    if P==2:
        check=[0,2,4,6,8]
    else:
        check=[0,5]
    for n,i in enumerate(S):
        if int(i) in check:
            ans += N-n
else:
    for i in cnt:
        ans += i*(i-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from collections import Counter

I = lambda s:map(int, s)

p = int(input().split()[1])
s = input()
if 10 % p == 0:
  r = sum(i for i, x in enumerate(I(s), 1) if x % p == 0)
else:
  c = Counter()
  c[0] = 1
  y = 1
  for i, x in enumerate(I(reversed(s)), 1):
    c[x * y % p] += 1
  r = sum(i * (i - 1) // 2 for i in c.values())
print(r)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from collections import Counter

p = int(input().split()[1])
s = input()
if 10 % p == 0:
  r = sum(i for i, x in enumerate(s, 1) if x in range(0, 10, p))
else:
  a = accumulate(int(x) * pow(10, i, p) for i, x in enumerate(reversed(s), 1))
  c = Counter(x % p for x in a) 
  c[0] += 1
  r = sum(i * (i - 1) // 2 for i in c.values())
print(r)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from collections import Counter

p = int(input().split()[1])
a = enumerate(reversed(input()), 1)
if 10 % p == 0:
  r = sum(i for i, x in a if x in range(0, 10, p))
else:
  a = accumulate(int(x) * pow(10, i, p) for i, x in a)
  c = Counter(x % p for x in a) 
  c[0] += 1
  r = sum(i * (i - 1) // 2 for i in c.values())
print(r)

Submission status: Wrong Answer

Solution code:
n, P = map(int, input().split())
S = input()
ans = 0
#----------------------------------------------
# 1.
# int(S[a:b]) * 10 ** (n - b) == (int(S[a: n]) - int(S[b: n])) で表される
# 例
# S = 1234
# a = 1, b = 3 のとき
# 23 = (234 - 4) // 10 ** (4 - 3)
#    =  230 // 10
#    =  23
#
# 2.
# Pは素数のため　P = 2, 5　のとき以外は　１０の約数でない
# A * (10 ** x) が Pで割れるとき　A は P の倍数　(x は任意定数)
#
# 3.
# 1. の式を mod P で考える
# int(S[a: b]) * 10 ** (n - b) == (int(S[a: n]) - int(S[b: n]))
# ⇒　(S[a: b] * 10 ** (n - b)) % P == (S[a: n] - S[b: n]) % P  (mod P)
# ⇒　(S[a: b] % P) * (10 ** (n - b) % P) == (S[a: n] % P) - (S[b: n] % P)  (mod P)
# 2.より P = 2, 5以外のときは 10 ** (n - b) % P != 0となるため
# (S[a: n] % P) - (S[b: n] % P)　= 0　すなわち　(S[a: n] % P) == (S[b: n] % P)のとき
# S[a:b] % P　= 0である
#
# これより
# S[i: n] % P (0 <= i < n) を求めれば
# 以下のコードのようにS[i: j] % P を求めることができる (0 <= i < n, i <= j < n)
#----------------------------------------------
#まずS[i: n] % P (0 <= i < n) を求める (remain に格納する)
remain = [0] * P
remain[0] += 1
d = 1
left = 0
for i in range(n):
    print(left)
    left = (left + int(S[n - i - 1]) * d) % P
    remain[left] += 1
    d = d * 10 % P
# print(remain)
for r in remain:
    ans += r * (r - 1) // 2
#----------------------------------------------
# 4.P = 2, 5　のときについて考える
#     1. P = 2 のとき
#         ある数の下１桁が2の倍数のとき、その数は2の倍数であるため
#         S[i] % 2 == 0 のとき
#         S[h:i] % 2 == 0 (0 <= h <= i)
#         よって以下のようなコードで答えを求めることができる
#----------------------------------------------
if P == 2:
    ans = 0
    for i in range(n):
        if int(S[i]) % 2 == 0:
            ans += i + 1
    print(ans)
#----------------------------------------------
    # 2. P = 5 のときもP = 2 のときと同様に考えれば良いため
#----------------------------------------------
if P == 5:
    ans = 0
    for i in range(n):
      if int(S[i]) % 5 == 0:
          ans += i + 1
    print(ans)
if P != 2 and P != 5:
    print(ans)

Submission status: Wrong Answer

Solution code:
n, P = map(int, input().split())
S = input()
ans = 0
#----------------------------------------------
# 1.
# int(S[a:b]) * 10 ** (n - b) == (int(S[a: n]) - int(S[b: n])) で表される
# 例
# S = 1234
# a = 1, b = 3 のとき
# 23 = (234 - 4) // 10 ** (4 - 3)
#    =  230 // 10
#    =  23
#
# 2.
# Pは素数のため　P = 2, 5　のとき以外は　１０の約数でない
# A * (10 ** x) が Pで割れるとき　A は P の倍数　(x は任意定数)
#
# 3.
# 1. の式を mod P で考える
# int(S[a: b]) * 10 ** (n - b) == (int(S[a: n]) - int(S[b: n]))
# ⇒　(S[a: b] * 10 ** (n - b)) % P == (S[a: n] - S[b: n]) % P  (mod P)
# ⇒　(S[a: b] % P) * (10 ** (n - b) % P) == (S[a: n] % P) - (S[b: n] % P)  (mod P)
# 2.より P = 2, 5以外のときは 10 ** (n - b) % P != 0となるため
# (S[a: n] % P) - (S[b: n] % P)　= 0　すなわち　(S[a: n] % P) == (S[b: n] % P)のとき
# S[a:b] % P　= 0である
#
# これより
# S[i: n] % P (0 <= i < n) を求めれば
# 以下のコードのようにS[i: j] % P を求めることができる (0 <= i < n, i <= j < n)
#----------------------------------------------
#まずS[i: n] % P (0 <= i < n) を求める (remain に格納する)
remain = [0] * P
remain[0] += 1
d = 1
left = 0
for i in range(n):
    left = (left + int(S[n - i - 1]) * d) % P
    remain[left] += 1
    d = d * 10 % P

for r in remain:
    ans += r * (r - 1) // 2
#----------------------------------------------
# 4.P = 2, 5　のときについて考える
#     1. P = 2 のとき
#         ある数の下１桁が2の倍数のとき、その数は2の倍数であるため
#         S[i] % 2 == 0 のとき
#         S[h:i] % 2 == 0 (0 <= h <= i)
#         よって以下のようなコードで答えを求めることができる
#----------------------------------------------
if P == 2:
    ans = 0
    for i in range(n):
        if int(S[i]) % 2 == 0:
            ans += i + 1
    print(ans)
#----------------------------------------------
    # 2. P = 5 のときもP = 2 のときと同様に考えれば良いため
#----------------------------------------------
if P == 5:
    ans = 0
    for i in range(n):
      if int(S[i]) % 2 == 0:
          ans += i + 1
    print(ans)
if P != 2 and P != 5:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, P = MAP()
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)

else:
	tmp = ""

	mod_dic = defaultdict(int)

	for i, s in enumerate(S[::-1]):
		tmp += s
		mod_dic[int(tmp)%P] += 1
	ans = 0
	for v in mod_dic.values():
		ans += v*(v-1)//2
	print(ans+mod_dic[0])

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, P = MAP()
S = input()

if P == 2 or P == 5:
	tmp = ""
	cnt = [0]*(N+1)

	for i, s in enumerate(S):
		tmp += s
		if int(tmp)%P == 0:
			cnt[i+1] = i+1
		else:
			cnt[i+1] = cnt[i]
	print(sum(cnt))

else:
	tmp = ""

	mod_dic = defaultdict(int)

	for i, s in enumerate(S[::-1]):
		tmp += s
		mod_dic[int(tmp)%P] += 1
	ans = 0
	for v in mod_dic.values():
		ans += v*(v-1)//2
	print(ans+mod_dic[0])

Submission status: Wrong Answer

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

sys.setrecursionlimit(10**7)
inf=10**20
mod=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 [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,p=LI()
  s=S()

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

  _s=list(s)
  _s.reverse()

  a=[]
  i=0
  for x in _s:
    b=(10**i*int(x))%p
    a.append(b)
    i+=1

  b=[0]*p
  b[a[0]%p]=1
  for i in range(n-1):
    a[i+1]+=a[i]
    a[i+1]%=p
    b[a[i+1]]+=1

  for i,x in enumerate(b):
    if i==0:
      ans+=x
    if x>1:
      ans+=x*(x-1)//2

  return ans

# main()
print(main())

Submission status: Wrong Answer

Solution code:
import numpy as np
import collections

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

s1 = ""
s2 = ""
answer = 0
s= [0]

for i in range(N-1,-1,-1):
    s.append(int(S[i-1:N])%P)

#print(s)

#co = np.mod(s,P)
c = collections.Counter(s)
for x in c.values():
    answer +=x*(x-1) // 2
#answer=np.count_nonzero(co == 0 )
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, P = [int(x) for x in input().split()]
    S = input().strip()

    M = [0] * N
    for i, s in enumerate(S[::-1]):
        M[i] = (int(s) * (10 ** i)) % P

    MA = []
    MA.append(M[0])
    c = collections.Counter()
    ans = 0
    c[0] += 1
    ans += c[MA[0]]
    c[M[0]] += 1
    for i in range(1, N):
        MA.append((MA[i - 1] + M[i]) % P)
        ans += c[MA[i]]
        c[MA[i]] += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, P = [int(x) for x in input().split()]
    S = input().strip()

    M = [0] * N
    for i, s in enumerate(S[::-1]):
        M[i] = (int(s) * (10 ** i)) % P

    MA = []
    MA.append(M[0])
    for i in range(1, N):
        MA.append((MA[i - 1] + M[i]) % P)

    MA.append(0)

    c = collections.Counter(MA)
    ans = 0
    for i in range(P):
        ans += max(0, (c[i] * (c[i] - 1)) // 2)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
'''
Fuad Ashraful Mehmet 
University of Asia Pacific
Date:07th march 2020
'''

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

s=input()
f=[]

for c in s:
    f.append(int(c))

ans=0
if p==2:
    num=0
    for i in range(n-1,-1,-1):
        num=num*10+f[i]
        num=num%p
        if not num:
            ans+=i+1
elif p==5:
    num=0
    for i in range(n-1,-1,-1):
        num=num*10+f[i]
        num=num%p
        if not num:
            ans+=i+1

else:
    pre=[0]*10005
    pre[0]=1
    ans=0
    num=0
    x=1
    for i in range(n-1,-1,-1):
        num=num*10+f[i]
        num=num%p
       # x=(x*10)%p

        ans+=pre[num]
        pre[num]+=1


print(ans)

Submission status: Wrong Answer

Solution code:
'''
Fuad Ashraful Mehmet 
University of Asia Pacific
Date:07th march 2020
'''

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

s=input()
f=[]

for c in s:
    f.append(int(c))

ans=0
if p==2:
     
    for i in range(n):
        if not f[i]%p:
            ans+=i+1
    
elif p==5:
    for i in range(n):
        if not f[i]%p:
            ans+=i+1

else:
    pre=[0]*10005
    pre[0]=1
    ans=0
    num=0
    x=1
    for i in range(n-1,-1,-1):
        num=num*x+f[i]
        num=num%p
        x=(x*10)%p

        ans+=pre[num]
        pre[num]+=1


print(ans)

Submission status: Wrong Answer

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

    TF = 2, 5
    if p in TF:
        answer = 0
        for i, char in enumerate(s):
            if int(char) % p == 0:
                answer += i + 1
        print(answer)
        return

    # u = [int(s[i:]) for i in range(n)]
    u = []
    t = 0
    for i, char in enumerate(s[::-1]):
        t += 10 ** i * int(char)
        u.append(t)
    u = u[::-1]
    u.append(0)
    # The numbers to consider are int(s[i:j]) (0 <= i < j <= n)
    # u[i] := int(s[i:]) (u[n] = 0 for convenience)
    # int(s[i:j]) and u[i] - u[j] are congruent (unless p == 2 or 5)
    remainders = [number % p for number in u]
    d = {}
    return
    for remainder in remainders:
        if remainder not in d:
            d[remainder] = 1
        else:
            d[remainder] += 1
    answer = 0
    for count in d.values():
        if count > 1:
            answer += count * (count - 1) // 2
    print(answer)

main()

Submission status: Wrong Answer

Solution code:
'''
Fuad Ashraful Mehmet 
University of Asia Pacific
Date:07th march 2020
'''

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

s=input()
f=[]

for c in s:
    f.append(int(c))

ans=0
if p==2:
     
    for i in range(n):
        if not f[i]%p:
            ans+=i+1
    
elif p==5:
    for i in range(n):
        if not f[i]%p:
            ans+=i+1

else:
    pre=[0]*10005
    pre[0]=1
    ans=0
    num=0
    for i in range(n-1,-1,-1):
        num=num*10+f[i]
        num=num%p

        ans+=pre[num]
        pre[num]+=1


print(ans)

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = list(map(int,list(input())))
mod = P
Cum = []
S.reverse()


temp = 0
power = 1
for i in range(N):
    temp += (S[i]*power)%mod
    temp %= mod
    power *= 10
    power %= mod
    Cum.append(temp)

from collections import Counter

counter=Counter(Cum)

counter[0]+=1

ans = 0
for i in counter:
    ans += int(counter[i]*(counter[i]-1)/2)
print(ans)

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = list(map(int,list(input())))
mod = P
Cum = []
S.reverse()

if 10%P!=0: 
    temp = 0
    power = 1
    for i in range(N):
        temp += (S[i]*power)%mod
        temp %= mod
        power *= 10
        power %= mod
        Cum.append(temp)

    from collections import Counter

    counter=Counter(Cum)

    counter[0]+=1

    ans = 0
    for i in counter:
        ans += int(counter[i]*(counter[i]-1)/2)
    print(ans)    

else:
    print(0)

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = list(map(int,list(input())))
mod = P
Cum = []
S.reverse()

if 10%P!=0: 
    temp = 0
    for i in range(N):
        temp += (S[i]*(10**i))%mod
        temp = temp%mod
        Cum.append(temp)

    from collections import Counter

    counter=Counter(Cum)

    counter[0]+=1

    ans = 0
    for i in counter:
        ans += int(counter[i]*(counter[i]-1)/2)
    print(ans)    

else:
    print(0)

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = list(map(int,list(input())))
mod = P
Cum = []
S.reverse()

if 10%P!=0: 
    temp = 0
    for i in range(N):
        temp += (S[i]*(10**i))%mod
        temp = temp%mod
        Cum.append(temp)

    from collections import defaultdict

    counter = defaultdict(int)
    for x in Cum:
        counter[x] += 1

    counter[0]+=1

    ans = 0
    for i in counter:
        ans += int(counter[i]*(counter[i]-1)/2)
    print(ans)
else:
    print(0)

Submission status: Wrong Answer

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

    TF = 2, 5
    if p in TF:
        answer = 0
        for i, char in enumerate(s):
            if int(char) % p == 0:
                answer += i + 1
        print(answer)
        return

    u = [int(s[i:]) for i in range(n)]
    u.append(0)
    # The numbers to consider are int(s[i:j]) (0 <= i < j <= n)
    # u[i] := int(s[i:]) (u[n] = 0 for convenience)
    # int(s[i:j]) and u[i] - u[j] are congruent (unless p == 2 or 5)
    remainders = [number % p for number in u]
    d = {}
    return
    for remainder in remainders:
        if remainder not in d:
            d[remainder] = 1
        else:
            d[remainder] += 1
    answer = 0
    for count in d.values():
        if count > 1:
            answer += count * (count - 1) // 2
    print(answer)

main()

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = list(input())
mod = P
Cum = []
S.reverse()
temp = 0
for i in range(N):
    temp += (int(S[i])*(10**i))%mod
    temp = temp%mod
    Cum.append(temp)
    
from collections import Counter

counter=Counter(Cum)

counter[0]+=1

ans = 0
for i in counter:
    ans += int(counter[i]*(counter[i]-1)/2)
print(ans)

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = list(input())
mod = P
Cum = []
S.reverse()
temp = 0
for i in range(N):
    temp += (int(S[i])*(10**i))%mod
    temp = temp%mod
    Cum.append(temp)
    
from collections import defaultdict

counter = defaultdict(int)
for x in Cum:
    counter[x] += 1

counter[0]+=1

ans = 0
for i in counter:
    ans += int(counter[i]*(counter[i]-1)/2)
print(ans)