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()
ans = 0
if p == 2:
    for i,c in enumerate(s,1):
        if int(c)%2 == 0: ans += i
else:
    cnt = [0]*p
    cnt[0] = 1
    x = 0
    d = 1
    for c in s[::-1]:
        x += d*int(c)
        x %= p
        cnt[x%p] += 1
        d *= 10
        d %= p
    # print(cnt)
    for v in cnt: ans += v*(v-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
n,p = map(int,input().split())
s = input()
cnt = [0]*p
cnt[0] = 1
x = 0
d = 1
for c in s[::-1]:
    x += d*int(c)
    x %= p
    cnt[x%p] += 1
    d *= 10
    d %= p
# print(cnt)
ans = 0
if p == 2: ans = cnt[0]*(cnt[0]-1)//2
else:
    for v in cnt: ans += v*(v-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
n,p = map(int,input().split())
s = input()
cnt = [0]*p
cnt[0] = 1
x = 0
d = 1
for c in s[::-1]:
    x += d*int(c)
    cnt[x%p] += 1
    d *= 10
# print(cnt)
ans = 0
for v in cnt: ans += v*(v-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

def solve():
    input = sys.stdin.readline
    N, P = map(int, input().split())
    S = input().strip("\n")
    modSum = 0
    modSum = int(S[0]) % P
    modDict = defaultdict(int)
    ans = 0

    if P == 2 or P == 5:
        for i in range(N):
            if int(S[i]) % P == 0:
                ans += i + 1
        
    else:
        modDict[modSum] += 1
        for i in range(1, N):
            modSum = ((modSum * 10) + int(S[i])) % P
            modDict[modSum] += 1

        for key in modDict:
            v = modDict[key]
            if key > 0: ans += v * (v - 1) // 2
            else: ans += v + (v * (v - 1) // 2)
    
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

def solve():
    input = sys.stdin.readline
    N, P = map(int, input().split())
    S = input().strip("\n")
    modSum = [0] * (N + 1)
    modSum[0] = int(S[0]) % P
    modDict = defaultdict(int)
    modDict[modSum[0]] += 1
    for i in range(1, N):
        modSum[i] = ((modSum[i-1] * 10) + int(S[i])) % P
        modDict[modSum[i]] += 1

    ans = 0
    for key in modDict:
        v = modDict[key]
        if key > 0: ans += v * (v - 1) // 2
        else: ans += v + (v * (v - 1) // 2)
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:

def m():
    n,p=map(int,input().split())
    now=0
    s=input()
    if p==2 or p==5:
        ans=0
        for i in range(n):
            if int(s[i])%p:continue
            ans+=i+1
    else:
        table=[0]*p
        table[0]=1
        for i in s:
            now=(10*now+int(i))%p
            table[now]+=1
        ans=sum(j*(j-1)//2 for j in table)
    print(ans)
if __name__ == "__main__":
    m()

Submission status: Wrong Answer

Solution code:
# E - Divisible Substring
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:
    l = [1]+[0]*(P-1)
    tmp = 0
    for i in range(N):
        tmp = (10*tmp+int(S[i]))%P
        l[tmp] += 1
    for x in l:
        ans += x*(x-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,p = map(int,ipt().split())
    s = input()
    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:
        d = defaultdict(int)
        pi = 0
        for i in s[::-1]:
            pi = (pi*10+int(i))%p
            d[pi] += 1
        for i in d.values():
            ans += i*(i-1)//2
        ans += d[0]
        print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

N, P = map(int, input().split())
S = input()
ac = [0]*(N+1)
for i in range(1, N+1):
    ac[i] = (ac[i-1]+int(S[-i])*pow(10, i-1, P))%P
c = Counter(ac)
ans = 0
for i in c.values():
    ans += i*(i-1)//2
print(ans)

Submission status: Wrong Answer

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

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

    print(ans)
    exit()


mods=[0]*p
mods[0]=1
num=0
fac=1

for i in range(n):
    num+=(int(s[n-i-1])*fac)
    num%=p

    fac=(fac*10)
    fac%=p
    mods[num]+=1

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

print(len(s))
print(mods)
print(ans)

Submission status: Wrong Answer

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

mods=[0]*p
mods[0]=1
num=0
fac=1

for i in range(n):
    num+=(int(s[n-i-1])*fac)%p
    fac=(fac*10)%p
    mods[num%p]+=1

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


print(ans)

Submission status: Wrong Answer

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

mods=[0]*p

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

#print(mods)
ans=mods[0]
for i in range(p):
    #print("i>>",i)
    ans+=(mods[i]*(mods[i]-1))//2


print(ans)

Submission status: Wrong Answer

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

mods=[0]*p

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

#print(mods)
ans=mods[0]
for i in range(p):
    #print("i>>",i)
    ans+=(mods[i]*(mods[i]-1))//2


print(ans)

Submission status: Wrong Answer

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

mods=[0]*p

num=0
for i in range(n):
    num=(num+int(s[-i-1])*(10**i))%p
    mods[num%p]+=1

#print(mods)
ans=mods[0]
for i in range(p):
    #print("i>>",i)
    ans+=(mods[i]*(mods[i]-1))//2


print(ans)

Submission status: Wrong Answer

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

mods=[0]*p

num=0
for i in range(n):
    num=(num+int(s[-i-1])*(10**i))%p
    mods[num%p]+=1

#print(mods)
ans=mods[0]
for i in range(p):
    #print("i>>",i)
    ans+=(mods[i]*(mods[i]-1))//2


print(ans)

Submission status: Wrong Answer

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

mods=[0]*p

num=0
for i in range(n):
    num=(num+int(s[-i-1])*(10**i))%p
    mods[num%p]+=1

#print(mods)
ans=mods[0]
for i in range(p):
    #print("i>>",i)
    ans+=(mods[i]*(mods[i]-1))//2


print(ans%p)

Submission status: Wrong Answer

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

mods=[0]*p

num=0
for i in range(n):
    num=(num+int(s[-i-1])*(10**i))
    mods[num%p]+=1

#print(mods)
ans=0
for i in range(p//2+1):
    #print("i>>",i)
    if i==0:
        ans+=(mods[i]*(mods[i]+1))//2
    elif i*2==p:
        if mods[i]>=2:
            ans+=(mods[i]*(mods[i]-1))//2
    else:
        if i<p-i:
            ans+=mods[i]*mods[p-i]
    #print(ans)

print(ans)

Submission status: Wrong Answer

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

mods=[0]*p

num=0
for i in range(n):
    num=(num+int(s[-i-1])*(10**i))%p
    mods[num]+=1

print(mods)
ans=0
for i in range(p//2+1):
    print("i>>",i)
    if i==0:
        ans=mods[i]
        if mods[i]>=2:
            ans+=(mods[i]*(mods[i]-1))//2
    elif i*2==p:
        if mods[i]>=2:
            ans+=(mods[i]*(mods[i]-1))//2
    else:
        ans+=mods[i]*mods[p-i]
    print(ans)

print(ans)

Submission status: Wrong Answer

Solution code:
## coding: UTF-8

N, P = map(int,input().split())
S = input()[::-1]


remainder = [0] * P
tmp = 0
rad = 1 #10**(i) % P

for i in range(N):
    r = int(S[i])
    tmp += r * rad
    tmp %= P
    remainder[tmp] += 1
    rad *= 10
    rad %= P
remainder[0] += 1


ans = 0
for i in range(P):
    e = remainder[i]
    ans += e*(e-1)/2
print(int(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np

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

dp = np.zeros(p,dtype = int)

count = 0
d = 1
for i in range(n):
    ne_ar = np.zeros(p,dtype = int)
    ne = (int(s[n-i-1]) * d) % p
    ne_ar[ne:] += dp[:(p-ne)]
    ne_ar[:ne] += dp[(p-ne):]
    ne_ar[ne] += 1
    dp = ne_ar
    d *= 10
    d %= p
    count += ne_ar[0]

print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

dp = np.zeros(p)

count = 0
d = 1
for i in range(n):
    ne_ar = np.zeros(p)
    ne = (int(s[n-i-1]) * d) % p
    ne_ar[ne:] += dp[:(p-ne)]
    if(ne != 0):
        ne_ar[:ne] += dp[(p-ne):]
    ne_ar[ne] += 1
    dp= ne_ar
    d *= 10
    d %= p
    count += int(ne_ar[0])

print(count)

Submission status: Wrong Answer

Solution code:
n, p = [int(_) for _ in 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)
    exit()

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

ans = 0
for c in P:
    ans += c*(c-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n,p=map(int,input().split())
s=input()[::-1]
DP=[0]
ans=0

if p==2 or p==5:
    for i,j in enumerate(s):
        if int(j)%p==0:
            ans +=i+1
else:
    num,point=0,1
    for i in s:
        num +=int(i)*point
        num %=p
        DP.append(num)
        point *=10
        point %=p

    DP=Counter(DP)
    for v,m in DP.items():
        if m>=2:ans +=m*(m-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n,p=map(int,input().split())
s=input()[::-1]
DP=[0]

if p==2 or p==5:
    if int(s[0])%p==0:print(n*(n+1)//2)
    else:print(0)
else:
    num,point=0,1
    for i in s:
        num +=int(i)*point
        num %=p
        DP.append(num)
        point *=10
        point %=p

    ans=0
    DP=Counter(DP)
    for v,m in DP.items():
        if m>=2:ans +=m*(m-1)//2
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n,p=map(int,input().split())
s=input()[::-1]
DP=[0]

num,point=0,1
for i in s:
    num +=int(i)*point
    num %=p
    DP.append(num)
    point *=10
    point %=p

ans=0
DP=Counter(DP)
for v,m in DP.items():
    if m>=2:ans +=m*(m-1)//2
print(ans)

Submission status: Wrong Answer

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

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

ans = L[0]
for i in range(P):
    ans += L[i]*(L[i]-1)//2

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

mods = [0] * (N+1)

for i in reversed(range(N)):
    mods[i] = (mods[i+1] + pow(10, N-i-1, P) * int(S[i]))% P

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

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n, p = map(int, input().split())
s=input()
d = defaultdict(int)

    

for i in range(n):

    x = s[i:]

    while x[0]=="0" :
        if len(x) == 1:
            break
        x = x[1:]

    d[int(x)%p]+=1

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

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
S=input()
list=[0 for _ in range(P)]
list[0]=1
now=0
a=0
if P==2 or P==5:
  for s in reversed(S):
    if int(s)%P==0:
      a+=1
  print(int(a*(a+1)/2))
    

else:
  b=1
  h=0
  for s in reversed(S):
    h=h+b*int(s)
    list[h%P]+=1
    b=b*10%P
    
  c=0
  for i in range(len(list)):
    c+=list[i]*(list[i]-1)/2
  print(int(c))

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
S=input()
list=[0 for _ in range(P)]
list[0]=1
now=0
a=0
if P==2 or P==5:
  for s in reversed(S):
    if int(s)==P:
      a+=1
  print(a*(a+1)/2)
    

else:
  b=1
  h=0
  for s in reversed(S):
    h=h+b*int(s)
    list[h%P]+=1
    b=b*10%P
    
c=0
for i in range(len(list)):
  c+=list[i]*(list[i]-1)/2
print(int(c))

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
S=input()
list=[0 for _ in range(P)]
list[0]=1
now=0
b=1
for i in range(len(S)):
  now+=b*int(S[len(S)-i-1])
  list[now%P]+=1
  b=b*10
  i+=1
c=0
for i in range(len(list)):
  c+=list[i]*(list[i]-1)/2
print(int(c))

Submission status: Wrong Answer

Solution code:
#!python3

LI = lambda: list(map(int, input().split()))

# input
N, P = LI()
S = input()


def main():
    d = {i: 0 for i in range(P)}
    w = 0
    d[0] = 1
    ans = 0
    m = 1
    for s in S[::-1]:
        x = int(s)
        v = x * m % P
        w = (w + v) % P
        ans += d[w]
        d[w] += 1
        m = 10 * m % P
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout

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

# s = input()
# n = len(s)
# P = 2019


if len(s) <= 3:
    print(0)
    exit()

suffix_rems = [-1]*n
suffix_rems[-1] = int(s[-1])%P

rems_d = dict()
if int(s[-1])%P==0:
    rems_d[0] = 2
else:
    rems_d[0] = 1
    rems_d[int(s[-1])%P] = 1


special_keys = set()
for i in range(n-1)[::-1]:
    rem = (pow(10, n-i-1, P) * int(s[i]) + suffix_rems[i + 1])%P

    if rem in rems_d:
        rems_d[rem] += 1
        special_keys.add(rem)
    else:
        rems_d[rem] = 1

    suffix_rems[i] = rem

# print(suffix_rems)
# print(rems_d)
ans = 0
for key in special_keys:
    t = rems_d[key]
    # if key == 0:
    #     ans += t
    ans += (t*(t-1))//2

print(ans)

Submission status: Wrong Answer

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

if P==5:
    ans = 0
    for i,m in enumerate(S):
        if m == '5' or m == '0':
            ans += i+1
elif P==2:
    ans = 0
    for i,m in enumerate(S):
        if int(m) % 2 ==0:
            ans += i+1
else:
    S = int(S)
    primdic = defaultdict(int)
    for i in range(1,N):
        # i~右端までの数字のmodPをキーにする
        primdic[(S%(10**i))%P] += 1
    # 文字なしの時はあまり0なので
    primdic[0] += 1
    ans = 0
    for value in primdic.values():
        ans += value*(value-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, P = map(int,input().split())
S = input()
primdic = defaultdict(int)
for i in range(N):
    primdic[int(S[i:])%P] += 1
primdic[0] += 1
ans = 0
for value in primdic.values():
    ans += value*(value-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
N,P = map(int,input().split())
S = map(int,input())
S_li = [0]*(N+1)
S_rev = reversed(tuple(S))
counter = 0
tmp = 0
count= 0
from  collections import Counter

if 10%P==0:
    for i,num in enumerate(S_rev):
        if num==P or num==0:
            counter += N-i
    print(counter)

else:
    ctr = [0] * P
    ctr[0] = 1
    ret = 0
    t = 0
    c = 1
    for x in S_rev:
        t = (t + c * x) % P
        ret += ctr[t]
        ctr[t] += 1
        c = c * 10 % P
 
    print(ret)

Submission status: Wrong Answer

Solution code:
N,P = map(int,input().split())
S = input()
S_li = [0]*(N+1)
S_rev = reversed(S)
counter = 0
tmp = 0
count= 0
from  collections import Counter

if 10%P==0:
    for i,num in enumerate(S_rev):
        if num==str(P) or num=="0":
            counter += N-i
    print(counter)

else:
    for i,num in enumerate(S_rev):
        tmp += int(num)*(10**i)%P
        S_li[i+1] = (S_li[i] + int(num)*pow(10,i,P))%P 
    
    
    S_count = Counter(S_li)

    for key in S_count.keys():
        count = S_count[key]
        counter += count*(count-1)//2
    
    print(counter)

Submission status: Wrong Answer

Solution code:
N,P = map(int,input().split())
S = input()
S_li = []
S_rev = reversed(S)
counter = 0
tmp = 0
count= 0
from  collections import Counter

if 10%P==0:
    for i,num in enumerate(S_rev):
        if num==str(P) or num=="0":
            counter += N-i
    print(counter)

else:
    for i,num in enumerate(S_rev):
        tmp += int(num)*(10**i)%P
        S_li.append(tmp%P)
    
    
    S_count = Counter(S_li)
    for key in S_count.keys():
        count = S_count[key]
        counter += count*(count-1)//2
    counter += S_count[0]
    print(counter)

Submission status: Wrong Answer

Solution code:
N,P = map(int,input().split())
S = input()
S_li = []
S_rev = reversed(S)
counter = 0
tmp = 0
count= 0


if 10%P==0:
    for i,num in enumerate(S_rev):
        if num==str(P) or num=="0":
            counter += N-i
    print(counter)

else:
    for i,num in enumerate(S_rev):
        tmp += int(num)*(10**i)
        S_li.append(tmp%P)
    
    
    S_set = set(S_li)

    for k in S_set:
        count = S_li.count(k)
        counter += count*(count-1)//2
    counter += S_li.count(0)
    print(counter)

Submission status: Wrong Answer

Solution code:
N,P = map(int,input().split())
S = input()
S_li = []
S_rev = reversed(S)
counter = 0
tmp = 0
count= 0
print(S_rev)

if 10%P==0:
    for i,num in enumerate(S_rev):
        if num==str(P) or num=="0":
            counter += N-i
    print(counter)

else:
    for i,num in enumerate(S_rev):
        tmp += int(num)*(10**i)
        S_li.append(tmp%P)
        print(tmp)
    
    S_set = set(S_li)

    print(S_li)

    for k in S_set:
        count = S_li.count(k)
        counter += count*(count-1)//2
    counter += S_li.count(0)
    print(counter)

Submission status: Wrong Answer

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

total = 0
if mod == 2 or mod == 5:
	for i, q in enumerate(s):
		if int(q)%mod == 0:
			total += i+1
else:
	counts = [0]*mod
	counts[0] = 1
	h = 0
	
	d = 1
	for t in reversed(s):
		m = int(s)*d%mod
		h = (h+m)%mod
		total += counts[h]
		counts[h] += 1
		d = (d*10)%mod

print(total)

Submission status: Wrong Answer

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

    if 10 % P == 0:
        ret = 0
        for i, x in enumerate(reversed(tuple(A)), start=0):
            if x % P == 0:
                ret += N - i
        print(ret)
        return

    acc = [0] * P
    acc[0] = 1

    ret = 0
    t = 0
    for x in A:
        t = (t * 10 + x) % P
        ret += acc[t]
        acc[t] += 1

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,P = map(int,input().split())
S = input().strip()
A = [0 for _ in range(N)]
A[-1] = int(S[-1])%P
b = 1
for i in range(N-2,-1,-1):
    a = int(S[i])%P
    b = (10*b)%P
    A[i] = (A[i+1]+(a*b)%P)%P
C = {i:0 for i in range(P)}
for i in range(N):
    C[A[i]] += 1
ans = C[0]
for j in range(P):
    n = C[j]
    ans += (n*(n-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):
        if int(c)%P==0:
            ans += i+1
    print(ans)
    exit()

mem = [0]
for c in S:
    mem.append((mem[-1]*10 + int(c)) % P)
from collections import Counter
ctr = Counter(mem)
ans = 0
for v in ctr.values():
    ans += v*(v-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,copy
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()))

n,p = inpl()
t = list(input())[::-1]
d = defaultdict(int)
now = 0
d[now] += 1
for i,x in enumerate(t):
    tmp = (pow(10,i,p) * int(x)) % p
    now += tmp
    now %= p
    d[now] += 1
res = 0
# print(d)
for va in d.values():
    res += va*(va-1)//2
print(res)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n,mod = map(int,input().split())
s = input()
l = [0]*(n+1)
for i in range(n-1,-1,-1):
    l[i] = (l[i+1]+int(s[i])*pow(10,n-1-i,mod))%mod
#print(l)
c = Counter(l)
#print(c)
def nC2(i):
    return i*(i-1)//2
ans = c[0]-1+nC2(c[0]-1)
for i in range(1,mod):
    ans += nC2(c[i])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

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

A = [0]  #A[i] = 下i桁をPで割った余り
for i in range(1,N+1):
    A.append((A[i-1]+pow(10,i,P)*S[N-i]) % P)

from collections import Counter

c = Counter(A)
B = c.values()

ans = 0

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

print(ans)

Submission status: Wrong Answer

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

ls = [0]*P
ans = 0
m = 10 % P
for i in range(N):
    n = int(S[i]) % P
    l = [0]*P
    for i in range(P):
        x = (i*m + n) % P
        l[x] = ls[i]
    ls = [y for y in l]
    ls[n] += 1
    ans += ls[0]

print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin 
from collections import Counter

N, P = map(int, stdin.readline().split())
S = stdin.readline().strip()

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


else:

	count = Counter()
	ten = 1
	mod = 0
	for i in range(N):
		x = (int(S[N - i - 1])*ten + mod) % P
		ten = ten*10 % P 
		mod = x
		count[x] += 1

	count[0] += 1


	for i in count.values():
		ans += i*(i - 1)//2

print (ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin 

N, P = map(int, stdin.readline().split())
S = stdin.readline().strip()
print (S, N, P)

dp = [[0]*N for _ in range(N)]
ans = 0
for i in range(N):
	dp[i][i] = (int(S[i]) % P)
	if dp[i][i] == 0:
		ans += 1

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

print (ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

def ep(*params):
    print(*params,file=sys.stderr)

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

ans = 0
d = [0]*(N+1)
cnt = [0]*P
ten = 1

for i in range(N-1,-1,-1):
    a = int(S[i]) * ten % P
    d[i] = (d[i+1]+a) % P
    ten *= 10
    ten %= P

ep(d)

for i in range(N,-1,-1):
    ans += cnt[d[i]]
    cnt[d[i]] += 1;
    ep(i,ans,cnt)
ep(cnt)
ans = 0
for i in cnt:
    ans += int((i*(i-1))/2)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

total = 0
if p in [2, 5]:
    for i in range(n-1, -1, -1):
        if int(s[i]) % p == 0:
            total += i + 1
else:
    dp = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        dp[i] = (dp[i + 1] * 10 + int(s[i])) % p

    c = Counter(dp)

    for k, v in c.items():
        if v >= 2:
            total += v * (v - 1) // 2

print(total)

Submission status: Wrong Answer

Solution code:
from collections import Counter


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)


def combination(n, r, mod=10**9+7):
    """
    nCr mod m
    """
    if n < r:
        return 0
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


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

total = 0
if p in [2, 5]:
    for i in range(n-1, -1, -1):
        if int(s[i]) % p == 0:
            total += i + 1
else:
    dp = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        dp[i] = (dp[i + 1] * 10 + int(s[i])) % p

    c = Counter(dp)

    for k, v in c.items():
        if v >= 2:
            total += combination(v, 2)

print(total)

Submission status: Wrong Answer

Solution code:
N,P = map(int,input().split())
lst=[int(d) for d in input()]
chk=[0]*P
t=0
c=1
if N==2:
 ans=0 
 a=N
 for x in lst[::-1]:
  if x%2==0:
   ans+=a
  a-=1
 print(ans)
elif N==5:
 ans=0 
 a=N
 for x in lst[::-1]:
  if x%5==0:
   ans+=a
  a-=1
 print(ans)
else:
 for x in lst[::-1]:
  t+=c*x
  t%=P
  chk[t]+=1
  c*=10
  c%=P 
 md=0
 ans=chk[0]
 d=1
 for i in range(N-1):
  md=(md+lst[N-1-i]*d)%P
  if chk[md]>0:
   chk[md]-=1
  ans+=chk[md]
  d*=10
  d%=P
 print(ans)

Submission status: Wrong Answer

Solution code:
N,P = map(int,input().split())
lst=[int(d) for d in input()]
chk=[0]*P
t=0
for x in lst[::-1]:
 t=(t*10+x)%P
 chk[t]+=1
md=0
ans=chk[0]
for i in range(N-1):
 md=(md*10+lst[N-1-i])%P
 if chk[md]>0:
  chk[md]-=1
 ans+=chk[md]
print(ans)

Submission status: Wrong Answer

Solution code:
N,P = map(int,input().split())
lst=[int(d) for d in input()]
chk=[0]*P
t=0
for x in lst[::-1]:
 t=(t*10+x)%P
 chk[t]+=1
md=0
ans=chk[0]
for x in lst[::-1]:
 md=(md*10+x)%P
 if chk[md]>0:
  chk[md]-=1
 ans+=chk[md]
print(ans)

Submission status: Wrong Answer

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

if P == 2 or P == 5:
    def solve25(N, P, S):
        c = 0
        for i in range(N-1, -1, -1):
            if int(S[i]) % P == 0:
                # 以降桁を増やしてもOK
                c += i+1
        return c
    print(solve25(N, P, S))
else:
    def solve(N, P, S):
        rcounts = [0] * P
        rcounts[0] = 1 # sそのものが割り切れた場合に引き算する相手がいないから
        ints = 0
        for i, s in enumerate(S[::-1]):
            ints += int(s)
            r = ints % P
            rcounts[r] += 1
            ints *= 10
        c = 0
        for v in rcounts:
            if v > 1:
                c += v*(v-1)//2
        return c
    print(solve(N, P, S))

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, P = map(int, input().split())
S = list(map(int, list(input())))
ans = 0
if P in (2, 5):
    cnt = 0
    for i, s in enumerate(S):
        if s % 2 == 0:
            ans += i+1
else:
    S.reverse()
    now = 0
    d = [0] * (N+1)
    for i in range(N):
        now += S[i] * pow(10, i, P)
        now %= P
        d[i] = now % P
    c = Counter(d)
    for i, v in c.items():
        ans += v*(v-1)//2
    #print(d)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, P = map(int, input().split())
S = list(map(int, list(input())))
ans = 0
if P == (2, 5):
    cnt = 0
    for i, s in enumerate(S):
        if i % 2 == 0:
            ans += i+1
else:
    S.reverse()
    now = 0
    d = [0] * (N+1)
    for i in range(N):
        now += S[i] * pow(10, i, P)
        d[i] = now % P
    c = Counter(d)
    for i, v in c.items():
        ans += v*(v-1)//2
    #print(d)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, P = map(int, input().split())
S = list(map(int, list(input())))
S.reverse()
ans = 0
if P == (2, 5):
    cnt = 0
    for i, s in enumerate(S):
        if i % 2 == 0:
            ans += i+1
else:
    now = 0
    d = [0] * (N+1)
    for i in range(N):
        now += S[i] * pow(10, i)
        d[i] = now % P
    c = Counter(d)
    for i, v in c.items():
        ans += v*(v-1)//2
    #print(d)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, P = map(int, input().split())
S = list(map(int, list(input())))
S.reverse()
ans = 0
if P == 2:
    cnt = 0
    for i in S:
        if i % 2 == 0:
            cnt += 1
    ans = cnt * (cnt+1) // 2
elif P == 5:
    cnt = 0
    for i in S:
        if i in (0, 5):
            cnt += 1
    ans = cnt * (cnt+1) // 2     
else:
    now = 0
    d = [0] * (N+1)
    for i in range(N):
        now += S[i] * pow(10, i)
        d[i] = now % P
    c = Counter(d)
    for i, v in c.items():
        ans += v*(v-1)//2
    #print(d)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, P = map(int, input().split())
S = list(map(int, list(input())))
S.reverse()
S = [0] + S
ans = 0
if P == 2:
    cnt = 0
    for i in S:
        if i % 2 == 0:
            cnt += 1
    ans = cnt * (cnt-1) // 2
elif P == 5:
    cnt = 0
    for i in S:
        if i in (0, 5):
            cnt += 1
    ans = cnt * (cnt-1) // 2     
else:
    now = 0
    d = [0] * (N+1)
    for i in range(N):
        now += S[i] * pow(10, i)
        d[i] = now % P
    c = Counter(d)
    for i, v in c.items():
        ans += v*(v-1)//2
    #print(d)


print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

s = input()


a = 0
t = list(map(int, list(s)))
t.reverse()


if p == 2:
    for i in range(n):
        if t[i] % 2 == 0:
            a += len(t) - i 
elif p == 5:
    for i in range(n):
        if t[i] % 5 == 0:
            a += len(t) - i 

else:
    u = []
    k = 1
    for i in t:
        l = 0
        if i == 0:
            l = i*k % p
            u.append(k)
        else:
            l = (l + i*k) % p
            u.append(l)
        k = k * 10 % p

    c = Counter(u)
    a += c[0]
    for i in c.values():
        if i > 1:
            a += i * (i-1) // 2


print(a)

Submission status: Wrong Answer

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

s = int(input())

a = 0
t = []

while s > 0:
    d = s // 10
    r = s % 10
    t.append(r)
    s = d

u = []

for i in range(len(t)):
    u.append(t[i]*(10**i) % p)

for i in range(len(u)):
    for j in range(i, len(u)):
        if sum(u[i:j+1]) % p == 0:
            a += 1

print(a)

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
s=input()
S=s[::-1]

if 10%P!=0:
    D={}
    D[0]=1
    ans=0
    Num=0
    for i in range(N):
        if (Num*10+int(S[i]))%P not in D:
            D[(Num*10+int(S[i]))%P]=1
        else:
            ans+=D[(Num*10+int(S[i]))%P]
            D[(Num*10+int(S[i]))%P]+=1
        Num=(Num*10+int(S[i]))%P
    print(ans)
else:
    cnt=0
    for i in range(N):
        if int(s[i])%P==0:
            cnt+=i+1
    print(cnt)