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(' '))
s = input()

cnt = 0
m = 0
j = {0:1}
for i in range(n):
    ss = s[n - i - 1:] 
    m = int(ss) % p
    if m not in j:
        j[m] = 1
    else:
        j[m] += 1
ret = 0
for v in j.values():
    if v != 1:
        ret += v * (v - 1) // 2
print(ret)

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
	numP0=np.zeros(p, int32)
	numP0[0]=1
	for i0 in range(len(s)-1,-1,-1):
		sub=s[i0:]
		sub=int(sub)
		sub%=p
		ans+=numP0[sub]
		numP0[sub]+=1
# 		print(s[i0:], sub, numP0, ans)
	print(ans)
		

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

Submission status: Wrong Answer

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

pre = 0
ans = 0

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

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

Submission status: Wrong Answer

Solution code:
def main():
    n, p = map(int, input().split())
    s = list(map(int, list(input())))
    now = 1
    now2 = 0

    dp = [0]*p
    cnt = 0
    if p != 5:
        for i in s:
            now2 = (now2*10+i) % p
            dp[((i-now2) % p)*pow(now, p-2, p) % p] += 1
            cnt += dp[((-now2) % p)*pow(now, p-2, p) % p]
            now = (now*10) % p
            print(dp)
    else:
        for j, i in enumerate(s):
            if i in [0, 5]:
                cnt += j+1
    print(cnt)


main()

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=1
    for s in S:
        if int(s)%P==0:
            count+=1
    count=count*(count-1)//2
    print(count)
    exit()

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:
n, p = map(int, input().rstrip().split())
s = input().rstrip()

if p == 2 or p == 5:
    ans = 0
    for i, c in enumerate(s):
        if int(c) % p == 0:
            ans += i + 1
    print(ans)
else:
    si = int(s)
    p_a = si % p
    cnt = [0] * p
    k = 0
    cnt[k] = 1
    for i, c in enumerate(map(int, s)):
        k = k * 10 + c
        k %= p
        cnt[k] += 1

    ans = 0
    for i in range(p):
        ans += cnt[i] * (cnt[i] - 1) // 2
    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)
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:
import sys
input=sys.stdin.readline
n,p=map(int,input().split())
s=input().rstrip()
if p==2:
    for i in range(n):
        ans=0
        if int(s[i])%2==0:
            ans+=i+1
elif p==5:
    for i in range(n):
        ans=0
        if int(s[i])==0 or int(s[i])==5:
            ans+=i+1
else:
    count=[0]*p
    x=0
    y=1
    count[0]=1
    for i in range(n-1,-1,-1):
        x=x+y*int(s[i])
        x=x%p
        count[x]+=1
        y=(y*10)%p
    ans=0
    for i in count:
        ans+=i*(i-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:

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

def main():
    N,P=MI()
    s=input()
    ans=0
    t=0
    mod=[0]*P
    mod[0]=1
    for i in range(N):
        t=t*10+int(s[N-i-1])
        t=t%P
        mod[t]+=1
        if mod[t]>=2:
            ans+=mod[t]-1
            

    print(ans)   
        
    
            
    
        
    

main()

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

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:
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 = sr()
    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
    for i in range(N):
        lp[int(S[i:])%P] += 1
    MOD = 10*9+7
    SIZE = 10**6+1
    inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0]*SIZE  # fac[j] = j! mod MOD
    finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2,SIZE):
        inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
        fac[i] = fac[i-1]*i%MOD
        finv[i]= finv[i-1]*inv[i]%MOD
    
    def choose(n,r): # nCk mod MOD の計算
        if 0 <= r <= n:
            return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
        else:
            return 0
    ans = lp[0]
    for i in range(P):
        ans += choose(lp[i], 2)
    print(ans)
resolve()

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

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)


b=Counter(nlst)[0]
count=b*(b-1)//2

print(count)

Submission status: Wrong Answer

Solution code:
n,p = map(int,input().split())
s = list(map(int,(list(input()))))
def keychange(dic,x):
    newdic = {}
    for k in dic:
        b = (k*10 + x) % p
        newdic[b] = dic[k]
    return newdic
inv_t = [0]+[1]
for i in range(2,p):
  inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
dic = {}
count = 0
memory = [1,0]
for i in range(n):
    x = s[i] % p
    memory[0] = 10*memory[0] % p
    memory[1] = (10*memory[1] + x) % p
    xinv = inv_t[memory[0]]*(x-memory[1]+p) % p
    if xinv in dic:
        dic[xinv] += 1
    else:
        dic[xinv] = 1
    zeroinv = (p-memory[1])*inv_t[memory[0]] % p
    if zeroinv in dic:
        count += dic[zeroinv]
print(count)

