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:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,p = mi()
s = input()
srev = s[::-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)
    exit()

acum = []
from collections import defaultdict
d = defaultdict(lambda :0)
for i in range(1,n+1):
    a = int(srev[:i])
    modd = a % p
    d[modd] += 1
    acum.append((modd,d[modd]))
ans = d[0]
for i in range(n):
    ans += d[acum[i][0]] - acum[i][1]
print(ans)

Submission status: Wrong Answer

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,p = mi()
s = input().strip()
srev = s[-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)
    exit()

acum = []
from collections import defaultdict
d = defaultdict(lambda :0)
for i in range(1,n+1):
    a = int(srev[:i])
    modd = a % p
    d[modd] += 1
    acum.append((modd,d[modd]))
ans = d[0]
for i in range(n):
    ans += d[acum[i][0]] - acum[i][1]
print(ans)

Submission status: Wrong Answer

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

if P != 2 and P != 5:
    count = [0] * P
    count[0] = 1
    lst = [0] * (N + 1)
    for i in range(N):
        lst[i + 1] = ((lst[i] * 10) + int(S[i])) % P
        count[lst[i + 1]] += 1

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

    print (ans)

if P == 2:
    count = 0
    for index, s in enumerate(S):
        if int(s) % 2 == 0:
            count += (index + 1)
    print (count)

if P == 5: 
    count = 0
    for index, s in enumerate(S):
        if int(s) % 5 == 0:
            count += (index + 1)
    print (count)

Submission status: Wrong Answer

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

if P != 2 and P != 5:
    count = [0] * P
    count[0] = 1
    lst = [0] * (N + 1)
    for i in range(N):
        lst[i + 1] = ((lst[i] * 10) + int(S[i])) % P
        count[lst[i + 1]] += 1

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

    print (ans)

