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:
n,p=map(int,input().split())
l=list(input())
for i in range(n):
    l[i]=int(l[i])
w=0
wl=[]
po=pow(10,p-2,p)
if p==2 or p==5:
    ans=0
    for i in range(n):
        if l[i]%p==0:
            ans+=i+1
    print(ans)
    exit()
for i in range(n):
    wl.append(w)
    #if w==0:
        #ans+=rr[n-1-i]
    w-=l[n-1-i]
    w*=po
    w%=p
wl.reverse()
r=[]
rt=0
for i in range(n):
    rt+=l[n-1-i]*pow(10,i,p)
    r.append(rt%p)
    #rt*=10
    rt%=p
r.reverse()
d=[0]*p
ans=0
for i in range(n):
    d[r[i]]+=1
    ans+=d[wl[i]]  
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n,p= map(int,input().split())
s = input()
cum_sum = [0]*(1+n)
#ここでソートするとO(NlogN)でTLE?　pow i*p が両方maxでlog(i*p)がだめ？

# cnt[k]でkの時のあまりを作っておく
cnt_modk = [0]*p
cnt_modk[0] += 1
for i in range(n):
    cum_sum[i+1] = (cum_sum[i]*10+int(s[i]))%p
for i in range(1,n+1):
    cum_sum[i] = cum_sum[i]*pow(10,i*p-2)%p
    cnt_modk[cum_sum[i]] += 1
#cum_sum.sort()
#print(cum_sum)
ans = 0
if p == 2 or p == 5:#右端を固定すれば2,5で割り切れるならそれ以降は全部いけるのでn-iをたす
    for i in range(n):
        if int(s[-1-i]) % p == 0:
            ans += n-i
    print(ans)
    exit()
for i in range(p):
    ans += cnt_modk[i]*(cnt_modk[i]-1)//2
"""cnt = 1
for i in range(n):
    if cum_sum[i] != cum_sum[i+1]:
        ans += cnt*(cnt-1)//2
        cnt = 1
    else: cnt += 1
ans += cnt*(cnt-1)//2"""
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N, P = map(int, input().split())
    S = [int(c) for c in input()]

    ret = 0
    curr_num = 0
    counter = [0] * P
    counter[0] = 1

    for x in reversed(S):
        curr_num = (curr_num * 10 + x) % P
        ret += counter[curr_num]
        counter[curr_num] += 1

    print(ret)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Wrong Answer

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

if p == 2:
  for i in range(n):
    if s[i] in [0,2,4,6,8] :
      ans += i + 1
elif p == 5:
  for i in range(n):
    if s[i] in [0,5]:
      ans += i + 1
else:
  sp = [0]*n
  sp[n-1] = s[n-1]%p
  cnt[sp[n-1]] += 1
  for i in range(1,n):
    sp[n-i-1] = (sp[n-i]+s[n-i-1]*(10**i%p))%p
    cnt[sp[n-i-1]] += 1
  for j in range(p):
    cj = cnt[j]
    ans += cj * (cj-1)//2