Submission status: Wrong Answer

Solution code:
def main():
    N, P = map( int ,input().split())
    S = [ int(s) for s in list(input())][::-1]
    L = [0]*P
    L[0] = 1
    t = 0
    for i in range(N):
        t = (S[i]*pow(10,i,P)+t)%P
        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:
def main():
    n, p = map(int, input().split())
    s = list(map(int, list(input())))
    now = 1
    now2 = 0

    dp = [0]*p
    cnt = 0
    for i in s:
        now2 = (now2*10+i) % p
        dp[((i-now2) % p)*pow(now, p-2, p) % p] += 1
        cnt += dp[((-now2) % p)*pow(now, p-2, p) % p]
        now = (now*10) % p

    print(cnt)


main()

Submission status: Wrong Answer

Solution code:
NN = 2020202
MOD = 10**9+7
INF = float("inf")


n, p = map(int, input().split())
S = input()
pl = len(str(p))
d = [0]*p
d[0] = 1
val = 0

if p == 2 or p == 5:
    count = 1
    for i in range(len(S)):
        if int(S[i])%p == 0:
            count += 1
            # print(int(S[i]), count)

    print((count*(count-1))//2)

else:
    for i in range(len(S)-1, -1, -1):
        val = (10*val+int(S[i]))%p
        d[val] += 1

    # print(d)
    ans = 0
    for e in d:
        ans += (e*(e-1))//2
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

As = [0]
A = 0
D = 1
for S in Ss[::-1]:
    S = int(S)
    A = (A + S*D) % P
    As.append(A)
    D = D*10 % P
#print('As:', As)

cnt = Counter()
ans = 0
for A in As:
    ans += cnt[A]
    cnt[A] += 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 cur != 0 and prev != cur:
        answer += 1

counter = Counter(remain)
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:
import sys
input = sys.stdin.readline
from collections import Counter

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

if mod == 2 or mod == 5:
    ans = 0
    for i, s in enumerate(S):
        if int(s)%mod==0:
            ans += i+1
else:
    dp = [0]
    for s in S:
        dp.append((dp[-1]*10+int(s))%mod)

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

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N, P = map( int ,input().split())
    S = [ int(s) for s in list(input())][::-1]
    L = [0]*P
    L[0] = 1
    t = 0
    for s in S:
        t = (t*10+s)%P
        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:
n,p=map(int,input().split())
s=input()

genL=[set() for i in range(n+1)]
ans=0


def ser(l,gL):
    global kari

    for gR in genL[l+len(str(gL))]:
        new=str(gL)+str(gR)
        if new not in genL[l]:
            kari.add(new)
            ser(l,new)





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:
    pke=len(str(p))
    for i in range(pke+1):
        for l in range(n-i):
            num=s[l:l+i+1]
            if int(num)%p==0:

                genL[l].add(num)


    for i in range(n):
        kari=set()
        for l in genL[i]:
            ser(i,l)

        for k in kari:
            genL[i].add(k)

    for i in genL:
        ans+=len(i)

print(ans)

Submission status: Wrong Answer

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

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

nlst=[0,int(S[0])]
for i in range(1,N):
    nlst.append((nlst[i]*10+int(S[i])))

nlst=[i%P for i in nlst]

b=Counter(nlst)[0]
count=b*(b-1)//2

print(count)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
n, p = [int(i) for i in sys.stdin.readline().split()]
s = sys.stdin.readline().strip()
us = Counter([])
cur = ""
ans = 0
for i, _s in enumerate(s[::-1]):
    cur = _s + cur
    mod = int(cur) % p
    if mod == 0:
        ans += us[mod] + 1
    else:
        ans += us[mod]
    us.update([mod])
print(ans)

Submission status: Wrong Answer

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

ans=0
for i in range(n):
    
    if dp[i][0]!=-1:
        ans+=dp[i][0]
        if dp[i][1]!=n:
            if dp[dp[i][1]]!=-1:
                dp[dp[i][1]][0]+=dp[i][0]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n,p = l_in()
s = s_in()

from collections import Counter

c = Counter()

ms = []
m = 0

res = 0
if p == 2:
    for i, t in enumerate(s[::-1]):
        t = int(t)
        if t%2 == 0:
            res += n-i

    print(res)
    exit()

if p == 5:
    for i, t in enumerate(s[::-1]):
        t = int(t)
        if t == 0 or t == 5:
            res += n-i

    print(res)
    exit()


for i, t in enumerate(s[::-1]):
    t = int(t)
    if t == 0:
        t = p
    m += t*(10**i)
    print(m)
    ms.append(m)
    c[m%p] += 1

for m in ms:
    res += c[m%p]-1
print(res//2 + c[0])

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 = sr()
    lp = [0]*P
    for i in range(N):
        lp[int(S[i:])%P] += 1
    from functools import reduce
    def Comb(N, A):
        num = reduce(lambda x, y: x * y, range(N, N-A, -1))
        den = reduce(lambda x, y: x * y, range(1, A+1))
        return num//den
    ans = lp[0]
    for i in range(P):
        ans += Comb(lp[i], 2)
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=input()[::-1]
A=[0]*n
A[0]=int(s[0])
t=1
for i in range(1,n):
  A[i]=(int(s[i])*t+A[i-1])%p
  t=(t*10)%p
ans=0
import collections
D=collections.defaultdict(int)
D[0]=1
if p!=2 and p!=5:
  for i in range(n):
    ans+=D[A[i]]
    D[A[i]]+=1
  print(ans)
else:
  s=s[::-1]
  ans=0
  for i in range(n):
    if int(s[i])%p==0:
      ans+=i+1
  print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

h = 1

su = 0

if P == 2:
    for i in range(N):
        if int(S[i]) % 2 != 0:
            continue
        su += i + 1
    print(su)
    exit()

if P == 5:
    for i in range(N):
        if int(S[i]) % 5 != 0:
            continue
        su += i + 1
    print(su)
    exit()

        



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

B = [0]*(N+1)

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

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


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

print(su)

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
cum_sum.sort()
#print(cum_sum)
ans = 0
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:
N,P = map(int,input().split())
S = input()

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

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=input()[::-1]
A=[0]*n
A[0]=int(s[0])
t=1
for i in range(1,n):
  A[i]=(int(s[i])*t+A[i-1])%p
  t=(t*10)%p
ans=0
import collections
D=collections.defaultdict(int)
D[0]=1
if p!=2 and p!=5:
  for i in range(n):
    ans+=D[p-A[i]]
    D[A[i]]+=1
  print(ans)
else:
  s=s[::-1]
  ans=0
  for i in range(n):
    if int(s[i])%p==0:
      ans+=i+1
  print(ans)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

table = [0] * p
table[0] = 1
d = 1
n = 0
for i in range(len(s)):
    n = (10 * n + s[i]) % p
    table[n] += 1
r = 0
for v in table:
    r += v * (v - 1) // 2
print(r)

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
    K=pow(10,p-2,p)
    invlist=[0 for i in range(n+1)]
    invlist[0]=1
    invlist[1]=K
    for i in range(2,n+1):
        invlist[i]=(invlist[i-1]*K)%p
    uselist=[0 for i in range(n+1)]
    for i in range(n+1):
        uselist[i]=(modlist[i]*invlist[i])%p
    ANS=dict(collections.Counter(uselist))
    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=[int(i) for i in input().split()]
S = str(input())
modlist = [0 for i in range(P)]

for i in range(1,N+1):
    n = int(S[N-i:])
    modlist[n%P] = modlist[n%P]+1
modlist[0]+=1

ans=0
for i in modlist:
    if i>=2:
        ans = ans + i*(i-1)/2

print(int(ans))

Submission status: Wrong Answer

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

pre = 0
ans = 0

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

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

Submission status: Wrong Answer

Solution code:
N,P = map(int,input().split())
S = input()
#s = set()
#for i in range(1,int(S)//P):
#  s.add(P*i)
ret = 0
#print(s)
for end in range(1,len(S)+1):
  for start in range(end):
    #if int(S[start:end]) in s:
    #  ret += 1
    if end-start > len(str(P)) and int(S[start:end])%P==0:
      ret += 1
print(ret)

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)


P = [0] * p

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

# a = 0
# for i in range(n):
#     a = (a * 10 + int(s[i]))
#     a = a%p
#     P[a] += 1

ans = 0
u = 0
v = 0
s = list(s)
for i in range(n):
    s[i] = int(s[i])
# for i in range(n):
#     print(u,P[(p-u)%p])
#     ans += P[(p-u)%p]
#     u = (u-int(s[n-1-i])) % p
#     u = u * inv(10%p, mod) % p
# print(s)
for i in range(n):
    v = (u * 10 + s[i]) % p
    P[v] += 1
    # qq = s[i-1] if i > 0 else 0
    ans += P[(p-v*s[i])%p]
    # print(ans)
    u = v
ans -= 1
if s[-1] == 0:
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7
class mint:
    def __init__(self, x):
        self.x = x % MOD if isinstance(x, int) else int(x) % MOD
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __imod__(self, other):
        self.x %= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __mod__(self, other):
        return (
            mint(self.x % other.x) if isinstance(other, mint) else
            mint(self.x % other)
        )
    def __truediv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rmod__(self, other):
        return (
            mint(other.x % self.x) if isinstance(other, mint) else
            mint(other % self.x)
        )
    def __rtruediv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )

