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:
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi

MOD = 10 ** 9 + 7
SIZE = 10 ** 6

g1, g2, inv = [1, 1], [1, 1], [0, 1]
for i in range(2, SIZE + 1):
    g1.append((g1[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * inv[-1]) % MOD)
    
def comb(n, r):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n - r] % MOD

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

S = S[::-1]

if P == 2 or P == 5:
    tmp = 0
    answer = 0
    for i, s in enumerate(S):
        tmp += int(s) * pow(10, i, P)
        if tmp % P == 0:
            answer += 1
    answer += comb(N, 2)
else:
    cnt = defaultdict(int)
    tmp = 0
    answer = 0
    for i, s in enumerate(S):
        tmp += int(s) * pow(10, i, P)
        if tmp % P == 0:
            answer += 1
        answer += cnt[tmp % P]
        cnt[tmp % P] += 1

print(answer)

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict

MOD = 10 ** 9 + 7
SIZE = 10 ** 6

g1, g2, inv = [1, 1], [1, 1], [0, 1]
for i in range(2, SIZE + 1):
    g1.append((g1[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * inv[-1]) % MOD)
    
def comb(n, r):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n - r] % MOD

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

S = S[::-1]

if P == 2 or P == 5:
    tmp = 0
    answer = 0
    for i, s in enumerate(S):
        tmp += int(s) * 10 ** i
        if tmp % P == 0:
            answer += 1
    answer += comb(N, 2)
else:
    cnt = defaultdict(int)
    tmp = 0
    answer = 0
    for i, s in enumerate(S):
        tmp += int(s) * 10 ** i
        if tmp % P == 0:
            answer += 1
        answer += cnt[tmp % P]
        cnt[tmp % P] += 1

print(answer)

Submission status: Wrong Answer

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

result = 0
for i in range(1, len(s)):
  for j in range(i):
    cur_int = int(s[j:i])
    if cur_int%p == 0:
      result+=1
print(result)

Submission status: Wrong Answer

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline

N,P = MI()
S = S()
mod = 0
ans = 0
dic = {0:1}
if P == 2 or P == 5:
    for i in range(N):
        if int(S[i])%P==0:
            ans += i+1
else:
    for i in range(N-1,-1,-1):
        mod = (mod+10**(N-1-i)*int(S[i]))%P
        dic[mod] = dic.get(mod,0)+1
    for i in dic.values():
        ans += int(i*(i-1)/2)
