Problem:


Score : 500 points

Problem Statement

Takahashi has a string S of length N consisting of digits from 0 through 9.

He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S - there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.

Here substrings starting with a 0 also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.

Compute this count to help Takahashi.

Constraints

1 \leq N \leq 2 \times 10^5

S consists of digits.

|S| = N

2 \leq P \leq 10000

P is a prime number.

Input

Input is given from Standard Input in the following format:

N P
S

Output

Print the number of non-empty (contiguous) substrings of S that are divisible by P when regarded as an integer written in base ten.

Sample Input 1

4 3
3543

Sample Output 1

6

Here S = 3543. There are ten non-empty (contiguous) substrings of S:

3: divisible by 3.

35: not divisible by 3.

354: divisible by 3.

3543: divisible by 3.

5: not divisible by 3.

54: divisible by 3.

543: divisible by 3.

4: not divisible by 3.

43: not divisible by 3.

3: divisible by 3.

Six of these are divisible by 3, so print 6.

Sample Input 2

4 2
2020

Sample Output 2

10

Here S = 2020. There are ten non-empty (contiguous) substrings of S, all of which are divisible by 2, so print 10.

Note that substrings beginning with a 0 also count.

Sample Input 3

20 11
33883322005544116655

Sample Output 3

68



Sample input:
4 3
3543


Sample output:
6

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = input()
memo = 0
pre = 0
ans = 0

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

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

Submission status: Wrong Answer

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


memo = {}
ans = 0
rot = 0
for i in range(n):
    rot = (rot * 10 + int(s[i])) % p
    
    if (int(s[i]) - rot) % p not in memo:
        memo[(int(s[i]) - rot) % p] = 1
    else:
        memo[(int(s[i]) - rot) % p] += 1
    if rot in memo:
        ans += memo[rot]

print(ans)

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
l=list(input())
for i in range(n):
    l[i]=int(l[i])
w=0
wl=[]
po=pow(10,p-2,p)
for i in range(n):
    wl.append(w)
    #if w==0:
        #ans+=rr[n-1-i]
    w-=l[n-1-i]
    w*=po
    w%=p
wl.reverse()
r=[]
rt=0
for i in range(n):
    rt+=l[n-1-i]*(10**i)
    r.append(rt%p)
r.reverse()
d=[0]*p
ans=0
for i in range(n):
    d[r[i]]+=1
    ans+=d[wl[i]]  
print(ans)

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = input()
numMultiples = 0
seenRemainders = [[] for _ in range(N)]
for i in range(N):
    remainder = 0
    prefixesFound = 0
    for j in range(i, N):
        remainder = (10 * remainder + int(S[j])) % P
        if remainder in seenRemainders[j]:
            break
        seenRemainders[j].append(remainder)
        if remainder == 0:
            prefixesFound += 1
    numMultiples += prefixesFound * (prefixesFound + 1) / 2
print(int(numMultiples))

Submission status: Wrong Answer

Solution code:
N, P = [int(i) for i in input().split()]

S = input()

ans = [0 for i in range(N)]

def solve(n):
    if n==N:
        return 0
    else:
        for i in range(n+1, N+1):
            num = int(S[n:i])
            ##print(num, n, i)
            if num%P == 0 :
                ans[n] =1+solve(i) 
                return ans[n]
        return 0
##print(solve(0))
print(sum(ans))

Submission status: Wrong Answer

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
n,k  = map(int,input().split())
st = input()
numMultiples = 0
seenRemainders = []
for i in range(n):
    seenRemainders.append([])
#print(seenRemainders)
for i in range(n):
    remainder = 0
    prefixesFound = 0
    for j in range(i,n):
        remainder = (10 * remainder + int(st[j])) % k
        if remainder in seenRemainders[j]:
            break
        seenRemainders[j].append(remainder)
        if remainder == 0:
            prefixesFound+=1
    numMultiples += prefixesFound * (prefixesFound + 1) // 2
print(numMultiples)

Submission status: Wrong Answer

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

dp = [0] * P
dp[0] = 1

ans = 0
now = 0
for i, s in enumerate(map(int, S)):
    now = (s * pow(10, i, P) + now) % P
    ans += dp[now]
    dp[now] += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