if P == 2:
    count = 1
    for s in S:
        if int(s) % 2 == 0:
            count += 1
    print (count * (count - 1) // 2)

if P == 5: 
    count = 1
    for s in S:
        if int(s) % 5 == 0:
            count += 1
    print (count * (count - 1) // 2)

Submission status: Wrong Answer

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

if N != 2 and N != 5:
    count = [0] * P
    count[0] = 1
    lst = [0] * (N + 1)
    for i in range(N):
        lst[i + 1] = ((lst[i] * 10) + int(S[i])) % P
        count[lst[i + 1]] += 1

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

    print (ans)

if N == 2:
    count = 1
    for s in S:
        if int(s) % 2 == 0:
            count += 1
    print (count * (count - 1) // 2)

if N == 5: 
    count = 1
    for s in S:
        if int(s) % 5 == 0:
            count += 1
    print (count * (count - 1) // 2)

Submission status: Wrong Answer

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

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

else:
    sl = [] # S[i:N]%Pのリスト
    for i in range(N):
        sl.append(int(S[i:N])%P)

    t = 0
    for i in reversed(range(10)):
        t = sl.count(i)
        if t > 1:
            ans += t*(t-1)//2
    ans += t

# output
print(ans)

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = input()
 
t = []
q = [0]*p
q[0] = 1
 
for i in range(n):
  q[int(s[i:])%p] += 1
 
res = 0
for i in q:
  if i >=2:
    res += i*(i-1)/2
 
print(int(res))

Submission status: Wrong Answer

Solution code:
import collections

n, p = map(int,input().split())
D = input()
s = [0] * n
mod = 0
out = 0
if 10 % p == 0:
    for i, d in enumerate(D):
        if int(d) % p == 0:
            out += i + 1
else:
    M = [(int(d) * 10 ** (n - i)) % p for i, d in enumerate(D)]
    s[n - 1] = M[n - 1]
    for i in range(n - 2, 0, -1):
        s[i] = (s[i + 1] + M[i]) % p
    C = collections.Counter(s)
    out += C[0]
    for c in C.values():
        out += (int(c) * (int(c) - 1)) / 2
print(int(out))

Submission status: Wrong Answer

Solution code:
import collections

n, p = map(int,input().split())
D = input()
s = [0] * n
mod = 0
out = 0
if 10 % p == 0:
    for i, d in enumerate(D):
        if int(d) % p == 0:
            out += i + 1
else:
    M = [(int(d) * 10 ** i) % p for i, d in enumerate(D)]
    s[0] = M[0]
    for i in range(1, n):
        s[i] = (s[i - 1] + M[i]) % p
    C = collections.Counter(s)
    out += C[0]
    for c in C.values():
        out += (int(c) * (int(c) - 1)) / 2
print(int(out))

Submission status: Wrong Answer

Solution code:
import collections

n, p = map(int,input().split())
D = input()
s = [0] * n
mod = 0
out = 0
if 10 % p == 0:
    for i, d in enumerate(D):
        if int(d) % p == 0:
            out += i + 1
else:
    M = [(int(d) * 10 ** i) % p for i, d in enumerate(D)]
    s[0] = M[0]
    for i in range(1, n):
        s[i] = (s[i - 1] + M[i]) % p
    C = collections.Counter(s)
    out += C[0]
    for c in C.values():
        out += (int(c) * (int(c) - 1)) / 2
print(out)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

if p in (2, 5):
    if p == 2:
        ok_list = [i for i in range(10)][::2]
    else:
        ok_list = [0, 5]
    ans = 0
    for i in range(n):
        if int(s[i]) in ok_list:
            ans += i+1
    print(ans)
else:
    dd = defaultdict(int)
    dd[0] = 1
    prev = 0
    for i in range(n-1, -1, -1):
        d = int(s[i]) * pow(10, i, p)
        prev = (prev + d) % p
        dd[prev] += 1

    print(sum(v*(v-1)//2 for v in dd.values()))

Submission status: Wrong Answer

Solution code:
from collections import Counter
n,p=map(int,input().split())
s=[int(i) for i in input()]
if p==2 or p==5:
  ans=0
  for i in range(n):
    if s[i]%p==0:
      ans+=i+1
  print(ans)
else:
  ans=0
  d=Counter()
  d[0]+=1
  num=0
  for i in range(n-1,-1,-1):
    num=(10*num+s[i])%p
    ans+=d[num]
    d[num]+=1
  print(ans)

Submission status: Wrong Answer

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

mod = [0] * n


v = 0
pow10 = 1

ans = 0


cnt = [0] * p
cnt[0] = 1

for i in range(n - 1, -1, -1):
    v = (pow10 * int(s[i]) + v) % p
    pow10 = (pow10 * 10) % p
    ans += cnt[v]
    cnt[v] += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def main():
    n, p = [int(e) for e in input().split()]
    s = input()

    cnt = 0
    if p == 2 or p == 5:
        cum = 0
        for i in range(n - 1, -1, -1):
            if int(s[i]) % p == 0:
                cum += 1
                cnt += cum
    else:
        D = {n: 0}
        exp = 1
        for i in range(n - 1, -1, -1):
            D[i] = (D[i + 1] + (int(s[i]) * exp % p)) % p
            exp *= 10
            exp %= p

        Di = defaultdict(int)
        Di[0] = 1
        for i in range(n - 1, -1, -1):
            Di[D[i]] += 1
            cnt += Di[D[i]] - 1

    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def main():
    n, p = [int(e) for e in input().split()]
    s = input()

    cnt = 0
    if p == 2 or p == 5:
        cum = 0
        for i in range(n - 1, -1, -1):
            if int(s[i]) % p == 0:
                cum += 1
                cnt += cum
    else:
        D = defaultdict(int)
        D[0] = 1
        for i in range(n - 1, -1, -1):
            m = int(s[i:]) % p
            D[m] += 1
            cnt += D[m] - 1
            
    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def main():
    n, p = [int(e) for e in input().split()]
    s = input()

    cnt = 0
    if p == 2 or p == 5:
        cum = 0
        for i in range(n - 1, -1, -1):
            if int(s[i]) % p == 0:
                cum += 1
                cnt += cum
    else:
        D = defaultdict(int)
        D[0] = 1
        for i in range(n - 1, -1, -1):
            m = int(s[i:]) % p
            D[m] += 1
            cnt += D[m] - 1
        print(D)

    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
for i in range(1):
	N, P = map(int,input().split())
	S = list(map(int, list(input())))

	if P == 2 or P == 5:
		ans = 0

		for i, s in enumerate(S):
			if int(s)%P == 0:
				ans += i+1
		print(ans)

	else:
		tmp = 0

		mod_cnt = [0]*P

		z = 1
		for i, n in enumerate(S):
			tmp += n*z
			z = z * 10 % P
			mod_cnt[int(tmp)%P] += 1
		ans = 0
		for v in mod_cnt:
			ans += v*(v-1)//2
		print(ans+mod_cnt[0])

Submission status: Wrong Answer

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

	if P == 2 or P == 5:
		ans = 0

		for i, s in enumerate(S):
			if int(s)%P == 0:
				ans += i+1
		print(ans)

	else:
		tmp = 0

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

if p in (2, 5):
    if p == 2:
        ok_list = [i for i in range(10)][::2]
    else:
        ok_list = [0, 5]
    ans = 0
    for i in range(n):
        if int(s[i]) in ok_list:
            ans += (i+1)*(i)//2
    print(ans)
else:
    dd = defaultdict(int)
    dd[0] = 1
    for i in range(n):
        dd[int(s[i:]) % p] += 1

    ans = sum(v*(v-1)//2 for v in dd.values())
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

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

ans = sum(v*(v-1)//2 for v in dd.values())
print(ans)

Submission status: Wrong Answer

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

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

def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x
    elif y % 2 == 0:
        return power(x, int(y/2)) ** 2
    else:
        return power(x, int((y-1)/2)) ** 2 * x

def main():
	N, P = MAP()
	S = list(map(int, list(input())))

	if P == 2 or P == 5:
		ans = 0

		for i, s in enumerate(S):
			if int(s)%P == 0:
				ans += i+1
		print(ans)

	else:
		tmp = 0

		mod_cnt = [0]*P

		for i, s in enumerate(S[::-1]):
			tmp += power(10, i) * S[i]
			mod_cnt[tmp%P] += 1
		ans = 0
		for v in mod_cnt:
			ans += v*(v-1)//2
		print(ans+mod_cnt[0])


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import numpy as np

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

    P_list = np.zeros(P)
    P_list[0] = 1

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

    else:
        ans = 0
        Uj = 0
        for i,v in enumerate(S[::-1]):
            Uj = Uj + int(v)*10**(N-i-1)
            amari = Uj%P
            ans = ans + P_list[amari]
            P_list[amari] += 1

        ans = int(ans)

        print ans
        exit()

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

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

    P_list = np.zeros(P)
    P_list[0] = 1

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

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

    else:
        ans = 0
        Uj = 0
        for i in range(N-1, -1, -1):
            Uj = 10*Uj + int(S[i])
            amari = Uj%P
            ans = ans + P_list[amari]

            P_list[amari] += 1

        ans = int(ans)

        print ans
        exit()

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
n,p = map(int,input().split())
s = input()
num = 0
s1 = [0]*(n+1)
ans = 0
if p == 2 or p == 5:
	for i in range(len(s)):
		if int(s[i])%p == 0:
			ans += i+1	
	print(ans)
	exit()
ans = 0
arr = [0]*p
s = s[::-1]
z = 1
for i in range(n):
	s1[i+1] = s1[i] + int(s[i])*z
	z *=10 %p
	s1[i+1] %=p
	arr[s1[i]] += 1
arr[s1[n]]+=1
print(s1)
for i in range(p):
	ans += arr[i] * (arr[i] - 1) // 2
print(ans)

Submission status: Wrong Answer

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

a=[0]*(N+1)
r=[0]*P

def combi(N,K):
    ans1=1
    ans2=1
    for i in range(K):
        ans1=ans1*(N-i)
        ans2=ans2*(K-i)
    ans=ans1//ans2
    return ans

for i in range(N+1):
    a[i]=int(S[:i+1])

if P!=2 and P!=5:
    for i in range(N+1):
        temp=a[i]%P
        r[temp]+=1
    ans=0
    for i in range(P):
        ans+=combi(r[i],2)
elif P==2:
    ans=0
    for i in range(N):
        if int(S[i])%2==0:
            ans+=i+1
elif P==5:
    ans=0
    for i in range(N):
        if int(S[i])==0 or int(S[i])==5:
            ans+=i+1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys


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


n, p = map(int, input(). split())
s = list(map(int, input()[::1]))

cnt = 0
if 10 % p == 0:
    for i, c in enumerate(s):
        if int(c) % p == 0:
            cnt += n - i
else:
    accmod = [0] * p
    num = 0
    for i in range(n):
        num = (num + s[i] * pow(10, i, p)) % p
        accmod[num] += 1
    for v in accmod:
        if v > 1:
            cnt += v * (v - 1) // 2
    cnt += accmod[0]
print(cnt)

Submission status: Wrong Answer

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

ct = Counter()
ct[0] = 1
ans = 0
for i in range(N-1, -1, -1):
    n = int(S[i:])
    mod = n % P
    ans += ct[mod]
    ct[mod] += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def main():
    n, p = [int(e) for e in input().split()]
    s = input()

    cnt = 0
    if p == 2 or p == 5:
        cum = 0
        for i in range(n - 1, -1, -1):
            if int(s[i]) % p == 0:
                cum += 1
                cnt += cum
    else:
        D = defaultdict(int)
        D[0] = 1
        for i in range(n - 1, -1, -1):
            m = int(s[i:]) % p
            D[m] += 1
            cnt += D[m] - 1

    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
S=[int(i) for i in list(input())][::-1]
if P==2 or P==5:
    ans=0
    for i in range(N):
        if S[i]%P==0:
            ans+=N-i
    print(ans)
else:   
    X=[0 for i in range(N+1)]
    tmp=1
    for i in range(N):
        X[i+1]=X[i]+tmp*S[i]
        X[i+1]%=P
        tmp=tmp*10

Submission status: Wrong Answer

Solution code:
import collections
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n,p= map(int, input().split())
s=list(input())
mod=0
ans=[]
s+='0'
count=0

if p==2 or p==5:
    for i in range(n+1):
        if p==2 and s[i]=='0' or '2' or '4' or '6' or '8':
            count+=1
        elif p==5 and s[i]=='0' or '5':
            count+=1
    if count==1:
        print(0)
    else:
        print(combinations_count(count,2))
    exit()



for i in range(n+1):
    if s[n-i]!=0:
        mod+=(pow(10,i,p)*int(s[n-i]))%p
        mod%=p
    ans.append(mod)

ans = collections.Counter(ans)
ans=ans.most_common()
for i in range(len(ans)):
    if ans[i][1]>=2:
        count+=combinations_count(ans[i][1],2)

print(count)

Submission status: Wrong Answer

Solution code:
import collections
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n,p= map(int, input().split())
s=list(input())
mod=0
ans=[]
s+='0'
count=0

if p==2 or p==5:
    for i in range(n+1):
        if p==2 and s[i]=='0' or '2' or '4' or '6' or '8':
            count+=1
        elif p==5 and s[i]=='0' and '5':
            count+=1
    if count==1:
        print(0)
    else:
        print(combinations_count(count,2))
    exit()



for i in range(n+1):
    if s[n-i]!=0:
        mod+=(pow(10,i,p)*int(s[n-i]))%p
        mod%=p
    ans.append(mod)

ans = collections.Counter(ans)
ans=ans.most_common()
for i in range(len(ans)):
    if ans[i][1]>=2:
        count+=combinations_count(ans[i][1],2)

print(count)

Submission status: Wrong Answer

Solution code:
n,p = map(int,input().split())
s = input()
u = [0]*(n+1)
for i in range(n):
    u[i] = int(s[i:])%p
    
count = 0
for i in range(n):
    for j in range(n-i):
        if p == 2 or p == 5:
            if int(s[j])%p == 0:
                count += 1
        else:
            if u[i]==u[i+j+1]:
                count += 1
                
print(count)

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
S=[int(i) for i in list(input())]
X=[0 for i in range(N+1)]
tmp=1
for i in range(N):
    X[i+1]=X[i]+tmp*S[i]
    X[i+1]%=P
    tmp=tmp*10
    tmp%=P
#print(X)
D=dict()
for i in range(N+1):
    if X[i] in D:
        D[X[i]]+=1
    else:
        D[X[i]]=1
ans=0
for k in D:
    ans+=(D[k]*(D[k]-1))//2
#print(D)
print(ans)

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
S=input()
count=0
for i in range(N):
    for k in range(i,N):
        X=int(S[i:k+1])
        if X%P==0:
            count+=1
(count)

Submission status: Wrong Answer

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

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

ans = 0
count = [0] * P
count[0] = 1
for i in range(N):
    ans += count[sum_rem[i]]
    count[sum_rem[i]] += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
S=input()
L=[0]
for i in enumerate(S[::-1]):
    i0=int(i[0])
    i1=int(i[1])
    L.append((10**i0%P * i1 + L[-1])%P)
L.pop(0)    
sl=set(L)
ans=L.count(0)
for i in sl:
    cnt = L.count(i)
    ans += cnt*(cnt-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
S=[int(i) for i in list(input())][::-1]
X=[0 for i in range(N+1)]
tmp=1
for i in range(N):
    X[i+1]=X[i]+tmp*S[i]
    X[i+1]%=P
    tmp=tmp*10
    tmp%=P
#print(X)
D=dict()
for i in range(N+1):
    if X[i] in D:
        D[X[i]]+=1
    else:
        D[X[i]]=1
ans=0
for k in D:
    ans+=(D[k]*(D[k]-1))//2
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n,p=map(int,input().split())
s=input()[::-1]
a=0
t=0
d=1
m=[0]*p
m=[0]
for i in range(n):
  x=int(s[i])*d%p
  m.append((m[-1]+x)%p)
  d=(d*10)%p
c=Counter(m)
for i,j in c.items():
  a+=j*(j-1)//2

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

Submission status: Wrong Answer

Solution code:
from collections import Counter
n,p=map(int,input().split())
s=input()[::-1]
a=0
t=0
d=1
m=[0]*p
m=[0]
for i in range(n):
  x=int(s[i])*d%p
  m.append((m[-1]+x)%p)
  d=(d*10)%p
c=Counter(m)
for i,j in c.items():
  a+=j*(j-1)//2

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

Submission status: Wrong Answer

Solution code:
from collections import Counter
n,p=map(int,input().split())
s=input()[::-1]
a=0
t=0
d=1
m=[0]*p
m=[0]
for i in range(n):
  x=int(s[i])*d%p
  m.append((m[-1]+x)%p)
  d=(d*10)%p
c=Counter(m)
for i,j in c.items():
  a+=j*(j-1)//2

print(a)

Submission status: Wrong Answer

Solution code:
N, P = map(int,input().split())
S = input()
X = []
hoge = 0

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

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

for i in range(N):
    hoge = (hoge*10 + int(S[i]))%P
    X.append(hoge)
X.sort()
ans = 0
hoge = X[0]
count = 1
for i in X[1:]:
    if hoge == i:
        count += 1
    else:
        if hoge == 0:
            ans += count*(count+1)//2
        else:
            ans += count*(count-1)//2
        hoge = i
        count = 1
if hoge == 0:
    ans += count*(count+1)//2
else:
    ans += count*(count-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
N, P = map(int,input().split())
S = input()
X = []
hoge = 0
for i in range(N):
    hoge = (hoge*10 + int(S[i]))%P
    X.append(hoge)
X.sort()
ans = 0
hoge = X[0]
count = 1
for i in X[1:]:
    if hoge == i:
        count += 1
    else:
        if hoge == 0:
            ans += count*(count+1)//2
        else:
            ans += count*(count-1)//2
        hoge = i
        count = 1
if hoge == 0:
    ans += count*(count+1)//2
else:
    ans += count*(count-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
N, P = map(int,input().split())
S = input()
X = []
hoge = 0
for i in range(N):
    hoge = (hoge*10 + int(S[i]))%P
    X.append(hoge)
X.sort()
ans = 0
hoge = X[0]
count = 1
for i in X[1:]:
    if hoge == i:
        count += 1
    else:
        if hoge == 0:
            ans += count*(count+1)//2
        else:
            ans += count*(count-1)//2
        hoge = i
        count = 1
print(ans)

Submission status: Wrong Answer

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, P = iim()
    S = list(map(int, input().rstrip()))

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

    T = [0] * P
    T[0] = 1

    ss, p10 = 0, 1
    for s1 in S[::-1]:
        ss += p10 * s1
        ss %= P
        T[ss] += 1
        ss = 10 * ss % P

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

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def solve_2_or_5(S, p):
    l = len(S)
    ans = 0
    for i in range(l):
        if int(S[i]) % 2 == 0:
            ans += l-i
    
    return ans

def solve():
    n, p = map(int, input().split())
    S = input()
    
    if p == 2:
        return solve_2_or_5(S, 2)
    elif p == 5:
        return solve_2_or_5(S, 5)

    d = defaultdict(int)
    s = ''
    d[0] += 1 # 0を考慮
    for i in S[::-1]:
        s = i + s
        target = int(s)
        m = target % p
        d[m] += 1
    
    ans = 0
    for k, v in d.items():
        # 組み合わせ
        ans += v * (v-1) // 2
    return ans

print(solve())

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def solve_2_or_5(S, p):
    c = 1
    s = ''
    for i in S[::-1]:
        s = i + s
        if int(s[-1]) % p == 0:
            c += 1
    return c * (c-1) // p

def solve():
    n, p = map(int, input().split())
    S = input()
    
    if p == 2:
        return solve_2_or_5(S, 2)
    elif p == 5:
        return solve_2_or_5(S, 5)

    d = defaultdict(int)
    s = ''
    d[0] += 1 # 0を考慮
    for i in S[::-1]:
        s = i + s
        target = int(s)
        m = target % p
        d[m] += 1
    
    ans = 0
    for k, v in d.items():
        # 組み合わせ
        ans += v * (v-1) // 2
    
    return ans

print(solve())

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

else:
    cnt = [0] * p
    cnt[0] = 1
    now = 0
    for i, j in enumerate(reversed(s)):
        now = (int(s) * pow(10, i, p) + now) % p
        ans += cnt[now]
        cnt[now] += 1

print(ans)

Submission status: Wrong Answer

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

if P == 2 or P == 5:
    ans = 0
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i+1
    print(ans)
    import sys
    sys.exit(0)

suf_nums = [-1] * N
s = 0
power = 165
for i in range(N):
    s += int(S[-1-i]) * power
    suf_nums[i] = s
    power *= 10

surpluses = [0] * P
ans = 0
for num in suf_nums:
    surplus = num % P
    surpluses[surplus] += 1
    if surplus == 0:
        ans += surpluses[0]
    else:
        ans += surpluses[surplus] - 1

print(ans)

Submission status: Wrong Answer

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

if P == 2 or P == 5:
    ans = 0
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i+1
    print(ans)
    import sys
    sys.exit(0)

suf_nums = [-1] * N
s = 0
for i in range(N):
    s += int(S[-1-i])
    suf_nums[i] = s
    s *= 10

surpluses = [0] * P
ans = 0
for num in suf_nums:
    surplus = num % P
    surpluses[surplus] += 1
    if surplus == 0:
        ans += surpluses[0]
    else:
        ans += surpluses[surplus] - 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
if __name__ == '__main__':
    lines = sys.stdin.readlines()
    line = [a.strip('\n').split(' ') for a in lines]
    for i,v in enumerate(line):
        if i == 0:
            n = int(v[0])
            p = v[1]
        else:
            numbers = list(v[0])
            # print(numbers)

    count = 0
    leng = len(list(p))
    p = int(p)

    left = []
    right = []
    tar = int(''.join(numbers))

    count = 0

    moto = tar%p

    num = [int(i) for i in numbers]

    for i in range(n):
        tar = int(''.join(numbers[i:n]))
        a = tar % p
        right.append(a)

    if p == 2 or p == 5:
        c = 0
        for i,v in enumerate(num):
            if v % p == 0:
                c += (i+1)

    else:
        c = 0
        c += right.count(0)
        for i,v in enumerate(right):
            if v - moto > 0:
                c += right[i+1:].count(v-moto)
            if v - moto <=0:
                c += right[i+1:].count(moto-v)

    print(c)

Submission status: Wrong Answer

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

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

u = defaultdict(int)
u[0] = 1
for i in range(n,0,-1):
    d = int(s[:i])
    u[d%p] += 1

res = 0
for v in u.values():
    res += v*(v-1)//2

print(res)

Submission status: Wrong Answer

Solution code:
def main():
    N, P = (int(i) for i in input().split())
    S = input()

    ans = 0
    if P == 5:
        for i in range(1):
            for j in range(1, N-i+1):
                num = int(S[i:i+j])
                if num % P == 0:
                    # print("!", end=" ")
                    ans += len(S[i:i+j])
                # print(num)
    elif P == 2:
        for i in range(1):
            for j in range(1, N-i+1):
                num = int(S[i:i+j])
                if num % P == 0:
                    # print("!", end=" ")
                    ans += len(S[i:i+j])
                # print(num)
    """
    A = [int(s) for s in S]
    from itertools import accumulate
    acc = accumulate([0] + A)
    right = N
    for left in range(N):
        while left

    print()
    """
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
if __name__ == '__main__':
    lines = sys.stdin.readlines()
    line = [a.strip('\n').split(' ') for a in lines]
    for i,v in enumerate(line):
        if i == 0:
            n = int(v[0])
            p = v[1]
        else:
            numbers = list(v[0])
            # print(numbers)

    count = 0
    leng = len(list(p))
    p = int(p)

    left = []
    right = []
    tar = int(''.join(numbers))

    count = 0

    moto = tar%p

    num = [int(i) for i in numbers]

    for i in range(n):
        tar = int(''.join(numbers[i:n]))
        a = tar % p
        right.append(a)

    if p == 2 or p == 5:
        c = 0
        for i,v in enumerate(num):
            if v % p == 0:
                c += (i+1)

    else:
        c = 0
        c += right.count(moto)
        for i,v in enumerate(right):
            if v - moto > 0:
                c += right[i+1:].count(v-moto)
            if v - moto <=0:
                c += right[i+1:].count(moto-v)

    print(c)