print(cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, P = lr()
S = sr()
# 累積和
remain = [0] * N
cur = 0
answer = 0
for i in range(N):
    prev = cur
    num = 10 * cur + int(S[i])
    cur = num % P
    remain[i] = cur
    if int(S[i]) % P == 0 and prev != cur:
        answer += 1

counter = Counter(remain)
if P == 2 or P == 5:
    ind = (i for i, x in enumerate(S, 1) if int(x) % P == 0)
    answer = sum(ind)
else:
    for k, v in counter.items():
        if k == 0:
            answer += v * (v+1) // 2
        else:
            answer += v * (v-1) // 2

print(answer)

Submission status: Wrong Answer

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

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

for i in range(n-1, -1, -1):
    m = int(s[i:]) % p
    ans += mod[m]
    mod[m] += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n,p=map(int,input().split())
s=input()
x=[0 for i in range(p)]
ans=0
if p==2:

    for i in range(n):
        if int(s[i])%2==0: ans+=i+1
    print(ans)

elif p==5:
    for i in range(n):
        if int(s[i])%5==0: ans+=i+1
    print(ans)

else:
    tmp1=1
    tmp2=0
    for i in range(n):
        tmp2=(tmp1*int(s[i])+tmp2)%p
        x[tmp2]+=1
        tmp1=(tmp1*10)%p
    ans+=x[0]
    for i in range(p):
        ans+=x[i]*(x[i]-1)//2
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n,p=map(int,input().split())
s=input()
x=[0 for i in range(p)]
ans=0
if n==2:

    for i in range(n):
        if int(s[i])%2==0: ans+=i+1
    print(ans)

elif n==5:
    for i in range(n):
        if int(s[i])%5==0: ans+=i+1
    print(ans)

else:
    tmp1=1
    tmp2=0
    for i in range(n):
        tmp2=(tmp1*int(s[i])+tmp2)%p
        x[tmp2]+=1
        tmp1=(tmp1*10)%p
    ans+=x[0]
    for i in range(p):
        ans+=x[i]*(x[i]-1)//2
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd

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

if P in [2,5]:
    count=0
    for i in range(N):
        if int(S[i])%P==0:
            count+=i+1
    print(count)
    exit()
S=list(S)
nlst=[0,int(S[0])%P]
for i in range(1,N):
    nlst.append((nlst[i]*pow(10,N-i,P)+int(S[i]))%P)

count=0
for i,n in Counter(nlst).most_common():
    count+=n*(n-1)//2

print(count)

Submission status: Wrong Answer

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd

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

if P in [2,5]:
    count=0
    for i in range(N):
        if int(S[i])%P==0:
            count+=i+1
    print(count)
    exit()
S=list(S)
nlst=[0,int(S[0])%P]
for i in range(1,N):
    nlst.append((nlst[i]*pow(10,i,P)+int(S[i]))%P)

count=0
for i,n in Counter(nlst).most_common():
    count+=n*(n-1)//2

print(count)

Submission status: Wrong Answer

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

t = []

for i in range(n):
  t.append(s[i:])

t = [int(i)%p for i in t]

c = t.count(0)
for i in range(n):
  c += [t[i]==x for x in t[i+1:]].count(True)

print(c)

Submission status: Wrong Answer

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, P = lr()
    S = list(map(int, list(sr())))[::-1]
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if int(S[i])%P == 0:
                ans += i+1
        print(ans)
        return
    lp = [0]*P
    c = 0
    for i in range(N):
        d = S[i]*10**i
        c = (c+d)%P
        lp[c] += 1
    ans = lp[0]
    for i in range(P):
        ans += max(lp[i]*(lp[i]-1)//2, 0)
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
num = input().strip()
ans = 0
if P == 2:
    for idx, nu in enumerate(num):
        if nu in '24680':
            ans += idx + 1
elif P == 5:
    for idx, nu in enumerate(num):
        if nu in '50':
            ans += idx + 1
else:
    nnum = [0] * N
    base = 1
    for i in range(N-1, -1, -1):
        nnum[i] = (int(num[i]) * base) % P
        base = (base * 10) % P
    for i in range(1, N):
        nnum[i] = (nnum[i] + nnum[i-1]) % P
    dp = [0] * P
    for i in range(N):
        if nnum[i] == 0:
            ans += 1 + dp[nnum[i]]
        else:
            ans += dp[nnum[i]]
        dp[nnum[i]] += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, P = lr()
S = sr()
# 累積和
remain = [0] * N
cur = 0
answer = 0
for i in range(N):
    prev = cur
    num = 10 * cur + int(S[i])
    cur = num % P
    remain[i] = cur
    if int(S[i]) % P == 0 and prev != cur:
        answer += 1

counter = Counter(remain)
if P == 2 or P == 5:
    answer = counter[0] * (counter[0] + 1) // 2
else:
    for k, v in counter.items():
        if k == 0:
            answer += v * (v+1) // 2
        else:
            answer += v * (v-1) // 2

print(answer)

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=list(input())
import collections
if p!=2 and p!=5:
    modlist=[0 for _ in range(n+1)]
    modlist[0]=0
    modlist[1]=int(s[0])%p  
    for i in range(2,n+1):
        modlist[i]=(10*modlist[i-1]+int(s[i-1]))%p
    ANS=dict(collections.Counter(modlist))
    ans=0
    for some in ANS.values():
        ans+=(some*(some-1)//2)
    print(ans)
else:
    print(1)

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
S=input()
l=0
r=0
num=0
amari=[0 for _ in range(P)]
amari[0]=1
cnt=0
if (P!=2)or(P!=5):
    for i in range(N-1,-1,-1):
        #print(S[i],pow(10,N-i-1))
        num=num+int(S[i])*pow(10,N-1-i,P)
        #print(num)
        index=num%P
        amari[index]=amari[index]+1
    #print(amari)
    cnt=0
    for i in range(P):
        cnt=cnt+(max(0,amari[i])*max(0,amari[i]-1))/2
else:
    for i in range(N-1,-1,-1):
        if int(S[i])%P==0:
            cnt=cnt+i
print(int(cnt))

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n,p=MI()
    s=SI()
    if p==2 or p==5:
        ans=0
        for i,c in enumerate(s):
            if int(c)%p==0:ans+=i+1
        print(ans)
        exit()
    aa=[int(c) for c in s[::-1]]
    cc=[0]
    ten=1
    for a in aa:
        cc.append((cc[-1]+a*ten)%p)
        ten=ten*10%p
    cnt=Counter(cc)
    print(cc)
    print(cnt)
    ans=0
    for v in cnt.values():
        ans+=v*(v-1)//2
        print(v,ans)
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=list(input())
import collections
if p!=2 and p!=5:
    modlist=[0 for i in range(n+1)]
    modlist[0]=0
    modlist[1]=int(s[0])%p  
    for i in range(2,n+1):
        modlist[i]=(10*modlist[i-1]+int(s[i-1]))%p
    ANS=dict(collections.Counter(modlist))
    ans=0
    for some in ANS.values():
        ans+=(some*(some-1)//2)
    print(ans)
else:
    ans=0
    q=0
    for i in range(n):
        if int(s[i])%p==0:
            q+=1
        ans+=q
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n,p=map(int,input().split())
s=input()
x=[0 for i in range(p)]
ans=0
if n==2:

    for i in range(n):
        if int(s[i])%2==0: ans+=i+1
    print(ans)

elif n==5:
    for i in range(n):
        if int(s[i])%5==0: ans+=i+1
    print(ans)

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

Submission status: Wrong Answer

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

r_circ = []
v = 1
while True:
    r = v % P
    if r in r_circ:
        break
    r_circ.append(r)
    v *= 10

ans = 0
pr = 0
for l in reversed(range(len(S))):
    pr = 0
    for f in reversed(range(l+1)):
        d = int(S[f])
        r = d * r_circ[(l-f) % len(r_circ)] + pr
        r %= P
        if r == 0:
            ans += 1
        pr = r
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

n,p=list(map(int,input().split()))
s=[int(x) for x in sys.stdin.readline().strip()]
reslst=[0]*p

cnt=0

if p==2:
    for i in range(n):
        if s[i]%2==0:
            cnt+=i+1
elif p==5:
    for i in range(n):
        if s[i]==5 or s[i]==0:
            cnt+=i+1
else:
    x=0
    for i in range(n-1,-1,-1):
        x=s[i]*(10**i)+x
        reslst[x%p]+=1
    reslst[0]+=1

    for i in range(p):
        j=reslst[i]

        cnt+=j*(j-1)//2

print(cnt)

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
S=input()
l=0
r=0
num=0
amari=[0 for _ in range(P)]
amari[0]=1
cnt=0
for i in range(N-1,-1,-1):
    #print(S[i],pow(10,N-i-1))
    num=num+int(S[i])*pow(10,N-1-i,P)
    #print(num)
    index=num%P
    amari[index]=amari[index]+1
#print(amari)
cnt=0
for i in range(P):
    cnt=cnt+(max(0,amari[i])*max(0,amari[i]-1))/2
print(int(cnt))

Submission status: Wrong Answer

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

mod = p
l = 100

M = [1]  # i!のmod
m = 1
for i in range(1, l):
    m = (m * i) % mod
    M.append(m)

def pow(x, y, mod):  # x**y の mod を返す関数
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = (ans * x) % mod
        x = (x**2) % mod
        y //= 2
    return ans

def inv(x, mod):  # x の mod での逆元を返す関数
    return pow(x, mod-2, mod)

T = [1]
for i in range(n-1):
    T.append((T[-1]*10) % p)

P = [0] * p
P[0] = 1

ans = 0
v = 0
S = [int(s[i]) for i in range(n-1,-1,-1)]

for i in range(n):
    v = (v + T[i]*S[i]) % p
    ans += P[v]
    P[v] += 1
    # print(P)

print(ans)

Submission status: Wrong Answer

Solution code:
#
import sys
import math
#import numpy as np
import itertools
from collections import Counter
# いくつか入力
n,p = (int(i) for i in input().split())
# 空白区切りの数列をリストに代入
s = [int(i) for i in list(input())] 

answer = 0
#print(s)
q=0
x=[]
if p == 2 or p == 5:
    for i in range(n-1,-1,-1):
        if s[i]%p == 0:
            answer += i+1
else:
    for i in range(n-1,-1,-1):
        q=(q+s[i])%p
        x.append(q)
        q = (q * 10)%p
    #print(x)
    counter = Counter(x)
    #print(counter)

    for k in counter:
    #    print(k)
        if k==0:
            answer += counter[k] * (counter[k]+1) // 2
        else:
            answer += counter[k] * (counter[k]-1) // 2

print(answer)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def answer():
    n, p = map(int, input().split())
    s = input()
    m = defaultdict(int)
    ans = 0
    if p == 2 or p == 5:
        for i, ss in enumerate(s):
            if int(ss) % p == 0:
                ans += i + 1
        return ans
    sss = 0
    for ss in s[::-1]:
        sss = sss*10 + int(ss)
        m[sss % p] += 1
    m[0] += 1
    for i in range(p):
        if m[i] >= 2:
            ans += m[i] * (m[i] - 1) // 2
    return ans

print(answer())

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
def main():
    N,P=map(int, input().split())
    S=input()
    B=[(ord(c)-ord("0"))%P for c in S]
    ans=0
    if P==2 or P==5:
        for i,b in enumerate(B,1):
            if b==0:
                ans+=i
    else:
        C=list(accumulate(B[::-1], lambda acc,x: (acc*10+x)%P))
        D={0:1}
        for c in C:
            D.setdefault(c,0)
            ans+=D[c]
            D[c]+=1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def answer():
    n, p = map(int, input().split())
    s = input()
    m = defaultdict(int)
    ans = 0
    if p == 2 or p == 5:
        for i, ss in enumerate(s):
            if int(ss) % p == 0:
                ans += i + 1
        return ans
    sss = 0
    for ss in s[::-1]:
        sss = (sss*10 + int(ss)) % p
        m[sss] += 1
    m[0] += 1
    for i in range(p):
        if m[i] >= 2:
            ans += m[i] * (m[i] - 1) // 2
    return ans

print(answer())

Submission status: Wrong Answer

Solution code:
import collections

def slowsolve(N, P, S):
    ans = 0
    for i in range(N):
        for j in range(i, N):
            if int(S[i:j+1]) % P == 0:
                print(S[i:j+1])
                ans += 1
    return ans
def solve(N, P, S):
    mods = {}
    divs = []
    k = 0
    ans = 0

    for i, c in enumerate(S):
        k = (k * 10 + int(c)) % P
        divs.append(k)

        if k != 0 and (P - k) in mods:
            ans += mods[P - k]

        newmods = {}
        newmods.setdefault(k, 0)
        newmods[k] += 1
        for m in mods:
            d = (m * 10) % P
            newmods.setdefault(d, 0)
            newmods[d] += 1
        mods = newmods

    counts = collections.Counter(divs)
    if 0 in counts:
        ans += counts[0]
        ans += (counts[0] * (counts[0] - 1)) // 2
    return ans

# print(slowsolve(5, 11, "33883"))
# print(solve(5, 11, "33883"))

if __name__ == "__main__":
    N, P = tuple(map(int, input().split(" ")))
    S = input()
    print(solve(N, P, S))

Submission status: Wrong Answer

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


print(ans)
#print(dp)

Submission status: Wrong Answer

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd

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

if P in [2,5]:
    count=0
    for i in range(N):
        if int(S[i])%P==0:
            count+=i+1
    print(count)
    exit()
S=list(S)
S.reverse()
nlst=[0,int(S[0])%P]
for i in range(1,N):
    nlst.append((nlst[i]*pow(10,i,P)+int(S[i]))%P)

count=0
for i,n in Counter(nlst).most_common():
    count+=n*(n-1)//2

print(count)

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = list(input())
S = [(int(value)*pow(10, N-1-idx, P))%P for idx, value in enumerate(S)]
count_multiples = 0
for i in range(N):
  accumulated_value = S[i]
  count_multiples += int(accumulated_value == 0)
  for j in range(i+1, N):
    accumulated_value = (accumulated_value+S[j])%P
    count_multiples += int(accumulated_value == 0)
print(count_multiples)

Submission status: Wrong Answer

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd

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

if P in [2,5]:
    count=0
    for i in range(N):
        if int(S[i])%P==0:
            count+=i+1
    print(count)
    exit()
S=list(S)
S.reverse()
nlst=[0,int(S[0])%P]
for i in range(1,N):
    nlst.append((nlst[i]*pow(10,P-2,P)+int(S[i]))%P)

count=0
for i,n in Counter(nlst).most_common():
    count+=n*(n-1)//2

print(count)

Submission status: Wrong Answer

Solution code:
#X=a_(N)a_(N-1)…a_1
#ここでn(i,j)=a_i…a_jとすると
#n(i,j)=n(i,1)-n(j-1,1)/10^(j-1))…(※)である
#(n(0,1)=0とする(とn(i,j)と辻褄が合いそう))
#10=2*5、Pは素数なので
#(i)P=2,5の時
#そもそも右端が2,5の倍数なら良い
#(ii)not(P=2,5)の時、(※)の分母はPと素なので、
#(n(i,0)-n(j+1,0) mod P)==0<=>n(i,0)==n(j+1,0) (mod P)である必要がある必要がある
#なので、n(k,0)(1<=k<=N)をリストかなんかに保存して、(l[i]-1)C2をP回足して終わり！

N,P=map(int,input().split())
S=input()
l=0
r=0
num=0
amari=[0 for _ in range(P)]
amari[0]=1
cnt=0
for i in range(N-1,-1,-1):
    #print(S[i],pow(10,N-i-1))
    num=num+int(S[i])*pow(10,N-1-i)
    #print(num)
    index=num%P
    cnt=cnt+amari[index]
    amari[index]=amari[index]+1
print(cnt)

Submission status: Wrong Answer

Solution code:
import collections

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
    print(ans)
else:
    S, a, temp = S[::-1], [int(S[0]) % P], 1
    for i in range(1, N):
        temp *= 10
        temp %= P
        a.append((a[i-1] + (int(S[i]) % P * temp) % P) % P)

    c = collections.Counter(a)
    if 0 in c:
        ans += c[0]
        ans += c[0] * (c[0] - 1) // 2
        del c[0]
    for x in c.keys():
        ans += c[x] * (c[x]-1) // 2 
    print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
def main():
    N,P=map(int, input().split())
    S=input()
    B=[(ord(c)-ord("0"))%P for c in S]
    ans=0
    if P==2 or P==5:
        acc=0
        for i,b in enumerate(B,1):
            if b==0:
                acc+=1
                ans+=acc
    else:
        C=list(accumulate(B[::-1], lambda acc,x: (acc*10+x)%P))
        D={0:1}
        for c in C:
            if c in D:
                ans+=D[c]
                D[c]+=1
            else:
                D[c]=1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, p = LI()
D = defaultdict(int)
D[0] += 1
s = S()
ans = 0
rem = 0
if p == 2 or 5:
    for i in range(n - 1, -1, -1):
        if int(s[i]) % p == 0:
            ans += i + 1
    print(ans)
    exit()

k = 1
for i in range(n - 1, -1, -1):
    d = int(s[i])
    rem = (k * d + rem) % p
    k = k * 10 % p
    ans += D[rem]
    D[rem] += 1


print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n,p= map(int,input().split())
s = input()
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[-1-i]) % p == 0:
            ans += n-i
    print(ans)
    exit()
cum_sum = [0]*(1+n)
for i in range(n):
    cum_sum[i+1] = (cum_sum[i]*10+int(s[i]))%p
for i in range(1,n+1):
    cum_sum[i] = cum_sum[i]*pow(10,i*p-2)%p
cum_sum.sort()
#print(cum_sum)
cnt = 1
for i in range(n):
    if cum_sum[i] != cum_sum[i+1]:
        ans += cnt*(cnt-1)//2
        cnt = 1
    else: cnt += 1
ans += cnt*(cnt-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
####

import numpy as np
from numpy import newaxis, float32, float64, int32, int64, int16, int8, uint8, uint32, complex64, complex128

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def main(inputs):
	n,p=getIntList(inputs[0])
	s=inputs[1][0]
	
	ans=0
	if p%2==0 or p%5==0:
		for i0 in range(len(s)-1,-1,-1):
			sub=int(s[i0:i0+1])
			if sub%p==0:
				ans+=i0+1
	else:
		numP0=np.zeros(p, int32)
		numP0[0]=1
		r=0
		for i0 in range(len(s)-1,-1,-1):
			sub=s[i0:i0+1]
			sub=int(sub)
			sub=r*10+sub
			sub%=p
			ans+=numP0[sub]
			numP0[sub]+=1
			r=sub
# 			print(s[i0:], sub, numP0, ans)
	print(ans)
		

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Submission status: Wrong Answer

Solution code:
import math
from collections import deque
def main():
    n,p = tuple([int(t)for t in input().split()])
 
    s = input()[::-1]
    subs = [0]*p
    counter =0

    if p==2 or p==5:
        for i in range(n):
            counter += n-i if int(s[0:i+1])%p==0 else 0
        
        print(counter)
        return

    for i in range(n):
        subs[int(s[0:i+1])%p] +=1

    counter+=subs[0]
 
    for i in range(p):
        counter+= subs[i]*(subs[i]-1)//2
 
    print(counter)
 
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
def main():
    N,P=map(int, input().split())
    S=input()
    B=[(ord(c)-ord("0"))%P for c in S]
    ans=0
    if P==2 or P==5:
        for i,b in enumerate(B,1):
            if b==0:
                ans+=i
    else:
        C=list(accumulate(B[::-1], lambda acc,x: (acc*10+x)%P))
        D={0:1}
        for c in C:
            if c in D:
                ans+=D[c]
                D[c]+=1
            else:
                D[c]=1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
S=input()
ans=0
if p==5:
    for i in range(n):
        if int(S[i])==5 or int(S[i])==0:
            ans+=i+1
elif p==2:
    for i in range(n):
        if int(S[i])%2==0:
            ans+=i+1
else:
    kouho=[0]*p
    s=0
    for i in range(n):
        s+=int(S[-i])*(10**i)
        a=s%p
        kouho[a]+=1
    for j in range(p):
        z=kouho[j]
        ans+=z*(z-1)//2
    ans+=kouho[0]
print(ans)

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=input()
dp=[[0 for i in range(p)] for j in range(n)]
x=int(s[0])
dp[0][x%p]=1
for j in range(1,n):
  x=int(s[j])
  dp[j][x%p]+=1
  for i in range(p):
    y=(i*10+x)%p
    dp[j][y]+=dp[j-1][i]

ans=0
for j in range(n):
  ans+=dp[j][0]




print(ans)
print(dp)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n,p= map(int,input().split())
s = input()
cum_sum = [0]*(1+n)
for i in range(n):
    cum_sum[i+1] = (cum_sum[i]*10+int(s[i]))%p
for i in range(n):
    cum_sum[i] = cum_sum[i]*pow(10,p-2)%p
cum_sum.sort()
#print(cum_sum)
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[-1-i]) % p == 0:
            ans += n-i
    print(ans)
    exit()
cnt = 1
for i in range(n):
    if cum_sum[i] != cum_sum[i+1]:
        ans += cnt*(cnt-1)//2
        cnt = 1
    else: cnt += 1
ans += cnt*(cnt-1)//2
print(ans)

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

hist1 = []


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]
        hist1.append(s)
    print()
    print(ans)
    print()


# test()
#
# for r in reversed(range(N)):
#     mod_counts = [0] * P
#     for l in range(r + 1):
#         mod_counts[int(S[l: r + 1]) % P] += 1
#     print(mod_counts)

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
p = 1
for i in reversed(range(N)):
    ans += mod_counts[offset]
    mod_counts[(int(S[i]) * p + offset) % P] -= 1
    offset *= 10
    offset += int(S[i])
    offset %= P
    p *= 10
    p %= P

print(ans)

Submission status: Wrong Answer

Solution code:
##mod M における　aの逆元を求めてくれる
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
#すなわちax==1(mod m)なる自然数xを返してくれる関数 動作時間:logM
def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

n,p=map(int,input().split())
s=list(input())
import collections
if p!=2 and p!=5:
    modlist=[0 for i in range(n+1)]
    modlist[0]=0
    modlist[1]=int(s[0])%p  
    for i in range(2,n+1):
        modlist[i]=(10*modlist[i-1]+int(s[i-1]))%p
    ANS=dict(collections.Counter(modlist))
    ans=0
    for some in ANS.values():
        ans+=(some*(some-1)//2)
    print(ans)
elif p==2:
    ans=0
    q=0
    for i in range(n):
        if int(s[i])%2==0:
            q+=1
        ans+=q
    print(ans)
elif p==5:
    ans=0
    q=0
    for i in range(n):
        if int(s[i])%5==0:
            q+=1
        ans+=q
    print(ans)

Submission status: Wrong Answer

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

answer=0
if P==2 or P==5:
  for i in range(N):
    si=int(S[i])
    if si%P==0:
      answer+=i+1
else:
  mod_table=[0]*P
  revS=S[::-1]
  
  modp=0
  for i in range(N):
    modp=(10*modp+int(revS[i]))%P
    mod_table[modp]+=1
    
  #print(mod_table)
  answer=mod_table[0]*(mod_table[0]+1)//2
  for i in range(1,P):
    answer+=mod_table[i]*(mod_table[i]-1)//2
  
print(answer)

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = input()
ss = len(s)
i = 0
t = 0
while i < ss:
  j = 0
  while i+j < ss:
    if int(s[i:i+j+1]) % p == 0:
      t += 1
      i = i+j+1
      break
    j += 1
print(t*(t+1)//2)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n,p=MI()
    s=SI()
    if p==2 or p==5:
        ans=0
        for i,c in enumerate(s):
            if int(c)%2==0:ans+=i+1
        print(ans)
        exit()
    aa=[int(c) for c in s[::-1]]
    cc=[0]
    ten=1
    for a in aa:
        cc.append((cc[-1]+a*ten)%p)
        ten=ten*10%p
    cnt=Counter(cc)
    ans=0
    for v in cnt.values():
        ans+=v*(v-1)//2
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,p = inpl()
s = input()[::-1]
res = 0
if p == 2 or p == 5:
    for i,t in enumerate(s):
        if int(t)%p == 0: res += i+1
    print(res)
    quit()
now = ''
d = defaultdict(int)
d[0] = 1
for i,t in enumerate(s):
    now = t + now
    d[int(now)%p] += 1
for key in list(d):
    v = d[key]
    res += v*(v-1)//2
print(res)