l=list(input())
for i in range(n):
    l[i]=int(l[i])
w=0
wl=[]
po=pow(10,p-2,p)
for i in range(n):
    wl.append(w)
    #if w==0:
        #ans+=rr[n-1-i]
    w-=l[n-1-i]
    w*=po
    w%=p
wl.reverse()
r=[]
rt=0
for i in range(n):
    rt+=l[n-1-i]*(10**i)
    r.append(rt%p)
r.reverse()
d={}
ans=0
for i in range(n):
    if r[i] in d:
        d[r[i]]+=1
    else:
        d[r[i]]=1
    if wl[i] in d:
        ans+=d[wl[i]]  
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

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

acc = [0] * N
cur = S[-1] % P
acc[-1] = cur
k = 1
for i in range(N-2, -1, -1):
    cur += 10**k * S[i]
    cur %= P
    acc[i] = cur
    k += 1
acc = [0] + acc

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

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

N, P = lr()
S = sr()
# 累積和
remain = [0] * N
cur = 0
for i in range(N):
    num = 10 * cur + int(S[i])
    cur = num % P
    remain[i] = cur

counter = Counter(remain)
answer = 0
for k, v in counter.items():
    if k == 0:
        answer += v * (v+1) // 2
    elif v == 1:
        continue
    else:
        answer += v * (v-1) // 2

print(answer)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, p = LI()
D = defaultdict(int)
D[0] += 1
s = S()
ans = 0
rem = 0
k = 1
for i in range(n - 1, -1, -1):
    d = s[i]
    rem = (pow(10, n - i - 1, p) * int(d) + rem) % p
    k = k * 10 % p
    ans += D[rem]
    D[rem] += 1


print(ans)

Submission status: Wrong Answer

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

dec = [1] * n
for i in range(1,n):
    dec[i] = (dec[i - 1] * 10) % p
s_mod = [0] * n
for i in range(n):
    s_mod[i] = (int(s[i]) * dec[i]) % p
    
#print(dec)
#print(s_mod)
    
cumsum = [0] * (n + 1)
cnt = [1] + [0] * (p - 1)
for i in range(n):
    cumsum[i + 1] = (cumsum[i] +  s_mod[i]) % p
    cnt[cumsum[i + 1]] += 1
#print(cumsum)
#print(cnt)
    
ans = 0
for i in range(p):
    ans += (cnt[i] * (cnt[i] - 1)) // 2
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

mem = defaultdict(int)
mem[0] += 1
T = [0]
dec = 1
x = 0
for s in S[::-1] :
  s = int(s)
  x = (dec * s + x) % P
  dec = dec * 10 % P
  T.append(x)
  mem[x] += 1

inv = pow(10, P - 2, P)
dec = 1
ret = 0
for i, t in enumerate(T) :
  if dec == 0 :
    ret += len(T) - i - 1
  else :
    ret += mem[t] - 1
  mem[t] -= 1
  dec = dec * inv % P
  
print(ret)

Submission status: Wrong Answer

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

print(n)

Submission status: Wrong Answer

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

dec = [1] * n
for i in range(1,n):
    dec[i] = (dec[i - 1] * 10) % p
s_mod = [0] * n
for i in range(n):
    s_mod[i] = (int(s[i]) * dec[i]) % p
    
print(dec)
print(s_mod)
    
cumsum = [0] * (n + 1)
cnt = [1] + [0] * (p - 1)
for i in range(n):
    cumsum[i + 1] = (cumsum[i] +  s_mod[i]) % p
    cnt[cumsum[i + 1]] += 1
print(cumsum)
print(cnt)
    
ans = 0
for i in range(p):
    ans += (cnt[i] * (cnt[i] - 1)) // 2
print(ans)

Submission status: Wrong Answer

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

s = input()

rem = [0]
currRem = 0
ans = 0

for ch in s:
    currRem *= 10
    currRem += (ord(ch) - ord('0'))
    currRem %= p
    rem.append(currRem)

rem.sort()
rem.append(-1)

currEqCnt = 1
for i in range(1, len(rem)):
    if (rem[i] == rem[i - 1]):
        currEqCnt += 1
    else:
        ans += (currEqCnt) * (currEqCnt - 1) // 2
        currEqCnt = 1

