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:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000)
# mod = 10 ** 9 + 7
mod = 998244353


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


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)


def main():
    N, P = read_values()
    S = input().strip()

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

    else:
        r = 0
        D = {0: 1}
        for i, s in enumerate(S[::-1]):
            r = (r * 10 + int(s)) % P
            D[r] = D.setdefault(r, 0) + 1
        res = 0
        for v in D.values():
            res += v * (v - 1) // 2

        print(res)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, p = map(int, input().split())
    s = input()
    mu = [None]*n
    ans = 0
    c = [0]*p
    if 10%p == 0:
        ss = map(int, s)
        ss = list(ss)
        for i in range(n):
            if ss[i]%p == 0:
                ans += i+1
        print(ans)
        return
    sr = s[::-1]
    ssr = map(int, sr)
    v = 0
    for i, si in enumerate(ssr):
        v = (v + si%p)%p
        mu[i] = v
        c[v] += 1
    c[0] += 1
    for i in c:
        if i:
            ans += ((i-1)*i)//2
        
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, p = map(int, input().split())
    s = input()
    mu = [None]*n
    ans = 0
    c = [0]*p
    if 10%p == 0:
        for i in range(n):
            if int(s[i])%p == 0:
                ans += i+1
        print(ans)
        return
    num = int(s)
    keta = n
    for i in range(n):
        v = num%p
        mu[i] = v
        c[v] += 1
        num -= int(s[i])*10**keta
        keta -= 1
    c[0] += 1
    for i in mu:
        c[i] -= 1
        ans += c[i]
        
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, P = getlist()
	S = list(input())
	if P == 2:
		ans = 0
		for i in range(N):
			if int(S[i]) % 2 == 0:
				ans += i + 1
		print(ans)
		return

	if P == 5:
		ans = 0
		for i in range(N):
			if int(S[i]) % 5 == 0:
				ans += i + 1
		print(ans)
		return
	
	D = defaultdict(int)
	D[0] = 1
	var = 0
	for i in range(N):
		var = var * 10 + int(S[i])
		var %= P
		D[var] += 1

	ans = 0
	for i in D:
		var = D[i]
		ans += int((var * (var - 1)) // 2)

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, P = getlist()
	S = list(input())
	if P == 2:
		ans = 0
		for i in range(N):
			if int(S[i]) % 2 == 0:
				ans += i + 1
		print(ans)
		return

	elif P == 5:
		ans = 0
		for i in range(N):
			if int(S[i]) % 5 == 0:
				ans += i + 1
		print(ans)
		return
	
	D = defaultdict(int)
	D[0] = 1
	var = 0
	for i in range(N):
		var = var * 10 + int(S[i])
		var %= P
		D[var] += 1

	ans = 0
	for i in D:
		var = D[i]
		ans += int((var * (var - 1)) // 2)

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, P = getlist()
	S = list(input())
	D = defaultdict(int)
	D[0] = 1
	var = 0
	for i in range(N):
		var = var * 10 + int(S[i])
		var %= P
		D[var] += 1

	ans = 0
	for i in D:
		var = D[i]
		ans += int((var * (var - 1)) // 2)

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, P = getlist()
	S = list(input())
	D = defaultdict(int)
	D[0] = 1
	var = 0
	for i in range(N):
		var = var * 10 + int(S[i])
		var %= P
		D[var] += 1

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

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, P = getlist()
	S = list(input())
	D = defaultdict(int)
	D[0] = 1
	var = 0
	for i in range(N):
		var = var * 10 + int(S[i])
		var %= P
		D[var] += 1

	ans = 0
	for i in D:
		var = D[i]
		ans += int(var * (var - 1) // 2)

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

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

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

else:
    mm = {}
    for i in range(n - 1, -1, -1):
        u = int(s[i:])
        r = u % p
        if r in mm:
            l = len(mm[r])
            c += l
            mm[r] = [i] + mm[r]
        else:
            mm[r] = [i]

        if r == 0:
            c += 1
        
print(c)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

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

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

else:
    mm = {}
    for i in range(n - 1, -1, -1):
        u = int(s[i:])
        r = u % p
        if r in mm:
            mm[r] = [i] + mm[r]
        else:
            mm[r] = [i]

        if r == 0:
            c += 1

    for k in mm:
        l = len(mm[k])
        c += (l - 1) * l // 2
        
print(c)

Submission status: Wrong Answer

Solution code:
# from collections import Counter
n, p = map(int, input().split())
s = [int(i) for i in input()]
p_cnt = 0

if p == 2 or p == 5:
    for i in range(n):
        if s[i] % p == 0:
            p_cnt += i+1
else:
    s = s[::-1]
    div_dic = dict(zip(range(p), [0] * p))
    tmp = 0

    for i in range(n):
        tmp += s[i] * pow(10, i, p)
        tmp %= p
        div_dic[tmp] += 1

    print(div_dic)
    for v in div_dic.values():
        p_cnt += v * (v - 1)
    p_cnt //= 2
    p_cnt += div_dic.get(0)

print(p_cnt)

Submission status: Wrong Answer

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

div_dic = dict(zip(range(p), [0] * p))

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

for v in div_dic.values():
    p_cnt += v * (v - 1) * 0.5

print(int(p_cnt))

Submission status: Wrong Answer

Solution code:

def main():
    N, P = map(int, input().split())
    S = input()
    ans = 0
    mods = [0 for i in range(N+1)]
    digits = 1

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

    print(ans)

main()

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
# Python3 program to Split string into characters 
def split(word): 
    return [char for char in word]  
Numberstring=input()
Numberlist=split(Numberstring)
ans=0
modulotally=[]
for i in range(0,P):
  modulotally.append(0)
for i in range(0,N):
  temptally=modulotally.copy()
  for j in range(0,P):
    modulotally[(10*j+int(Numberlist[i]))%P]=temptally[j]
  modulotally[int(Numberlist[i])%P]=modulotally[int(Numberlist[i])%P]+1
  ans=ans+modulotally[0]
print(ans)

Submission status: Wrong Answer

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

ans = 0
s = s[::-1]

if p == 2 or p == 5:
    for i in range(n):
        if s[i]%p == 0:
            ans += i+1
    print(ans)
    
else:
    res = [0] * p
    arr = [0] * n
    tmp = 0
    for i in range(n):
        tmp += s[i]*pow(10,i,p)
        tmp %= p
        arr[i] = tmp
    for i in arr:
        res[i] += 1
    for i in res:
        ans += i*(i-1)
    ans //= 2
    ans += res[0]
        
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

ans = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i])%p == 0:
            ans += i+1
    print(ans)
    sys.exit()
    
res = [0] * p
arr = [int(s[i:])%p for i in range(n)]
for i in arr:
    res[i] += 1
for i in res:
    ans += i*(i-1)
    ans //= 2
ans += res[0]
    
print(ans)

Submission status: Wrong Answer

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

ans = 0
if p < 10:
    arr = [int(i) % p for i in s]
else:
    arr = [int(i) for i in s]

dp = [0] * p
for i in range(n):
    tmp = arr[i]
    dp = dp[-tmp:] + dp[:-tmp]
    dp[tmp] += 1
    ans += dp[0]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

# import bisect
# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter

# import math

# from numba import jit

# from scipy import
# import numpy as np
# import networkx as nx

# import matplotlib.pyplot as plt

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, p = list(map(int, readline().split()))
    s = input()

    ans = 0

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

        for i in range(p):
            cnt = m[i]
            ans += cnt * (cnt - 1) // 2

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

# import bisect
# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter

# import math

# from numba import jit

# from scipy import
# import numpy as np
# import networkx as nx

# import matplotlib.pyplot as plt

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, p = list(map(int, readline().split()))
    s = input()

    ans = 0

    if p == (2 or 5):
        for i in range(n):
            if int(s[i]) % p == 0:
                ans += (i + 1)
    else:
        from collections import Counter
        m = Counter()
        m[0] = 1
        for i in range(n):
            num = int(s[n - i - 1:n])
            ans += m[num % p]
            m[num % p] += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7

N, P = MI()
S = input()

if P == 2:
    ans = 0
    for i, c in enumerate(S):
        if int(c) % 2 == 0:
            ans += i + 1
    print(ans)
elif P == 5:
    ans = 0
    for i, c in enumerate(S):
        if c in ['5', '0']:
            ans += i + 1
    print(ans)
else:
    d = defaultdict(int)
    s = ''
    for c in reversed(S):
        s += c
        d[int(s) % P] += 1
    ans = 0
    for m, cnt in d.items():
        if m == 0:
            ans += cnt
        ans += cnt * (cnt - 1) // 2
    print(ans)

Submission status: Wrong Answer

Solution code:
import collections

np_list = input().split(" ")
N = int(np_list[0])
P = int(np_list[1])

sum = 0
S = list(map(lambda s:int(s),input()[::-1]))
rem_list = [0]
digit = 1
for i in range(N):
    rem_list.append(((S[i]*digit)%P+rem_list[i])%P)
    digit *= 10
    digit %= P
if P == 2 or P == 5:
    for i in range(1,N+1):
        if rem_list[i] == 0:
            sum += N-i+1
else :
    c = collections.Counter(rem_list[1:])
    for i in range(1,N+1):
        if rem_list[i] == 0:
            sum += 1
        temp =c[rem_list[i]]
        temp -=1
        sum += temp
        c[rem_list[i]] = temp
print(sum)

Submission status: Wrong Answer

Solution code:
np_list = input().split(" ")
N = int(np_list[0])
P = int(np_list[1])

sum = 0
S = list(map(lambda s:int(s),input()[::-1]))
rem_list = [0]
for i in range(N):
    rem_list.append(((S[i]*10**(i))%P+rem_list[i])%P)
if P == 2 or P == 5:
    for i in range(1,N+1):
        if rem_list[i] == 0:
            sum += N-i+1
else :
    for i in range(1,N+1):
        if rem_list[i] == 0:
            sum += 1
        sum += rem_list[i+1:].count(rem_list[i])
print(sum)

Submission status: Wrong Answer

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

count = 0
tmp = ''
for i in range(n-1):
  tmp = ''
  if s[i] == '0':
    continue
  
  for j in range(i,n):
    tmp = tmp + s[j]
    if int(tmp) % p ==  0:
      count += 1

if int(s[n-1]) % p == 0:
  count += 1

print(count)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N,p = map(int,input().split())
S = input()
S = S[::-1]
d = defaultdict(lambda:0)
r = 0
for i in range(N):
    r *= 10
    r += int(S[i])
    r %= p
    d[r] += 1

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

if p==2 or p==5:
    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 defaultdict
N,p = map(int,input().split())
S = input()
d = defaultdict(lambda:0)
r = 0
for i in range(N):
    r *= 10
    r += int(S[i])
    r %= p
    d[r] += 1

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

if p==2 or p==5:
    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()[::-1]
ans=0
if p in [2,5]:
  for i in range(n):
    if int(s[i])%p==0:ans+=i+1
  print(ans)
  exit()
d=[0]*p
t=0
d[t]+=1
for i in range(n):
  t+=(10**i)*int(s[i])
  t%=p
  ans+=d[t]
  d[t]+=1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math
from itertools import product

def comb(n, r):
    if n<0 or r<0 or n-r<0:
        return 0
    return math.factorial(n)//math.factorial(n-r)//math.factorial(r)


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

ans = 0

if P==2 or P==5:
    for i in range(N):
        if S//(10**(N-1-i)) % P == 0:
            ans += i+1
else:
    R=[0]*P
    for i in range(N):
        r = S%(10**(N-i)) % P
        print(r, S%(10**(N-i)))
        R[r] += 1
    tmp = [comb(i, 2) for i in R]
    ans = sum(tmp)+R[0]

print(ans)

Submission status: Wrong Answer

Solution code:
import math
from itertools import product

def comb(n, r):
    if n<0 or r<0 or n-r<0:
        return 0
    return math.factorial(n)//math.factorial(n-r)//math.factorial(r)


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

ans = 0

if P==2 or P==5:
    for i in range(N):
        if S//(10**(N-1-i)) % P == 0:
            ans += i+1
else:
    R=[0]*P
    for i in range(N):
        r = S%(10**(N-i)) % P
        print(r, S%(10**(N-i)))
        R[r] += 1
    tmp = [comb(i, 2) for i in R]
    print(R, tmp)
    ans = sum(tmp)+R[0]

print(ans)

for i, j in product([0,1,2,3], [2]):
    print(i,j,comb(i,j))

Submission status: Wrong Answer

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

if p in (2,5):
    a = tuple(int(c)%p for c in s)
    out = 0
    for i,x in enumerate(a):
        if x==0:
            out += (i + 1)
else:
    a = [0]*n
    tmp = 0
    for i in reversed(range(n)):
        tmp = (tmp + 10**i * int(s[i])) % p
        a[i] = tmp
    d = {i: 0 for i in range(p)}
    d[0] = 1
    out = 0
    for x in a[::-1]:
        out += d[x]
        d[x] += 1
print(out)

Submission status: Wrong Answer

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

if p in (2,5):
    a = tuple(int(c)%p for c in s)
    out = 0
    for i,x in enumerate(a):
        if x==0:
            out += (i + 1)
else:
    a = [0]*n
    tmp = 0
    for i in reversed(range(n)):
        tmp = (tmp * 10 + int(s[i])) % p
        a[i] = tmp
    d = {i: 0 for i in range(p)}
    d[0] = 1
    out = 0
    for x in a[::-1]:
        out += d[x]
        d[x] += 1
print(out)

Submission status: Wrong Answer

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

if p in (2,5):
    a = tuple(int(c)%p for c in s)
    out = 0
    for i,x in enumerate(a):
        if x==0:
            out += (i + 1)
    print(out)
else:
    a = [0]*n
    tmp = 0
    for i in reversed(range(n)):
        tmp = (tmp * 10 + int(s[i])) % p
        a[i] = tmp
    d = {i: 0 for i in range(p)}
    d[0] = 1
    out = 0
    for x in a[::-1]:
        out += d[x]
        d[x] += 1
print(out)

Submission status: Wrong Answer

Solution code:
def choose_2_from_n(n):
    return (n-1)*n/2
l1 = input().split()
[n,p] = [int(x) for x in l1]
s = input()
remainder_pre = [0 for i in range(p)]
full = int(s)
for i in range(1,n+1):
    x = int(s[:i])
    a = ((x%p)*(10**(n-i)%p))%p
    remainder_pre[a] = remainder_pre[a] + 1
out = remainder_pre[0]
for i in range(p):
    if remainder_pre[i] >= 2:
        out += choose_2_from_n(remainder_pre[i])
print(int(out))

Submission status: Wrong Answer

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

zeroCount = 0
for i in s:
    if i == "0":
        zeroCount += 1
    else:
        break
s = s[zeroCount:]
n = len(s)

count = 0
if n != 0:
    i = 1
    while i <= n:
        j = 0
        while j + i <= n:
            crt = int(s[j:j+i])
            if (crt >= p or crt == 0) or crt % p == 0:
                count += 1
            j += 1
        i += 1

    if zeroCount != 0:
        count = count * 2 * zeroCount
else:
    count = int(zeroCount * (zeroCount+1) / 2)
print(count)

Submission status: Wrong Answer

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

zeroCount = 0
for i in s:
    if i == "0":
        zeroCount += 1
    else:
        break
s = s[zeroCount:]
n = len(s)

count = 0

i = 1
while i <= n:
    j = 0
    while j + i <= n:
        crt = int(s[j:j+i])
        if crt >= p and crt % p == 0:
            count += 1
        j += 1
    i += 1

if zeroCount != 0:
    count = count * 2 * zeroCount
print(count)

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
S=input()
s=[0 for i in range(N+1)]
a=[0 for i in range(N+1)]
a[0]=(10**0)%P
for i in range(N):
    A=a[i]
    a[i+1]=(A*(10%P))%P
    s[i+1]=(s[i]+A*int(S[N-i-1]))%P
d=[0 for i in range(P)]
for i in range(len(s)):
    d[s[i]]+=1
ans=0
for D in d:
    ans+=D*(D-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
S=input()
s=[0 for i in range(N+1)]
a=[0 for i in range(N+1)]
a[0]=(10**0)%P
for i in range(N):
    A=a[i]
    a[i+1]=(A*(10%P))%P
    s[i+1]=(s[i]+A*int(S[N-i-1]))%P
d=[0 for i in range(P)]
for i in range(len(s)):
    d[s[i]]+=1
ans=0
if P!=2 and P!=5:
    for D in d:
        ans+=D*(D-1)//2
    print(ans)
elif P==2:
    for i in range(N):
        if int(S[N-1-i])%2==0:
            ans+=(N-i)
    print(ans)
else:
    for i in range(N):
        if int(S[i])%5==0:
            ans+=(N-i)
    print(ans)

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
S=input()
s=[0 for i in range(N+1)]
a=[0 for i in range(N+1)]
a[0]=(10**0)%P
for i in range(N):
    A=a[i]
    a[i+1]=(A*(10%P))%P
    s[i+1]=(s[i]+A*int(S[i]))%P
d=[0 for i in range(P)]
for i in range(len(s)):
    d[s[i]]+=1
ans=0
if P!=2 and P!=5:
    for D in d:
        ans+=D*(D-1)//2
    print(ans)
elif P==2:
    for i in range(N):
        if int(S[N-1-i])%2==0:
            ans+=(N-i)
    print(ans)
else:
    for i in range(N):
        if int(S[i])%5==0:
            ans+=(N-i)
    print(ans)

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
S=input()
s=[0 for i in range(N+1)]
a=[0 for i in range(N+1)]
a[0]=(10**0)%P
for i in range(N):
    A=a[i]
    a[i+1]=(A*(10%P))%P
    s[i+1]=(s[i]+A*int(S[i]))%P
d=[0 for i in range(P)]
for i in range(len(s)):
    d[s[i]]+=1
ans=0
if P!=2 and P!=5:
    for D in d:
        ans+=D*(D-1)//2
    print(ans)
elif P==2:
    for i in range(N):
        if int(S[N-1-i])%2==0:
            ans+=(N-i)
    print(ans)
else:
    for i in range(N):
        if int(S[i])%5==0:
            ans+=(N-i-1)
    print(ans)

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
S=input()
s=[0 for i in range(N+1)]
a=[0 for i in range(N+1)]
a[0]=(10**0)%P
for i in range(N):
    A=a[i]
    a[i+1]=(A*(10%P))%P
    s[i+1]=(s[i]+A*int(S[i]))%P
d=[0 for i in range(P)]
for i in range(len(s)):
    d[s[i]]+=1
ans=0
if P!=2 and P!=5:
    for D in d:
        ans+=D*(D-1)//2
    print(ans)
elif P==2:
    for i in range(N-1):
        if int(S[N-1-i])%2==0:
            ans+=(N-i-1)
    print(ans)
else:
    for i in range(N):
        if int(S[i])%5==0:
            ans+=(N-i-1)
    print(ans)

Submission status: Wrong Answer

Solution code:
def choose_2_from_n(n):
    return (n-1)*n/2
l1 = input().split()
[n,p] = [int(x) for x in l1]
s = input()
remainder_pre = [0 for i in range(p)]
for i in range(1,n+1):
    x = int(s[:i])
    a = x%p
    remainder_pre[a] = remainder_pre[a] + 1
out = remainder_pre[0]
for i in range(p):
    if remainder_pre[i] >= 2:
        out += choose_2_from_n(remainder_pre[i])
print(int(out))

Submission status: Wrong Answer

Solution code:
def choose_2_from_n(n):
    return (n-1)*n/2
l1 = input().split()
[n,p] = [int(x) for x in l1]
s = input()
remainder_pre = [0 for i in range(p)]
for i in range(1,n+1):
    x = int(s[:i])
    remainder_pre[x%p] += 1
out = remainder_pre[0]
for i in range(p):
    if remainder_pre[i] >= 2:
        out += choose_2_from_n(remainder_pre[i])
print(int(out))

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
S=input()
s=[0 for i in range(N+1)]
a=[0 for i in range(N+1)]
a[0]=(10**0)%P
for i in range(N):
    A=a[i]
    a[i+1]=(A*(10%P))%P
    s[i+1]=(s[i]+A*int(S[i]))%P
d=[0 for i in range(P)]
for i in range(len(s)):
    d[s[i]]+=1
ans=0
for D in d:
    ans+=(D)*(D-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
S=input()
s=[0 for i in range(N+1)]
for i in range(N):
    s[i+1]=(s[i]+(10**i)*(int(S[i])))%P
d=[0 for i in range(P)]
for i in range(len(s)):
    d[s[i]]+=1
ans=0
for D in d:
    ans+=(D)*(D-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
# ABC158E
def f(p, s):
  n = len(s)
  count = 0
  for i in range(n):
    for j in range(i, n):
      count += int(s[i:j+1]) % p == 0
  print(count)

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

Submission status: Wrong Answer

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

    if p==2 or p==5:
        for i in s:
            if i%p==0:
                cnt+=1
        print(cnt*(cnt+1)//2)
        exit()

    sm=0
    for i in range(n):
        sm=(sm+s[n-1-i]*(10**i))%p
        m[sm]+=1
    
    for i in m:
        ans+=i*(i-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())))
    cnt,ans=0,0
    m=[0]*p

    if p==2 or p==5:
        for i in s:
            if i%p==0:
                cnt+=1
        print(cnt*(cnt+1)//2)
        exit()

    sm=0
    for i in range(n):
        sm=(sm*10+s[n-1-i])%p
        m[sm]+=1
    
    for i in m:
        ans+=i*(i-1)//2

    print(ans+m[0])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n,p=map(int,input().split())
    s=input()
    m=[0]*n
    for i in range(n):
      m[i]=int(s[i:])%p
    ans=0
    for i in range(n):
        x=m[i]
        for j in range(i+1):
            if j==0:
                y=0
            else:
                y=m[j-1]
            if x-y==0:
                ans+=1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def sumdigit(s,p):
    sum = 0
    for i in s:
        sum =sum + int(i)
        
    if((sum % p)==0):
        return True
    else:
        return False

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

count = 0

for i in range(0,n):
    for j in range(i+1, n+1):
        
        tmp = s[i:j]
        #print('tmp=%s' %tmp)
        
        # 5
        if(p == 5):
            if(tmp[-1]==5):
                count = count + 1
        # 3,9
        elif(p==3 or p==9):
            if(sumdigit(tmp,p)):
                count = count + 1
        else:
            if(int(tmp) % p == 0):
                count = count + 1

print(count)

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = input()
count = 0
if p in {2, 5}:
    for right in range(n):
        if int(s[right]) % p == 0:
            count += (right + 1)
else:
    mod_p_count = [0 for i in range(p)]
    mod_p_count[0] = 1
    for pow in range(n):
        sub_s = int(s) // 10**pow
        mod_p_count[sub_s % p] += 1
    for i in mod_p_count:
        count += i*(i - 1) // 2
print(count)

Submission status: Wrong Answer

Solution code:
from copy import copy
from collections import defaultdict
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:
    dp = [0] * n
    for i in range(n):
        tmp = int(s[i]) * 10 ** i % p
        dp[i] = tmp
    # print('dp', dp)
    for i in range(n):
        cum = copy(dp)
        for j in range(i, n - 1):
            cum[j + 1] = cum[j + 1] + cum[j]
        for k in range(i, n):
            if cum[k] % p == 0:
                ans += 1
        # print(cum)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
"""
方針：まず左端を固定して実際にPで割ったあまりを計算しながら数値列を伸ばしていけばO(N^2)で計算ができる
文字列の左右を固定した場合に（部分文字列について？）Pで割ったあまりを計算できないか，定式化を考えてみよう．
Ui := S[i:N]をSのi文字以降を評価した整数と置く．便宜上UN+1=0とする．
この時Sのi文字目からj文字目までを評価した整数は(Ui - Uj+1)/10^(j+1-i)と表せる．

"""

sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline
read = sys.stdin.read

n, p = [int(i) for i in readline().split()]
s = input()
"""
if p == 2 or p == 5:
    ans = 0
    for i, c in enumerate(s):
        if int(c) % p == 0:
            ans += i + 1
    print(ans)
    exit()
"""

res = [0] * p
res[0] = 1
t = 1
now = 0
for i in s[::-1]:
    i = int(i)
    now += i * t
    now %= p
    res[now] += 1
    t = t * 10 % p
    


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

print(ans)

Submission status: Wrong Answer

Solution code:
N, P = map(int,input("").split(" "))
S = input("")
count = 0
for i in range(N):
  for j in range(N-i):
    tmp = int(S[j:j+i]) if i > 0 else int(S[j])
    if tmp % P == 0:
      count += 1
 
print(count)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from functools import lru_cache


def main():
    n, p = map(int, input().split())
    s = input().strip()
    mod_dict.clear()

    ans = 0
    for i in range(n):
        for j in range(i, n):
            if is_mod_zero(s, i, j, p):
                ans += 1
    print(ans)


mod_dict = {}


def is_mod_zero(s, i, j, p):
    c = int(s[i:j + 1])
    if c in mod_dict:
        return mod_mem(c, p)
    if c == 0:
        return True
    if c < p:
        return False
    if i == j:
        return mod_mem(int(s[i]), p) == 0
    if c < 100:
        return mod_mem(c, p) == 0

    prev_c = int(s[i:j])
    new_c = int(s[j])
    tp = mod_mem(10, p)

    prev_c_mod = mod_mem(prev_c, p)
    new_c_mod = mod_mem(new_c, p)

    c_mod = ((tp * prev_c_mod) % p + new_c_mod) % p
    mod_dict[c] = c_mod
    return c_mod == 0


def mod_mem(a, p):
    if a in mod_dict:
        return mod_dict[a]

    a_mod = a % p
    mod_dict[a] = a_mod
    return a_mod


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=list(map(int,list(input())))
ans=0
d=[0 for i in range(n)]
if 10%p==0:
  for i in range(n):
    if s[i]%p==0:
      ans+=i+1
else:
  for i in range(n):
    a=(s[n-1-i]*10**(n-i))%p
    if i==0:
      d[n-1]=a
    else:
      d[n-1-i]=(d[n-i]+a)%p
      
for i in range(n):
  ans+=d[:n-i].count(d[n-i-1])
print(ans)

Submission status: Wrong Answer

Solution code:
n, p = list(map(int, input().split()))
s = input()
cnt = 0
for i in range(n):
    for j in range(i,n):
        s_ = s[i:j+1]
        if p > int(s_):
            continue
        elif int(s_)%p == 0:
            cnt += 1
print(cnt)

Submission status: Wrong Answer

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