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:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,mod = map(int,input().split())
S = list(map(int,input()))
tenpow = 1
for i in range(n-1,-1,-1):
  S[i] = S[i] * tenpow % mod
  tenpow = tenpow * 10 % mod
acum = [0]*(n+1)
for i in range(n):
  acum[i+1] = (acum[i]+S[i]) % mod
C = collections.Counter(acum)
for key,item in C.items():
  ans += (item-1) * item //2
print(ans)

Submission status: Wrong Answer

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

MOD = p

mods = [0 for _ in range(MOD)]
mods[0] = 1

num = 0
digit = 1
for s in S[::-1]:
  num = s * digit + num
  num %= MOD
  mods[num] += 1
  digit = (digit * 10) % MOD
  
ans = 0
for m in mods:
  ans += m * (m - 1) // 2

print(ans)

Submission status: Wrong Answer

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

# do shakutori
#以下が an mod p を求めるソースコードです.
def power_func(a, n, p):
    res = 1 #これは答え
    while n > 0:
        if n & 1:
            res = res * a % p
        a = a * a % p #1が立っているかどうかに関わらず次のaの累乗を用意しておく
        n = n >> 1
    return res

Q = [0]
for i in range(len(S)-1, -1, -1):
    pow = len(S) - i - 1
    Q.append((Q[-1] + power_func(10, pow, P) * int(S[i])) % P)
# print(Q)

import collections
dct = dict(collections.Counter(Q))
# print(dct)
ans = 0
for val in dct.values():
    ans += val * (val - 1) // 2
print(ans)

Submission status: Wrong Answer

Solution code:
n,p = map(int,input().split())
s = input()
A = [int(c) for c in s]
ju = [1]
for _ in range(n):
  ju.append(ju[-1]*10%p)
B = [A[i]*ju[i]%p for i in range(n)]

from collections import Counter