print(ans)

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = input()
count = 0
reversed(S)
tmp = 0

for i in range(N):
    for j in range(i+1, N+1):
        pass
print(count)

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = list(reversed(list(map(int, input()))))
if p == 2:
    ans = 0
    s = list(reversed(s))
    for i in range(n):
        if s[i] % 2 == 0:
            ans += i + 1
    print(ans)
    exit()
if p == 5:
    ans = 0
    s = list(reversed(s))
    for i in range(n):
        if s[i] % 5 == 0:
            ans += i + 1
    print(ans)
    exit()
cur = 1
c = [0] * (n + 1)
ans = 0
t = [0] * p
t[c[0]] += 1
for i in range(n):
    c[i + 1] = (c[i] + cur * s[i]) % p
    ans += t[c[i + 1]]
    print(t, c, ans)
    t[c[i + 1]] += 1
    cur = cur * 10 % p
print(ans)

Submission status: Wrong Answer

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

def keychange(dic,x):
    newdic = {}
    for k in dic:
        b = (k*10 + x) % p
        newdic[b] = dic[k]
    return newdic
dic = {}
count = 0
for i in range(n):
    print(dic)
    x = s[i] % p
    dic = keychange(dic,x)
    print(dic)
    if x in dic:
        dic[x] += 1
    else:
        dic[x] = 1
    if 0 in dic:
        count += dic[0]
print(count)

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
num = input().strip()
dp = [0] * P
ans = 0
last = 0
for i in range(N):
    last = (10 * last + int(num[i])) % P
    if last == 0:
        ans += 1 + dp[last]
    else:
        ans += dp[last]
    dp[last] += 1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

result = 0
tc = [0] * n
tims = []
pl = len(str(p))
for k in range(len(s)):
    i = s[k]
    key = i % p
    if key == 0:
        result += 1
        tci = 0
        if k != 0:
            tci = tc[k-1]
        result += tci
        tc[k] = tci+1
        tims =[]
    else:
        total = i
        tims.append(i)
        if pl > len(tims):
            continue
        for j in range(len(tims)-1)[::-1]:
            total = total * 10
            total += tims[j]
            if total % p == 0:
                result +=1
                tca = k - (len(tims)-1-j)
                tci = 0
                if tca != 0:
                    tci = tc[tca-1]
                result += tci
                tc[k] = tci+1
                #tims = tims[j+1: len(tims)]
                break
print(result)

Submission status: Wrong Answer

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

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

ans = 0
if 0 in a:
    ans += a.count(0)
    ans += ans * (ans - 1) // 2
sa = set(a) - {0}
for x in sa:
    acx = a.count(x)
    ans += acx * (acx-1) // 2 
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

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

N, P = lr()
S = sr()
# 累積和
remain = [0] * N
for i in range(N):
    num = S[:i+1]
    num = int(num)
    remain[i] = num % P

counter = Counter(remain)
answer = 0
for k, v in counter.items():
    if k == 0:
        answer += v * (v+1) // 2
    else:
        answer += v * (v-1) // 2

print(answer)

Submission status: Wrong Answer

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

print(n)

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,p = get_nums_l()
s = input()

mods = [0] * n

for i,c in enumerate(reversed(s)):
    mods[i] = pow(10,i,p) * int(c) % p
mods.reverse()
ruiseki = [0] * (n+1)

counts = [0] * p

for i,m in enumerate(mods):
    ruiseki[i+1] = (ruiseki[i] + m) % p

for x in ruiseki:
    counts[x] += 1

ans = 0
for i in range(p):
    num = counts[i]
    ans += num*(num-1)//2

# log(mods)
# log(ruiseki)

# ruiseki2 = list(sorted(ruiseki))
# ruiseki2.append(999999999999999)

# prev = ruiseki2[0]
# prev_i = 0

# # log(ruiseki2)

# ans = 0

# for i,r in enumerate(ruiseki2):
#     if i==0:
#         continue
#     if r != prev:
#         l = i-prev_i
#         # log(i,r,l)
#         ans += l*(l-1)//2
#         prev = r
#         prev_i = i
    # log(i, r, ans)