class comb():
    # class <mint> should be imported
    def __init__(self, n):
        self.n = n
        fact = [0]*(n+1) # 1-indexed
        ifact = [0]*(n+1) # 逆元
        fact[0] = mint(1)
        for i in range(1, n+1):
            fact[i] = fact[i-1]*i
        ifact[-1] = pow(fact[-1], MOD-2)
        for i in range(n, 0, -1):
            ifact[i-1] = ifact[i]*i
        self.fact = fact
        self.ifact = ifact
    def calc(self, n, k):
        if k<0 or k>n:
            return 0
        return self.fact[n]*self.ifact[k]*self.ifact[n-k]


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

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

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

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

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


print(ans)

Submission status: Wrong Answer

Solution code:
import re

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

mx = n//p
ans = 0
for i in range(1,mx+1):
    sh = "^0*"+str(p*i) + "$"
    #print(sh)
    ss = re.findall(sh,s)
    ans += len(ss)


print(ans)

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
d = list(map(int, input()))
ans =0
for k in range(0,N):
    for l in range(k+1,N+1):
        num = int("".join(map(str,d[k:l])))
        
        if num == 0:
            break
        elif num % P == 0:
            ans += 1
            print(num)

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import Counter
    input = sys.stdin.readline

    n,p = map(int,input().split())
    s = str(input())
    lis = []

    for i in range(n):
        s_1 = int(s[i:n])
        lis.append(s_1 % p)
    c = Counter(lis)
    c_1 = list(c.values())
    ans = 0
    for i in range(len(c_1)):
        if c_1[i] != 1:
            ans += (c_1[i])**2
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