B = Counter(B).most_common()
ans = 0
for _,count in B:
  if count == 1:
    break
  ans += count*(count-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N,P = LMIIS()
    S = input()[::-1]
    R = [0]*P
    R[0] = 1
    b = 1
    r = 0
    for c in S:
        r += b * int(c)
        r %= P
        R[r] += 1
        b *= 10
        b %= P
    ans = 0
    for r in R:
        ans += r*(r-1)//2
    print(ans)
        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N,P = map(int,input().split())
    S = input()[::-1]
    ans = 0
    if P == 2 or P == 5:
        for i,s in enumerate(S):
            if int(s) % P == 0:
                ans += N - i
    else:
        mods = [0] * P
        mods[0] = 1
        current = 0
        x = 0
        for s in S:
            current = (current + x * int(s)) % P
            ans += mods[current % P]
            mods[current % P] += 1
            x = x * 10 % P
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

def main():
    N,P = map(int,input().split())
    S = input()
    ans = 0
    if P == 2 or P == 5:
        for i,s in enumerate(S):
            if int(s) % P == 0:
                ans += N-i
    else:
        D = [0] * (N+1)
        for i in range(N):
            D[i] = int(S[N-1-i:N+1]) % P
        C = Counter(D)
        ans = sum([c*(c-1)//2 for c in C.values()])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

def main():
    N,P = map(int,input().split())
    S = input()[::-1]
    ans = 0
    if P == 2 or P == 5:
        for i,s in enumerate(S):
            if int(s) % P == 0:
                ans += N-i
    else:
        D = [0] * (N+1)
        for i in range(N):
            print(S[:i+1][::-1])
            D[i] =  int(S[:i+1][::-1]) % P
        C = Counter(D)
        ans = sum([c*(c-1)//2 for c in C.values()])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

def main():
    N,P = map(int,input().split())
    S = input()[::-1]
    ans = 0
    if P == 2 or P == 5:
        for i,s in enumerate(S):
            if int(s) % P == 0:
                ans += N-i
    else:
        D = [0] * (N+1)
        for i in range(N+1):
            D[i] =  int(S[:i+1][::-1]) % P
        C = Counter(D)
        ans = sum([c*(c-1)//2 for c in C.values()])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

N,P=map(int, sys.stdin.readline().split())
S=sys.stdin.readline().strip()
S=S[::-1]

L=[0] 
val=0
for i,x in enumerate(S):
    val+=pow(10,i,P)*int(x)
    L.append(val%P)

C=defaultdict(lambda: 0)    #mod2019の値の出現個数を記録
ans=0
for x in L:
    ans+=C[x]   #自分とmod2019の結果が同じ値となる出現個数をansに足す
    C[x]+=1     #自分のmod2019の値を出現個数に+1カウント
print ans

Submission status: Wrong Answer

Solution code:
from collections import Counter

def main():
    N,P = map(int,input().split())
    S = input()[::-1]
    ans = 0
    if P == 2 or P == 5:
        for i,s in enumerate(S):
            if int(s) % P == 0:
                ans += N-i
    else:
        D = [0] * (N)
        for i in range(N):
            D[i] =  int(S[:i+1][::-1]) % P
        C = Counter(D)
        ans = sum([c*(c-1)//2 for c in C.values()])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

def main():
    N,P = map(int,input().split())
    s = list(input())[::-1]
    ary_mod = [0] * P
    ary_mod[0] = 1
    now = 0
    digit = 1
    for i, ss in enumerate(s):
        now += int(ss) * digit % P
        digit *= 10
        digit %= P
        remind = now % P
        ary_mod[remind] += 1
    ans = 0
    for i, n in enumerate(ary_mod):
        ans += (n*(n-1)) // 2
    print(ans)
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

ans = 0
if p == 2 or p == 5:
  for i in range(n):
    if int(s[i]) % p == 0:
      ans += (i+1)
'''
else:      
  mods = [0]*(n+1)
  mods[0] = 1
  m = 0
  d = 1  
  for i in range(n):    
    m = (m + int(s[-i-1])*d) % p
    d = (d * 10) % p    
    mods[m] += 1
  
  for i in range(n):
    ans += mods[i]*(mods[i]-1)//2
'''
print(ans)

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
l = [0] * p
cur_base = 0
ans = 0
k = 1
for d in map(int, reversed(input())):
    l[cur_base] += 1
    cur_base = (cur_base - d * k) % p
    k = k * 10 % p
    ans += l[cur_base]
print(ans)

Submission status: Wrong Answer

Solution code:
# Problem E - Divisible Substring

from collections import Counter

# 組み合わせ
def combinations_count(n, r):
    return n * (n - 1) // r

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

# count
if P==2 or P==5:
    ans = 0
    for i in range(N-1, -1, -1):
        s = int(S[i])
        if s%P==0:
            ans += i + 1
    # output
    print(ans)
else:
    p_nums = [0]*(N+1)
    s = ""
    for i in range(N-1, -1, -1):
        s += S[i]
        p_nums[N - i] = int(s)%P
    p_counter = Counter(p_nums)
    ans = 0
    for key in p_counter.keys():
        p_c = p_counter[key]
        if p_c>=2:
            ans += combinations_count(p_c, 2)
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

def nCr(n,r):
  ret = 1
  for i in range(r):
    ret *= (n-i)
    ret //= i+1
  return ret    

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

ans = 0
if p == 2:
  for i in range(n):
    if int(s[i])%2 == 0:
      ans += (i+1)
      
elif p== 5:
  for i in range(n):
    if int(s[i])%5 == 0:
      ans += (i+1)
      
else:      
  mods = [0]*(n+1)
  t = ''
  for i in range(n):
    t = t + s[i]
    mods[i] = int(t)%p
  
  c = Counter(mods)
  for k,v in c.items():
    if v > 1:
      ans += nCr(v,2)

print(ans)

Submission status: Wrong Answer

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]*P
    ans=0
    for i in range(N+1):
        ans+=l[S[i]]
        l[S[i]]+=1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
N,MOD=map(int,input().split())
S=input()
Cum=[0]*(N+1)
for i in range(N):
    Cum[i+1]=(Cum[i]+int(S[N-i-1])*pow(10,i,MOD))%MOD
c=Counter(Cum).most_common()
res=0
for a,b in c:
    res+=b*(b-1)//2
    if(b==1):
        break
print(res)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
dd = defaultdict(int)
n,p=map(int, input().split())
S = list(input().rstrip())
tmp = 0
r=1
su=0

if p==2 or p==5:
    c=n
    for s in S[::-1]:
        if int(s)%p==0:
            su+=c
        c-=1
    print(su)
else:
    for s in S[::-1]:
        tmp+=int(s)*r
        r*=10
        tmp%=p
        r%=p
        dd[tmp]+=1
    for i in dd.values():
        su+=(i*(i-1))//2
    print(su)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
dd = defaultdict(int)
n,p=map(int, input().split())
S = list(input().rstrip())
tmp = 0
dd[0]+=1
r=1
su=0
if not p%2==0 or not p%5==0:
    for s in S[::-1]:
        tmp+=int(s)*r
        r*=10
        tmp%=p
        r%=p
        dd[tmp]+=1
    for i in dd.values():
        su+=(i*(i-1))//2
    print(su)

else:
    c=n
    for s in S[::-1]:
        if int(s)%p==0:
            su+=c
        c-=1
    print(su)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
dd = defaultdict(int)
n,p=map(int, input().split())
S = list(input().rstrip())
tmp = 0
dd[0]+=1
r=1
su=0
if not p%2==0 or p%5==0:

    for s in S[::-1]:
        tmp+=int(s)*r
        r*=10
        tmp%=p
        r%=p
        dd[tmp]+=1
    for i in dd.values():
        su+=(i*(i-1))//2
    print(su)

else:
    c=n
    for s in S[::-1]:
        if int(s)%p==0:
            su+=c
        c-=1
    print(su)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
dd = defaultdict(int)
n,p=map(int, input().split())
S = list(input().rstrip())
tmp = 0
dd[0]+=1
r=1

for s in S[::-1]:
    tmp+=int(s)*r
    r*=10

    tmp%=p
    r%=p
    dd[tmp]+=1
su=0
for i in dd.values():
    su+=(i*(i-1))//2
print(su)

Submission status: Wrong Answer

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
        print(ans)
        return

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

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


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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] * (P)
    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: Wrong Answer

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

if P%2 == 0 or P%5 == 0:
    ans = 0
    S = S[::-1]
    for i,j in enumerate(S):
        if int(j)%P == 0:
            ans += i+1
    print(ans)
else:
    tmp = 0
    mod = [0]*P
    mod[0] = 1
    S = S[::-1]
    for i,j in enumerate(S):
        tmp = (tmp + int(j)*pow(10,i,P))%P
        mod[tmp] += 1    
    print(sum([i*(i-1)//2 for i in mod]))

Submission status: Wrong Answer

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

if P%2 == 0 or P%5 == 0:
    ans = 0
    S = S[::-1]
    for i,j in enumerate(S):
        if int(j)%P == 0:
            ans += i+1
    print(ans)
else:
    tmp = 0
    mod = [0]*P
    ##mod[0] = 1
    S = S[::-1]
    for i,j in enumerate(S):
        tmp = (tmp + int(j)*pow(10,i,P))%P
        mod[tmp] += 1    
    print(sum([i*(i-1)//2 for i in mod]))

Submission status: Wrong Answer

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

if P%2 == 0 or P%5 == 0:
    ans = 0
    S = S[::-1]
    for i in range(len(S)):
        if int(S[i])%P == 0:
            ans += i+1
    print(ans)
else:
    tmp = 0
    mod = [0]*P
    mod[0] = 1
    S = S[::-1]
    for i,j in enumerate(S):
        tmp = (tmp + int(j)*pow(10,i,P))%P
        mod[tmp] += 1    
    print(sum([i*(i-1)//2 for i in mod]))

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = [int(i) for i in input()]
from collections import Counter
def solve(S,N,P):
    cum = [0]*(N+1)
    mods = [0]*N
    mods[0] = 1
    for i in range(1,N):
        mods[i] = mods[i-1]*10%P
    for i in range(N):
        cum[i+1] = (cum[i]+S[N-1-i]*mods[i])%P
    c = Counter(cum)
    ans = 0
    for v in c.values():
        ans += v*(v-1)//2
    return ans
print(solve(S,N,P))

Submission status: Wrong Answer

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

def solve(S,N,P):
    if P == 2:
        ans = 0
        for i in range(N):
            if int(S[i])%P == 0:
                ans += i+1
        return ans
    if P == 5:
        ans = 0
        for i in range(N):
            if int(S[i])%P == 0:
                ans += i+1
        return ans
    
    S = S[::-1]
    mod_list = [0]*P
    mod_list[0] = 1

    mod = P
    tmp = 0

    for i in range(N):
        tmp = (tmp + int(S[i])*pow(10,i,mod))%mod
        mod_list[tmp] += 1
    
    ans = 0
    for i in mod_list:
        ans += i*(i-1)//2
        
    return ans

solve(S,N,P)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


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


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N, P = MI()
    s = list(map(int, S()[::-1]))
    ans = 0
    sum_of_d = 0
    cnts = [0] * P
    cnts[0] = 1
    A = [0] * N
    D = [0] * N

    if P == 2 or P == 5:
        for i in range(N):
            if s[i] % P == 0:
                ans += N - i
        print(ans)
        return

    for i in range(N):
        d = s[i] * pow(10, i, P)
        A[i] = d % P
        if i == 0:
            D[i] = A[i]
        else:
            D[i] = (D[i-1] + A[i]) % P
        # sum_of_d = (sum_of_d + d) % p
        # cnts[sum_of_d] += 1

    for d in D:
        cnts[d] += 1

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

    print(ans)

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = list(input())
s.reverse()
r = [0 for _ in range(p)]
x = 0
for i in range(len(s)):
    x += pow(10, i, p) * int(s[i])
    x %= p
    r[x] += 1
ans = 0
for i in r:
    if i >= 2:
        ans += ((i - 1) * i) // 2
ans += r[0]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if int(S[i]) % P == 0:
                ans += i + 1
    else:
        val = [0] * P
        cur = 0
        tenfactor = 1
        val[cur] += 1
        for i in range(N):
            cur = (cur + int(S[N - i - 1]) * tenfactor) % P
            tenfactor *= 10
            tenfactor %= 10
            val[cur] += 1

        ans = 0
        for v in val:
            ans += v * (v - 1) // 2

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

if P == 2 or P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i+1
    print(ans)
else:
    mod_cnt = {}
    for i in range(1,N+1):
        mod = int(S[-i:N]) % P
        if mod in mod_cnt:
            mod_cnt[mod] += 1
        else:
            mod_cnt[mod] = 1
    ans = 0
    for cnt in mod_cnt.values():
        ans += (cnt * (cnt-1)) // 2
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if int(S[i]) % 2 == 0:
                ans += i + 1
    else:
        val = [0] * P
        val[0] += 1
        for i in range(N):
            cur = int(S[N - i - 1 :]) % P
            val[cur] += 1

        ans = 0
        for v in val:
            ans += v * (v - 1) // 2

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n, p = list(map(int, input().split()))
# a = list(map(int, input().split()))
s = input()
rem = [0 for i in range(p)]
total = 0
ans = 0
for i in range(len(s)-1, -1, -1):
    total += int(s[i])*pow(10, len(s)-i-1, p)
    total %= p
    if total % p == 0:
        ans += 1
    ans += rem[total]
    rem[total] += 1


print(ans)

Submission status: Wrong Answer

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

if P == 2 or P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i+1
    print(ans)
else:
    mod_cnt = {}
    for i in range(N+1):
        mod = int(S[-i:N]) % P
        if mod in mod_cnt:
            mod_cnt[mod] += 1
        else:
            mod_cnt[mod] = 1
    ans = 0
    for cnt in mod_cnt.values():
        ans += (cnt * (cnt-1)) // 2
    print(ans)

Submission status: Wrong Answer

Solution code:
def main():
  n,p=map(int,input().split())
  s=input()[::-1]
  x=[0]*p
  x[0]=1
  a,t=0,1
  for i in range(n):
    a=(a+int(s[i])*t)%p
    x[a]+=1
    t=(t*10)%p
  ans=sum([i*(i-1)//2 for i in x])
  print(ans)
if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=input()[::-1]
ans=0
u=0
d=1
l=[0]*p
l[0]=1
for i in map(int,s):
  u=(u+i*d)%p
  l[u]+=1
  d=d*10%p
for i in l:
  ans+=i*(i-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys


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

    if P == 2 or P == 5:
        tot = 0
        for i, c in enumerate(S):
            c = int(c)
            if c % P == 0:
                tot += i+1
        print(tot)
        return

    S = list(S)
    U = [0]*N
    a = 0
    for i in range(N-1, -1, -1):
        a = (a * 10 + int(S[i])) % P
        U[i] = a
    U.append(0)
    table = [0]*P
    tot = 0
    for i in range(N-1, -1, -1):
        tot += table[U[i]]
        table[U[i]] += 1
    tot += table[0]
    print(tot)

    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 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] = 1
ans = 0
for y in a:
    x = (x * 10 + y) % p
    ans += mem[x]
    mem[x] += 1
    # print(mem)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

if P == 2 or P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i + 1
    print(ans)
    sys.exit()

num = [0] * P
num[0] = 1
now, ans = 0, 0
for i in range(N-1, -1, -1):
    now = (now * 10 + int(S[i])) % P
    ans += num[now]
    num[now] += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

if P == 2 or P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i + 1
    print(ans)
    sys.exit()

num = [0] * P
now, ans = 0, 0
for i in range(N-1, -1, -1):
    now = (now * 10 + int(S[i])) % P
    ans += num[now]
    if now == 0:
        ans += 1
    num[now] += 1
print(ans)

Submission status: Wrong Answer

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




digit_rm = [0 for _ in range(n)]
for i in range(n):
	digit_rm[i] = (int(s[n-1-i]) * pow(10, i, p) ) % p

remain = [0 for _ in range(n)]
for i in range(n):
	if i == 0:
		remain[i] = digit_rm[i]
	else:
		remain[i] = (remain[i-1] + digit_rm[i]) % p

pcnt = [0 for _ in range(p)]

for i in remain:
	pcnt[i] += 1

if 10 % p == 0:
	ans = 0
	for i in range(n):
		if int(s[n-1-i]) % p == 0:
			ans += i + 1 
	print(ans)
else:
	ans = pcnt[0]
	for num in pcnt:
		if num != 0:
			ans += num * (num - 1) // 2

	print(ans)

Submission status: Wrong Answer

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

digit_rm = [0 for _ in range(n)]
for i in range(n):
	digit_rm[i] = (int(s[n-1-i]) * pow(10, i, p) ) % p

remain = [0 for _ in range(n)]
for i in range(n):
	if i == 0:
		remain[i] = digit_rm[i]
	else:
		remain[i] = (remain[i-1] + digit_rm[i]) % p

pcnt = [0 for _ in range(p)]

for i in remain:
	pcnt[i] += 1

ans = pcnt[0]
for num in pcnt:
	if num != 0:
		ans += num * (num - 1) // 2

print(ans)

Submission status: Wrong Answer

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

digit_rm = [0 for _ in range(n)]
for i in range(n):
	digit_rm[i] = (int(s[n-1-i]) * pow(10, i, p) ) % p

remain = [0 for _ in range(n)]
for i in range(n):
	if i == 0:
		remain[i] = digit_rm[i]
	else:
		remain[i] = (remain[i-1] + digit_rm[i]) % p


ans = remain.count(0)
numcnt = [i for i in range(i)]
for i in range(10):
	num = remain.count(i)
	if num != 0:
		ans += num * (num-1) // 2

print(ans)

Submission status: Wrong Answer

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

digit_rm = [0 for _ in range(n)]
for i in range(n):
	digit_rm[i] = (int(s[n-1-i]) * pow(10, i, p) ) % p

remain = [0 for _ in range(n)]
for i in range(n):
	remain[i] = sum(digit_rm[0:i+1]) % p

ans = remain.count(0)
numcnt = [i for i in range(i)]
for i in range(10):
	num = remain.count(i)
	ans += num * (num-1) // 2

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
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:
    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: Wrong Answer

Solution code:
from collections import Counter

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

sum = 0
if P == 2 or P == 5:
    for i in range(N):
        if int(S[i]) % P == 0:
            sum += i+1
    print(sum)
    # exit()

m = []
for i in range(N):
    m.append(int(S[i:]) % P)
    
mc = Counter(m)

for n, v in mc.items():
    if v > 1:
        sum += v*(v-1)/2

sum += mc[0]

print(int(sum))

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

m = []
for i in range(N):
    m.append(int(S[i:]) % P)
    
mc = Counter(m)

sum = 0
for n, v in mc.items():
    if v > 1:
        sum += v*(v-1)/2

sum += mc[0]

print(int(sum))

Submission status: Wrong Answer

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

Solution code:
from sys import stdin
from collections import deque

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)),N+1):
        for j in range(N-i+1):
            cand_arr.append(int(S[j:j+i]))
    print(cand_arr)
    cnt = 0
    for cand in cand_arr:
        if cand % P == 0:
            cnt += 1
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import numpy as np
N,P = list(map(int, input().split()))
S = '0'+input()

#N=200000
#P=9893
#S= '0'+'1234567890' * 20000

if (P==2)|(P==5):
    sum=0
    for i in range(N, 0, -1):
        if int(S[i]) % P == 0:
            sum+= i
    print(sum)


else:
    dp1 = np.zeros(N + 1)
    dp2 = np.zeros(N + 1)
    dp3 = np.zeros(P)
    dp1[N] = int(S[N]) % P
    dp3[int(dp1[N])] += 1
    k = 1
    for i in range(N - 1, 0, -1):
        dp1[i] = (dp1[i + 1] + (int(S[i]) * 10 * k)) % P
        dp3[int(dp1[i])] += 1
        k = (k * 10) % P

    sum = 0

    for i in range(P):
        if i == 0:
            sum += (dp3[i] * (dp3[i] - 1)) // 2 + dp3[i]
            continue
        if dp3[i] == 0: continue
        sum += (dp3[i] * (dp3[i] - 1)) // 2
    print(dp1)
    print(dp3)
    print(int(sum))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import numpy as np
N,P = list(map(int, input().split()))
S = '0'+input()

#N=200000
#P=9893
#S= '0'+'1234567890' * 20000

dp1 = np.zeros(N+1)
dp2 = np.zeros(N+1)
dp3 = np.zeros(P)
dp1[N] = int(S[N]) % P
dp3[int(dp1[N])] += 1
k = 1
for i in range(N-1, 0, -1):
    dp1[i] = (dp1[i+1] + (int(S[i]) * 10 * k)) % P
    dp3[int(dp1[i])] += 1
    k = (k * 10) % P

sum = 0

for i in range(P):
    if i == 0:
        sum += (dp3[i] * (dp3[i] - 1)) // 2 + dp3[i]
        continue
    if dp3[i] == 0:continue
    sum += (dp3[i] * (dp3[i] - 1)) // 2

print(int(sum))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import numpy as np
N,P = list(map(int, input().split()))
S = '0'+input()

#N=200000
#P=9893
#S= '0'+'1234567890' * 20000

dp1 = np.zeros(N+1)
dp2 = np.zeros(N+1)
dp3 = np.zeros(P)
dp1[N] = int(S[N]) % P
dp3[int(dp1[N])] += 1
k = 1
for i in range(N-1, 0, -1):
    dp1[i] = (dp1[i+1] + (int(S[i]) * 10 * k)) % P
    dp3[int(dp1[i])] += 1
    k = (k * 10) % P

sum = 0

for i in range(P):
    if i == 0:
        sum += (dp3[i] * (dp3[i] - 1)) // 2 + dp3[i]
        continue
    if dp3[i] == 0:continue
    sum += (dp3[i] * dp3[i] - 1) // 2

print(int(sum))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import numpy as np
N,P = list(map(int, input().split()))
S = '0'+input()

dp1 = np.zeros(N+1)
dp2 = np.zeros(N+1)
dp3 = np.zeros(P)
zero_count = 0
dp1[N] = int(S[N]) % P
dp3[int(dp1[N])] += 1
k = 1
for i in range(N-1, 0, -1):
    dp1[i] = (dp1[i+1] + ((int(S[i]) * 10 * k) % P)) % P
    dp3[int(dp1[i])] += 1
    k = (k * 10) % P
    if int(S[i]) % P == 0:
        zero_count += 1

sum = 0
for i in range(P):
    if i == 0:
        sum += (dp3[i] * dp3[i] - 1) // 2 + dp3[i]
        continue
    sum += (dp3[i] * dp3[i] - 1) // 2

print(int(sum)-zero_count)