# for m in mods:
#     if m == 0:
#         ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, p = LI()
D = defaultdict(int)
D[0] += 1
s = S()
ans = 0
rem = 0
k = 1
for i in range(n - 1, -1, -1):
    d = s[i]
    rem = (k * int(d) + rem) % p
    k = k * 10 % p
    ans += D[rem]
    D[rem] += 1


print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, p = LI()
D = defaultdict(int)
D[0] += 1
s = S()
ans = 0
rem = 0
k = 1
for i in range(n - 1, -1, -1):
    d = s[i]
    rem = (k * int(d) + rem) % p
    k *= 10 % p
    ans += D[rem]
    D[rem] += 1


print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def ext_gcd(a, b, x, y):
    if b == 0:
        x[0] = 1
        y[0] = 0
        return a
    
    d = ext_gcd(b, a % b, y, x)
    y[0] -= a // b * x[0]

    return d

def get_inv(n, p):
    x = [1]
    y = [1]
    ext_gcd(n, p, x, y)
    return x[0] % p

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

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

ls = [0]
p10 = [1]

for i in range(n):
    ls.append((ls[i] * 10 + s[i]) % p)
    p10.append(p10[i] * 10 % p)

mp = [0 for i in range(p)]
ans = 0

if p == 2:
    for i in range(n):
        if s[i] == 0:
            ans += i + 1
else:
    for i in range(n + 1):
        tmp = get_inv(p10[i], p)
        ans += mp[ls[i] * tmp % p]
        mp[ls[i] * tmp % p] += 1

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

start_idx = 0
mod_count = [0]*P
dp = [0] * (N+1)
digit = 1
for i, s in enumerate(S, 1):
  s = int(s)
  p = digit*s % P
  start_idx = (start_idx + P - p) % P
  dp[i] = dp[i-1] + mod_count[start_idx]
  if p == 0:
    dp[i] += 1

  digit = (digit * 10) % P
  mod_count[(start_idx + p)%P] += 1