lst = [0 for i in range(n)]
left = 0
right = 1
while left <= n-1:
    if left == right:
        right += 1
    while int(s[left:right]) % p != 0 and right <= n-1:
        right += 1
    if int(s[left:right]) % p == 0 and right <= n:
        lst[right-1] += lst[left-1] + 1
    left += 1

print(sum(lst))

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=input()
G=[[0]*p for i in range(2)]
G[0]=[i for i in range(p)]
for i in range(p):
  G[1][i]=G[0][i]*10%p
R=[[0]*p for i in range(3)]
a=0
b=1
c=2
for i in range(n):
  x=int(s[i])
  for j in range(p):
    y=(G[1][j]+x)%p
    R[a][y]=R[c][j]+R[c][y]-R[b][j]
  R[a][x%p]+=1
  a=b
  b=c
  c=(c+1)%3
print(R[c][0])

Submission status: Wrong Answer

Solution code:
import numpy as np
n,p=map(int,input().split())
t=np.zeros(p)
g=np.array([(i*10)%p for i in range(p)])
ans=0
for i in input():
    i=int(i)
    t=np.roll(t,i%p)
    t[i%p]+=1
    ans+=t[0]
    t=t[np.argsort(g)]
print(int(ans))

Submission status: Wrong Answer

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

def countSubStr(str, n, k): 
    numMultiples = 0
    seenRemainders = [set() for i in range(n)]# array of n sets, all initially empty
    for i in range(0, n+1):
        remainder = 0
        prefixesFound = 0
        for j in range(i, n):
            remainder = (10 * remainder + int(str[j])) % k
            if remainder in seenRemainders[j]:
                break

            seenRemainders[j].add(remainder)

            if remainder == 0:
                prefixesFound += 1
        numMultiples += prefixesFound * (prefixesFound + 1) / 2
    return int(numMultiples)


def solve(N: int, P: int, S: int):
    S = [c for c in str(S)]
    ans = countSubStr(S, len(S), P)
    print(ans)


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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 = int(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()
ans = 0

# dp[i][j] = S[i:j+1] でみたときの答え
dp = [[0] * N for _ in range(N)]

# 初期値の設定
for i in range(N):
    dp[i][i] = (int(S[i]) % P == 0)  # S[i] が P の倍数なら 1, そうでないなら 0

# 値の更新
for k in range(1, N):
    dp[0][0+k] = dp[0][0+k-1]
    for j in range(N-k):
        dp[j][j+k] += dp[j+1][j+k] + (int(S[j:j+k+1]) % P == 0)

# 求めたいのは dp[0][N-1]
print(dp[0][N-1])

Submission status: Wrong Answer

Solution code:
n,p = map(int,input().split())
s = input()
a = []
for i in range(n):
    for j in range(n-i):
        a.append(min(1,int(s[i:i+j+1])%p))
print(sum(a))

Submission status: Wrong Answer

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

check_list = []

max_n = int(S)//P
result = 0

for i in range(1, max_n+1):
    result += S.count(str(i*P))

print(result)