print(dic,ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline

N,P = MI()
S = S()
mod = 0
ans = 0
dic = {0:1}
if P == 2 or P == 5:
    for i in range(N):
        if int(S[i])%P==0:
            ans += i+1
else:
    for i in range(N-1,-1,-1):
        mod = (mod+10*int(S[i]))%P
        dic[mod] = dic.get(mod,0)+1
    for i in dic.values():
        ans += int(i*(i-1)/2)
print(dic,ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline

N,P = MI()
S = S()
mod = 0
ans = 0
dic = {0:1}
if P == 2 or P == 5:
    for i in range(N):
        if int(S[i])%P==0:
            ans += i+1
else:
    for i in range(N-1,-1,-1):
        mod = (mod*10+int(S[i]))%P
        dic[mod] = dic.get(mod,0)+1
    for i in dic.values():
        ans += int(i*(i-1)/2)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
N,P=map(int, sys.stdin.readline().split())
S=int(sys.stdin.readline().strip())
L=[S%P]
for i in range(N-1,0,-1):
    L.append((S%10**i)%P)
    #L.append(S%10**i)
    S%=10**i
L.append(0)

ans=0
D=defaultdict(lambda: 0)
for x in L:
    ans+=D[x]
    D[x]+=1
print ans

Submission status: Wrong Answer

Solution code:
n,p = map(int,input().split())
s = input()
x = 0
ss = ''
int_ss = 0
ans = 0

for i in range(n-1,-1,-1):
    ss = s[i] + ss
    int_ss = int(ss)

    if int_ss%p == 0:
        ans = ans + 1 + x
        x += 1

print(str(ans))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from collections import Counter
def resolve():
    n, p = map(int, input().split())
    S = input()

    res = 0
    now = 0
    counter = Counter()
    counter[0] = 1
    for i in range(n):
        now = (10 * now + int(S[i])) % p
        k = now * pow(10, -i % (p - 1) , p) % p
        res += counter[k]
        counter[k] += 1
    print(res)
resolve()

Submission status: Wrong Answer

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

S = input()

ans = 0
if P == 2 or P == 5:
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i + 1
else:
    counts = [0] * P
    h = 0
    d = 1
    for s in reversed(S):
        m = int(s) * d % P
        h = (h + m) % P
        counts[h] += 1
        d = (d * 10) % P
    ans = counts[0]
    for i in counts:
        ans += (i*i-1)//2

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

ans = 0

if not 10 % P:
    for r in range(N):
        if not int(S[r]) % P:
            ans += N-r
else:
    S = S[::-1]
    s = 0
    c = Counter()
    c[0] = 1
    
    for i in range(N):
        s = (s + int(S[i]) * pow(10, i, P) % P) % P
        
        ans += c[s]
        c[s] += 1
        
print(ans)

Submission status: Wrong Answer

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

mod = 0
c = [0] * p
c[0] = 1
ten = 1
for i in s:
    mod = (mod + ten * int(i)) % p
    ten = ten * 10 % p
    c[mod] += 1

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = input()
a = []
c = 0
if p == 2:
    b = [0]*n
    for i in range(n):
        if int(s[i])%2 == 0:
            b[i] += 1
    for i in range(n):
        if b[i] == 1:
            c += i+1
elif p == 5:
    b = [0]*n
    for i in range(n):
        if int(s[i])%5 == 0:
            b[i] += 1
    for i in range(n):
        if b[i] == 1:
            c += i+1
else:
    b = [0]*p
    b[0] = 1
    d = [1]
    print(d)
    a.append(int(s[-1])%p)
    for i in range(n-1):
        d.append(d[-1]*10%p)
    for i in range(1, n):
        a.append((int(s[-i-1])*d[i]+a[i-1])%p)
    for i in range(n):
        b[a[i]] += 1
    for i in range(p):
        c += int(b[i]*(b[i]-1)/2)
print(c)

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = input()
a = []
b = [0]*p
b[0] += 1
c = 0
for i in range(n):
    a.append(int(s[i:n])%p)
for i in range(n):
    b[a[i]] += 1
for i in range(p):
    c += int(b[i]*(b[i]-1)/2)
print(c)

Submission status: Wrong Answer

Solution code:
import collections


"""


aaaaaaa   bbbbb
^
i
	  j 
	      (j+1)

sum[i] = ((ll)(S[i] - '0') * ten[i + 1] % P + sum[i + 1]) % P;

"""


n,p = map(int,raw_input().split(' '))
s = map(int,list(raw_input()))

cc = collections.Counter()
count = 0
if p == 2 or p == 5:
	for i in range(len(s)):
		if s[i] % p == 0:
			count += (i+1)
	print count
else:
	cc[0]+=1
	og = 0 
	for i in range(len(s)-1, -1, -1):
		og = (og * 10 + s[i]) % p
		cc[og] += 1
	for k in cc:
		count += cc[k] * (cc[k]-1)/2
	print count

Submission status: Wrong Answer

Solution code:
import collections


"""


aaaaaaa   bbbbb
^
i
	  j 
	      (j+1)

"""
n,p = map(int,raw_input().split(' '))
s = map(int,list(raw_input()))

cc = collections.Counter()
count = 0
if p == 2 or p == 5:
	for i in range(len(s)):
		if s[i] % p == 0:
			count += (i+1)
	print count
else:
	cc[0]+=1
	og = 0 
	for i in range(len(s)-1, -1, -1):
		og = (og * 10 + s[i]) % p
		count += cc[og]
		cc[og] += 1
	print count

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
from collections import defaultdict

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

# MODの管理をして右から進める
N, P = lr()
S = sr()
dic = defaultdict(int)
dic[0] = 1
num = 0
power = 1
answer = 0
for s in S[::-1]:
    s = int(s)
    num += s * power
    num %= P
    answer += dic[num]
    dic[num] += 1
    power *= 10; power %= P

print(answer)
# 14

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
from collections import defaultdict

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

# MODの管理をして右から進める
N, P = lr()
S = sr()
dic = defaultdict(int)
dic[0] = 1
num = 0
power = 1
answer = 0
for s in S[::-1]:
    s = int(s)
    power *= 10; power %= P
    num += s * power
    num %= P
    answer += dic[num]
    dic[num] += 1

print(answer)
# 14

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

    s,p = map(int, input().split())
    n = input().rstrip()
    n = n[::-1]
    res = [0]*p
    res[0] += 1
    b = 1
    c = 0
    for i in range(s):
        a = int(n[i])
        c += a*b
        c %= p
        res[c] += 1
        b = b*10%p
    ans = 0
    for i in res:
        if i>=2:
            ans += i*(i-1)//2
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

U = []
for i in range(N):
    u = int(S[N-i-1])
    U.append(u)
    
npow = 1
T = [0]
now = 0
for i in range(N):
    now += U[i]*npow
    now %= P
    T.append(now)
    npow*=10
    npow%=P
    
pmod = [0]*P
for t in T:
    pmod[t]+=1
    
ans = 0
for p in pmod:
    ans += (p*(p-1))//2
    
print(ans)

Submission status: Wrong Answer

Solution code:
n,y = map(int, input().split())
a=[0]*y
k=1
r=p=0
for c in input()[::-1]:
    a[p]+=1
    p-=int(c)*k
    p%=y
    r+=a[p]
    k*=10
    k%=y
print(r)

Submission status: Wrong Answer

Solution code:
from collections import *
n, p = map(int, input().split())
s = list(map(int, input()))
if p%10==0:
    r = 0
    for i in range(n):
        if s[i]%p==0:
            r += i+1
    print(r)
    exit()
c = Counter()
c[0] += 1
v = r = 0
k = 1
for i in s[::-1]:
    v += int(i)*k
    v %= p
    r += c[v]
    c[v] += 1
    k *= 10
    k %= p
print(r)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
def input():return sys.stdin.readline().strip()

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

    ans = 0
    if P in [2, 5]:
        for i, c in enumerate(S):
            if int(c) % P == 0:
                ans += N-i
    else:
        d = defaultdict(int)
        d[0] = 1
        num = 0
        ten = 1
        for c in S[::-1]:
            num += int(c) * ten
            num %= P
            d[num] += 1
            ten *= 10
            ten %= P

        ans = sum([d[i]*(d[i]-1)//2 for i in range(P)])
        
    print(ans)

        
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import collections
n,p = map(int,input().split())
s=input()
arr=[int(s[i]) for i in range(n)] #文字列の各文字をそれぞれ数字に変換しておく
dic=collections.defaultdict(int)
tmp=0
for i in range(n-1,-1,-1): #右端の要素を右端とする連続部分列のあまりを順に求める
  tmp+=arr[i]*pow(10,n-1-i,p)
  tmp%=p
  dic[tmp]+=1
ans=0
rem=0 #調べるあまりの値(初期値は0)
for i in range(n-1,-1,-1):
  ans+=dic[rem]
  rem+=arr[i]*pow(10,n-1-i,p) #調べるあまりの値に(i番目の要素)*10^(n-1-i)を加える
  rem%=p
  dic[rem]-=1 #右端の要素が右端、i番目の要素が左端となる連続部分列のあまりの個数を1減らす
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
n,p = map(int,input().split())
s=input()
arr=[int(s[i]) for i in range(len(s))] #文字列の各文字をそれぞれ数字に変換しておく
dic=collections.defaultdict(int)
tmp=0
for i in range(n-1,-1,-1): #右端の要素を右端とする連続部分列のあまりを順に求める
  tmp+=arr[i]*pow(10,n-1-i,p)
  tmp%=p
  dic[tmp]+=1
ans=0
rem=0 #調べるあまりの値(初期値は0)
for i in range(n-1,-1,-1):
  ans+=dic[rem]
  rem+=arr[i]*pow(10,n-1-i,p) #調べるあまりの値に(i番目の要素)*10^(n-1-i)を加える
  rem%=p
  dic[rem]-=1 #右端の要素が右端、i番目の要素が左端となる連続部分列のあまりの個数を1減らす
print(ans)

Submission status: Wrong Answer

Solution code:
N,P = map(int,input().split())
S=input()
mem_mod = [0 for i in range(0,P,1)]
counter = 0
S_num = list(map(int, S))
tmp=10

for i in range(1,N,1):
    S_num[N-i-1] = S_num[N-i] + S_num[N-i-1]*pow(10,i,P)

for i in range(0,N,1):
    X = S_num[N-i-1] % P
    if X==0:
        counter+=1
    counter += mem_mod[X]
    mem_mod[X] += 1
print(counter)

Submission status: Wrong Answer

Solution code:
import sys

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

ans = 0

if P == 2:
    for a in A:
        if int(a) % 2 == 0:
            ans += 1
    print(ans * (ans + 1) // 2)
    sys.exit()
elif P == 5:
    for a in A:
        if a == "5" or a == "0":
            ans += 1
    print(ans * (ans + 1) // 2)
    sys.exit()


A = "0" + A

S = [0] * len(A)
cnt = [0] * P
cnt[0] = 1

for i in range(len(A) - 1):
    S[i + 1] = (S[i] + int(A[i + 1]) * pow(10, i, P)) % P
    cnt[S[i + 1] % P] += 1
# print(S, cnt)

# ans = cnt[0] * (cnt[0] - 1) // 2
for c in cnt:
    ans += c * (c - 1) // 2
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
#import queue
from copy import copy, deepcopy
from operator import itemgetter

import bisect#2分探索
#bisect_left(l,x), bisect(l,x)
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
#dequeを使うときはpython3を使う、pypyはダメ
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#q=heapq.heapify(l),heappush(q,a),heappop(q)

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s): return sorted(range(len(s)), key=lambda k: s[k])

#mod = 10**9+7

#N = int(input())
N, P = map(int, input().split())
S=input()
#L = [int(input()) for i in range(N)]
#A = list(map(int, input().split()))
#S = [inputl() for i in range(H)]
#q = queue.Queue() #q.put(i) #q.get() 
#q = queue.LifoQueue() #q.put(i) #q.get() 

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b=copy.deepcopy(a)  #2次元配列はこうコピーする
#w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

#素数リスト
# n = 100
# primes = set(range(2, n+1))
# for i in range(2, int(n**0.5+1)):
#     primes.difference_update(range(i*2, n+1, i))
# primes=list(primes)

#bisect.bisect_left(a, 4)#aはソート済みである必要あり。aの中から4未満の位置を返す。rightだと以下
#bisect.insort_left(a, 4)#挿入
if P!=2 and P!=5:
    pc=[0]*P
    pc[0]=1
    count=0
    ans=0
    p10=1
    for i in range(1,N+1):
        count+=int(S[N-i])
        count%=P
        ans+=pc[count]
        pc[count]+=1
        p10*=10
        p10%=P

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

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=[int(j) for j in input()][::-1]

if p==2:
    ans=0
    for i,j in enumerate(s):
        if j%2==0:
            ans+=(n-i)
    print(ans)
    exit()
if p==5:
    ans=0
    for i,j in enumerate(s):
        if j%5==0:
            ans+=(n-i)
    print(ans)
    exit()

c=[0]*p
tmp=0
c[0]+=1
t=1
import numpy as np
for i in s:
    tmp+=t*i
    print(tmp)
    c[tmp%p]+=1
    t=(t*10)%p
c=np.array(c)
print(c)
ans=c*(c-1)//2
print(ans.sum())

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
#import queue
from copy import copy, deepcopy
from operator import itemgetter

import bisect#2分探索
#bisect_left(l,x), bisect(l,x)
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
#dequeを使うときはpython3を使う、pypyはダメ
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#q=heapq.heapify(l),heappush(q,a),heappop(q)

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s): return sorted(range(len(s)), key=lambda k: s[k])

#mod = 10**9+7

#N = int(input())
N, P = map(int, input().split())
S=input()
#L = [int(input()) for i in range(N)]
#A = list(map(int, input().split()))
#S = [inputl() for i in range(H)]
#q = queue.Queue() #q.put(i) #q.get() 
#q = queue.LifoQueue() #q.put(i) #q.get() 

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b=copy.deepcopy(a)  #2次元配列はこうコピーする
#w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

#素数リスト
# n = 100
# primes = set(range(2, n+1))
# for i in range(2, int(n**0.5+1)):
#     primes.difference_update(range(i*2, n+1, i))
# primes=list(primes)

#bisect.bisect_left(a, 4)#aはソート済みである必要あり。aの中から4未満の位置を返す。rightだと以下
#bisect.insort_left(a, 4)#挿入

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

pc=[0]*P
ans=0
for p in l:  
    ans+=pc[p]
    pc[p]+=1
print(ans)

Submission status: Wrong Answer

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

count = 0
pval = [0]*10000

waru = 10
for i in range(n):
    tmp = (s%waru) % p
    if(tmp == 0):
        count = count +1
    count = count + pval[tmp]
    pval[tmp] = pval[tmp] + 1
    waru = waru * 10

print(count)

Submission status: Wrong Answer

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

count = 0
pval = [0]*10000

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

print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, P = map(int, input().split())
S = input()[::-1]
A = [0]
num = 0
d = 0
ans = 0
if 10 % P == 0:
    ans = 0
    for r in range(N):
        if int(S[r]) % P == 0:
            ans += r + 1
    print(ans)
else:
    for i in range(N):
        num += int(S[i]) * pow(10, i, P)
        num %= P
        A.append(num)
    A_ = Counter(A)
    for i in A_.values():
        ans += i * (i-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]
num = 0
d = 0
ans = 0
for i in range(N):
    num += int(S[i]) * pow(10, d, P)
    num %= P
    A.append(num)
    d += 1
A_ = Counter(A)
for i in A_.values():
    ans += i * (i-1) // 2
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def main():
    n, p = map(int, input().split())
    s = list(input())
    if 10 % p == 0:
        ans = 0
        for i in range(n):
            if (ord(s[i])-ord('0')) % p == 0:
                ans += i+1
        print(ans)
        return

    d = [0] * (n+1)
    ten = 1
    for i in reversed(range(n)):
        a = (ord(s[i])-ord('0')) * ten % p
        if i == 0:
            d[i] = a % p
        else:
            d[i] = (d[i+1]+a) % p
        ten *= 10
        ten %= p

    cnt = [0] * p
    ans = 0
    for i in reversed(range(n+1)):
        ans += cnt[d[i]]
        cnt[d[i]] += 1
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=input()
b=1
d=0
l=[0]*p
l[0]=1
ans=0
for c in s[::-1]:
  if p==2 or p==5:
    if int(c)%p==0:
      ans+=1
  else:
    d+=int(c)*b
    d%=p
    l[d]+=1
    b*=10
    b%=p
if p==2 or p==5:
  ans=ans*(ans+1)//2
else:
  for i in l:
    ans+=i*(i-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=input()
b=1
d=0
l=[0]*p
ans=0
for c in s[::-1]:
  if p==2 or p==5:
    if int(c)%p==0:
      ans+=1
  else:
    d+=int(c)*b
    d%=p
    l[d]+=1
    b*=10
    b%=p
if p==2 or p==5:
  ans=ans*(ans+1)//2
else:
  for i in l:
    ans+=i*(i-1)//2
print(ans+l[0])

Submission status: Wrong Answer

Solution code:
def main():
    n,p = map(int,input().split())
    s = input()
    dp = [0 for _ in range(p)]
    dp[0] += 1
    x = 0
    for i in range(n):
        x = (x+int(s[n-1-i])*pow(10,i,p))%p
        dp[x] += 1
    ans = 0
    for i in range(p):
        ans += (dp[i]*(dp[i]-1))//2
    print(ans)
 
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=input()
r=set()
last=0
d={0:0}
total=0
rem=0
if p==2:
  for i in range(0,len(s)):
    if int(s[i])%2==0:
      total+=i+1
  print(total)
elif p==5:
  for i in range(0,len(s)):
    if int(s[i])%5==0:
      total+=i+1
  print(total)
  
  
    
else:
  power=1
  for i in range(len(s)-1,-1,-1):#handling of 0's as n and rem
    n=int(s[i])*power+rem
    power*=10
    power=power%p
    rem=n%p
    if rem in d.keys():
        d[rem]+=1
    else:
        d[rem]=1
    total+=d[rem]-1
print(total+d[0])

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=[int(j) for j in input()][::-1]
c=[0]*p
tmp=0
c[0]+=1
t=1
import numpy as np
for i in s:
    tmp+=t*i
    c[tmp%p]+=1
    t=(t*10)%p
c=np.array(c)
ans=c*(c-1)//2
print(ans.sum())

Submission status: Wrong Answer

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

l = len(S)
if P == 2:
    ans = 0
    for i in range(l):
        if int(S[i])%2 == 0:
            ans += i+1
elif P == 5:
    ans = 0
    for i in range(l):
        if int(S[i])%2 == 0:
            ans += i+1
else:
    data = [0]*P
    for i in range(l-1, -1, -1):
        data[int(S[i:l])%P] += 1
    ans = data[0]
    for item in data:
        if item > 1:
            ans += item*(item-1)//2

print(ans)

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
s=[int(j) for j in input()][::-1]
c=[0]*p
tmp=0
c[0]+=1
t=1
import numpy as np
for i in s:
    tmp+=t*i
    c[tmp%p]+=1
    t=t*10%p
c=np.array(c)
ans=c*(c-1)//2
print(ans.sum())

Submission status: Wrong Answer

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

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

else:
    X = [0]
    for i, s in enumerate(S[::-1]):
        X.append((X[-1] + pow(10, i, P) * int(s)) % P)

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

Submission status: Wrong Answer

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

X = [0]
for i, s in enumerate(S[::-1]):
    X.append((X[-1] + pow(10, i, P) * int(s)) % P)


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

Submission status: Wrong Answer

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

if p == 2 or p == 5:
    res = 0
    for i in range(n):
        if int(s[i]) % p == 0:
            res += i + 1
    print(res)
else:
    cnt = {0: 1}
    now = 0
    d = 1
    for i in range(n):
        now = (now + (10 * d) * int(s[i])) % p
        cnt[now] = cnt.get(now, 0) + 1
        d = (d * 10) % p
    print(sum(cnt[k] * (cnt[k] - 1) // 2 for k in cnt))

Submission status: Wrong Answer

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

res = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            res += i + 1
else:
    cnt = {0: 1}
    now = 0
    d = 1
    for i in range(n):
        now = (now + int(s[i]) * d) % p
        res += cnt.get(now, 0)
        d = (d * 10) % p
        cnt[now] = cnt.get(now, 0) + 1

print(res)

Submission status: Wrong Answer

Solution code:
import collections
N, P = map(int,input().split())
S = input()
mod = P
div = [0]*(N+1)
for i in range(N):
    div[i+1] = (div[i] + int(S[N-1-i])*pow(10,i,mod))%mod
d = collections.Counter(div[1::])
ans = d[0]
for i in d.values():
    ans += i*(i-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s=input()[::-1]
l=[0]*m
a,t,p=0,0,1
if 10%m:
  for i in s: l[t%m]+=1; t+=int(i)*p; a+=l[t%m]; p=p*10%m
else:
  a=sum(i+1 for i in range(n) if int(s[i])%m<1)
print(a)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s=input()[::-1]
a=t=0
if 10%m<1:
  for i in s:
    if int(i)%m<1: t+=1; a+=t
  print(a); exit()
l=[0]*m
p=1
for i in s: l[t%m]+=1; t+=int(i)*p; a+=l[t%m]; p=p*10%m
print(a)

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = input()
now = 0
hyou = [0] * P
hyou[0] = 1
cnt = 1
ans = 0

if P == 2 or P == 5:
    for t in S[::-1]:
        temp = int(t)
        if temp % P == 0:
            ans += cnt
            cnt += 1
    print(ans)
    exit()

for i, t in enumerate(S[::-1]):
    now = (now + int(t) * pow(10, i, P)) % P
    ans += hyou[now]
    hyou[now] += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = input()
now = 0
hyou = [0] * P
hyou[0] = 1
ans = 0

for i, t in enumerate(S[::-1]):
    now = (now + int(t) * pow(10, i, P)) % P
    ans += hyou[now]
    hyou[now] += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N,K=map(int,input().split())
L=list(input())
t=1
N=0
Hash=defaultdict(lambda:0)
Hash[0]=1
for i in (L[::-1]):
    N=(N+int(i)*t)%K
    Hash[N]+=1
    t=(t*10)%K
ans=0
for i in Hash.values():
    ans+=i*(i-1)//2
print(ans)