print(dp[-1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import math
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#############
# Main Code #
#############

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

mods = []
count = 0

for digit in S:
  print(digit)
  mods.append(int(digit))
  if int(digit)%P == 0:
    count += 1
  if len(mods) > 1:
    for i in range(len(mods)-1):
      mods[i] = (mods[i]*10 + int(digit)) % P
      if mods[i] == 0:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import sys, collections
range = xrange
input = raw_input

n, p = [int(x) for x in input().split()]
A = [ord(x) - 48 for x in input()]


if p == 5:
    ans = 0
    for i in range(n):
        if A[i] == 0 or A[i] == 5:
            ans += i + 1
    print ans
    sys.exit()


DP = [0]*p
ans = 0
POW = 1
ind0 = 0
for a in reversed(A):
    DP[ind0] += 1
    #DP = [DP[(a * POW + i) % p] for i in range(p)]
    ind0 = (a * POW + ind0) % p
    ans += DP[ind0]
    POW = POW * 10 % p
print ans

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**9)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,p = na()
s = ns()
s = list(s)
ans = 0

seenRemainders = [[] for k in range(n)] #長さn
for i in range(n):
    remainder = 0
    prefixesFound = 0
    for j in range(i,n):
        remainder = (10 * remainder + int(s[j])) % p
        if remainder in seenRemainders[j]:
            break
        seenRemainders[j].append(remainder)
        if remainder == 0:
            prefixesFound+=1
    ans += prefixesFound * (prefixesFound + 1) // 2

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

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

N, P = lr()
S = list(sr())
# 累積和
remain = [0] * N
for i in range(N):
    num = ''.join(S[:i+1])
    num = int(num)
    remain[i] = num % P

counter = Counter(remain)
answer = 0
for k, v in counter.items():
    if k == 0:
        answer += v * (v+1) // 2
    else:
        answer += v * (v-1) // 2

print(answer)

Submission status: Wrong Answer

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

dp = [0] * P

ans = 0
now = 0
d = 1
for s in map(int , S):
    now = (now + s * d) % P
    dp[now] += 1
    ans += dp[(P - now) % P]
    d = d * 10 % P

print(ans)

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = [int(s) for s in input()]
dp = [[-1 for _ in range(N)] for _ in range(N)]
dp[N - 1][N - 1] = S[N - 1] % P

for r in range(N - 1, -1, -1):
    for l in range(r, -1, -1):
        if r == l:
            dp[l][r] = (S[l] * (10 ** (N-l-1))) % P
        else:
            dp[l][r] = (S[l] * (10 ** (N-l-1)) + dp[l+1][r]) % P

ans = 0
for r in range(N - 1, -1, -1):
    for l in range(r, -1, -1):
        if dp[l][r] == 0:
            ans += 1
print(ans)

Submission status: Wrong Answer

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

L = []

for i in range(N):
    for j in range(i+1, N+1):
        if int(S[i:j])%P == 0:
            L.append([i, j])
            break

res = 0


while True:
    cnt = 0
    last = -1
    for i in range(len(L)):
        l = L[i]
        if l == 0:
            continue
        if last == -1 or last == l[0]:
            last = l[1]
            L[i] = 0
            cnt += 1
        elif l[0] > last:
            break
    else:
        if cnt == 0:
            break

    res += cnt * (cnt+1)//2

print(res)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from collections import Counter

N, P = map(int, input().split())
S = list(map(int, list(input())))
s = []
t = 1
for i in S[::-1]:
    r = i % P
    s.append(r * t % P)
    t = t * 10 % P

s = list(accumulate([0] + s))
s = [i % P for i in s]
c = Counter(s)
answer = 0
for i in c.values():
    answer += i * (i - 1) // 2

print(answer)

Submission status: Wrong Answer

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


def solve(N: int, P: int, S: int):
    M10K = (10**(P-2))%P
    arr = [int(S[i])%P for i in range(len(S))]
    sum = 0
    for i in range(N):
        sDiv = 0
        coeff = 1
        for j in range(i,N):
            sDiv= (sDiv*coeff + arr[j])%P
            coeff*=10
            if sDiv == 0:
                sum+=1
    print(sum)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = next(tokens)  # type: int
    solve(N, P, S)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
i=list(map(int, input().split()))
s=input()
n=i[0]
p=i[1]
l=[]
y=0
for j in range(0,n):
    for k in range (j,n):
        z=int(s[j:k+1])
        l.append(z//p)
for x in range (0,n*(n+1)//2):
    if l[x]==0:
        y=y+1
print (y)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, p = LI()
D = defaultdict(int)
D[0] += 1
D2 = {}

s = S()
ans = 0
rem = 0
for i in range(n - 1, -1, -1):
    d = s[i]
    rem = (pow(10, i, p) * int(d) + rem) % p
    D2[i] = rem
    ans += D[rem]
    D[rem] += 1


print(ans)

Submission status: Wrong Answer

Solution code:
a, b = [int(c) for c in input().split(" ")]
S = input()
count = 0
for i in range(1, a):
  for j in range(0, a):
      if (j+i <= a+1):
        if (int(S[j:j+i]) % b == 0):
            count+=1
print(count)

Submission status: Wrong Answer

Solution code:
def ext_gcd(a, b, x, y):
    if b == 0:
        x[0] = 1
        y[0] = 0
        return a
    
    d = ext_gcd(b, a % b, y, x)
    y[0] -= a // b * x[0]

    return d

def get_inv(n, p):
    x = [1]
    y = [1]
    ext_gcd(n, p, x, y)
    return x[0] % p

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

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

ls = [0]
p10 = [1]

for i in range(n):
    ls.append((ls[i] * 10 + s[i]) % p)
    p10.append(p10[i] * 10 % p)

mp = [0 for i in range(p)]
ans = 0

for i in range(n + 1):
    tmp = 0
    if p != 2:
        tmp = get_inv(p10[i], p)
    ans += mp[ls[i] * tmp % p]
    mp[ls[i] * tmp % p] += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
N,P=[int(i) for i in input().split(" ")]
S=input()

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

mods=[]
S+='0'
for i in range(len(S)):
    mods.append((int(S)%(10**i))%P)

c=Counter(mods)

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

Submission status: Wrong Answer

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

R = [None]*N
k = 1
for i in range(N-1, -1, -1):
    R[i] = S[i]*k%P
    k = k*10%P

ans = 0
X = []
x = 0
for r in R:
    x  = (x+r)%P
    X.append(x)

D = [0]*P
D[0] = 1
for x in X:
    ans += D[x]
    D[x]+=1

print(ans)