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: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

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

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

print(ans)

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
s=input()
ans=0
if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            ans+=i+1
    print(ans)
elif p==5:
    for i in range(n):
        if int(s[i])%5==0:
            ans+=i+1
    print(ans)
else:
    s=s[::-1]
    accum=[0]*n
    d=dict()
    for i in range(n):
        accum[i]=int(s[i])*pow(10,i,p)%p
    for i in range(n-1):
        accum[i+1]+=accum[i]
        accum[i+1]%=p
    accum[-1]%=p
    #print(accum)
    for i in range(n):
        if accum[i] not in d:
            if accum[i]==0:
                ans+=1
            d[accum[i]]=1
        else:
            if accum[i]==0:
              ans+=1
            ans+=d[accum[i]]
            d[accum[i]]+=1
    #print(d)
    print(ans)

Submission status: Accepted

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




digit_rm = [0 for _ in range(n)]
for i in range(n):
	digit_rm[i] = (int(s[n-1-i]) * pow(10, i, p) ) % p

remain = [0 for _ in range(n)]
for i in range(n):
	if i == 0:
		remain[i] = digit_rm[i]
	else:
		remain[i] = (remain[i-1] + digit_rm[i]) % p

pcnt = [0 for _ in range(p)]

for i in remain:
	pcnt[i] += 1

if 10 % p == 0:
	ans = 0
	for i in range(n):
		if int(s[n-1-i]) % p == 0:
			ans += n - i
	print(ans)
else:
	ans = pcnt[0]
	for num in pcnt:
		if num != 0:
			ans += num * (num - 1) // 2

	print(ans)

Submission status: Accepted

Solution code:
import sys
#input = sys.stdin.buffer.readline
from collections import Counter

def main():
    N,P = map(int,input().split())
    S = input()
    
    if 10%P == 0:
        ans = 0
        for i,st in enumerate(S[::-1]):
            num = int(st)
            if num % P == 0:
                ans += N-i
    else:
        ans,base = 0,1
        MOD_list = [0]
        for st in S[::-1]:
            num = int(st)
            MOD = (MOD_list[-1]+num*base)%P
            MOD_list.append(MOD)
            base *= 10
            base %= P
        c = Counter(MOD_list)
        for v in c.values():
            ans += (v*(v-1))//2
        
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter

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

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

m = []
t = 1
q = 0
for i in range(N,0,-1):
    q = ((int(S[i-1]) % P) * t + q) % P
    m.append(q)
    t = (10 * t) % P
    
mc = Counter(m)

for v in mc.values():
    if v > 1:
        sum += v*(v-1)//2

sum += mc[0]

print(sum)

Submission status: Accepted

Solution code:
# coding: utf-8

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

#N=200000
#P=9893
#S= '0'+'1234567890' * 20000

if (P==2)|(P==5):
    sum=0
    for i in range(N, 0, -1):
        if int(S[i]) % P == 0:
            sum+= i
    print(sum)


else:
    dp1 = [0] * (N+1)
    dp2 = [0] * (N+1)
    dp3 = [0] * P
    dp1[N] = int(S[N]) % P
    dp3[int(dp1[N])] += 1
    k = 1
    for i in range(N - 1, 0, -1):
        dp1[i] = (dp1[i + 1] + (int(S[i]) * 10 * k)) % P
        dp3[int(dp1[i])] += 1
        k = (k * 10) % P

    sum = 0

    for i in range(P):
        if i == 0:
            sum += (dp3[i] * (dp3[i] - 1)) // 2 + dp3[i]
            continue
        if dp3[i] == 0: continue
        sum += (dp3[i] * (dp3[i] - 1)) // 2
    print(int(sum))

Submission status: Accepted

Solution code:
# coding: utf-8
import numpy as np
N,P = list(map(int, input().split()))
S = '0'+input()

#N=200000
#P=9893
#S= '0'+'1234567890' * 20000

if (P==2)|(P==5):
    sum=0
    for i in range(N, 0, -1):
        if int(S[i]) % P == 0:
            sum+= i
    print(sum)


else:
    dp1 = np.zeros(N + 1)
    dp2 = np.zeros(N + 1)
    dp3 = np.zeros(P)
    dp1[N] = int(S[N]) % P
    dp3[int(dp1[N])] += 1
    k = 1
    for i in range(N - 1, 0, -1):
        dp1[i] = (dp1[i + 1] + (int(S[i]) * 10 * k)) % P
        dp3[int(dp1[i])] += 1
        k = (k * 10) % P

    sum = 0

    for i in range(P):
        if i == 0:
            sum += (dp3[i] * (dp3[i] - 1)) // 2 + dp3[i]
            continue
        if dp3[i] == 0: continue
        sum += (dp3[i] * (dp3[i] - 1)) // 2
    print(int(sum))

Submission status: Accepted

Solution code:
from collections import defaultdict

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

ans = 0
if p == 2:
    for i in range(n):
        if s[i] % 2 == 0:
            ans += (i + 1)
elif p == 5:
    for i in range(n):
        if s[i] % 5 == 0:
            ans += (i + 1)
else:
    d = defaultdict(lambda: 0)
    ten = 1
    for i in reversed(range(n)):
        a = (s[i] * ten) % p
        d[i] = (d[i+1]+a) % p
        ten *= 10
        ten %= p

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

Submission status: Accepted

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}
        res = 0
        d = 1
        for i, s in enumerate(S[::-1]):
            r += int(s) * d
            r %= P
            d *= 10
            d %= P
            c = D.setdefault(r, 0)
            res += c
            D[r] += 1
        print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

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 += pow(10, i, P) * int(S[N - 1 - 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: Accepted

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)
    tens = 1
    v = 0
    for i, si in enumerate(ssr):
        v = (v + (si%p)*tens)%p
        mu[i] = v
        c[v] += 1
        tens *= 10
        tens %= p
    c[0] += 1
    for i in c:
        if i:
            ans += ((i-1)*i)//2
        
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

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]) % p == 0:
            c += i + 1

else:
    mm = {}
    r = 0
    mten = 1
    for i in range(n - 1, -1, -1):
        ch = int(s[i])
        r = (r + ch * mten) % p
        mten = (mten * 10) % p
        if r in mm:
            c += mm[r]
            mm[r] += 1
        else:
            mm[r] = 1

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

Submission status: Accepted

Solution code:
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

    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: Accepted

Solution code:

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

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

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

    count = [0 for i in range(P)]
    for i in range(N, -1, -1):
        ans += count[mods[i]]
        count[mods[i]] += 1

    print(ans)

main()

Submission status: Accepted

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

ans = 0

ruisekiwa = [0]*(n+1)
ten = 1

if 10 % p == 0:
  for i in range(n):
    if int(s[i]) % p == 0:
      ans += i+1
else:
  for i in range(0,n)[::-1]:#iは(n-1)から0まで降順にループ
    a = int(s[i]) * ten % p
    ruisekiwa[i] = (ruisekiwa[i+1] + a) % p
    ten *= 10
    ten %= p
    
  cnt = [0]*p
  for i in range(0,n+1)[::-1]:
    ans += cnt[ruisekiwa[i]]
    cnt[ruisekiwa[i]] += 1
print(ans)

Submission status: Accepted

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]))



if P == 2 or P == 5:
    for i in range(0,N):
        if S[i]%P == 0:
            sum += N-i
else :
    digit = 1
    rem_list = [0]
    for i in range(N):
        rem_list.append(((S[i]*digit)%P+rem_list[i])%P)
        digit *= 10
        digit %= P
    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: Accepted

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

ans = 0

if p == 2 or p == 5:
    for i in range(n):
        if s[i]%p == 0:
            ans += i+1
    print(ans)
    
else:
    s = s[::-1]
    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: Accepted

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 p == 5:
        for i in range(n):
            if int(s[i]) % p == 0:
                ans += (i + 1)
    else:
        c = [0] * p
        prev = 0
        c[0] = 1
        for i in range(n):
            num = int(s[n - i - 1])
            m = (num * pow(10, i, p) + prev) % p
            c[m] += 1
            prev = m

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, P = map(int, rl().split())
    S = input()
    
    ans = 0
    if P == 2 or P == 5:
        for i in range(N - 1, -1, -1):
            si = int(S[i])
            if si % P == 0:
                ans += i + 1
    else:
        cum = [0]
        t = 1
        for i in range(N - 1, -1, -1):
            cum.append(int(S[i]) * t % P)
            t = t * 10 % P
        for i in range(N):
            cum[i + 1] = (cum[i + 1] + cum[i]) % P
        
        counter = defaultdict(int)
        for val in cum:
            ans += counter[val]
            counter[val] += 1
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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)
    tenmod = 1
    lastmod = 0
    for i, c in enumerate(reversed(S)):
        if i > 0:
            tenmod = tenmod * 10 % P
        lastmod = (int(c) * tenmod % P + lastmod) % P
        d[lastmod] += 1
    ans = 0
    for m, cnt in d.items():
        if m == 0:
            ans += cnt
        ans += cnt * (cnt - 1) // 2
    print(ans)

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
s = input()[::-1]
if p == 2:
  ans = 0
  for num, i in enumerate(s):
    if int(i)%2 == 0:
      ans += n-num
elif p == 5:
  ans = 0
  for num, i in enumerate(s):
    if int(i)%5 == 0:
      ans += n-num
else:
  C = [0]*p
  now = 0
  for num, i in enumerate(s):
    a = int(i)
    now = (now+pow(10, num, p)*a)%p
    C[now] += 1
  ans = C[0]
  for c in C:
    ans += c*(c-1)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    N, P = map(int, input().split())
    S = list(map(int,list(input())))
    S_mod = [0] * N
    if P == 2:
        for i in range(N-1,-1,-1):
            if S[i] % 2 == 0:
                S_mod[i] = 1
        S_mod.reverse()
        ans = 0
        cnt = 0
        for i in range(N):
            if S_mod[i] == 1:
                cnt += 1
                ans += cnt
            else:
                ans += cnt
        print(ans)
        exit()
    if P == 5:
        for i in range(N-1,-1,-1):
            if S[i] % 5 == 0:
                S_mod[i] = 1
        S_mod.reverse()
        ans = 0
        cnt = 0
        for i in range(N):
            if S_mod[i] == 1:
                cnt += 1
                ans += cnt
            else:
                ans += cnt
        print(ans)
        exit()



    ten = 1
    for i in range(N-1,-1,-1):
        S_mod[i] = (S[i] * ten) % P
        ten *= 10
        ten %= P
    S_mod.reverse()
    S_acc = [0] * (N+1)
    for i in range(N):
        S_acc[i+1] = (S_acc[i] + S_mod[i]) % P
    d = defaultdict(int)
    for i in range(N+1):
        d[S_acc[i]] += 1
    ans = 0
    for i, j in d.items():
        if j >= 2:
            ans += (j * (j-1)) // 2

    print(ans)
    





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,p = [int(i) for i in input().split()]
s = input()
ans = 0
import collections

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

else:
  chk = []
  m = 0
  chk = collections.deque(chk)
  for i in range(n)[::-1]:
    m = (int(s[i])*pow(10,n-1-i,p)+m)%p
    chk.append(m)
  chk.append(0)
  chk = list(chk)
  c = collections.Counter(chk)
  for i in range(p):
    ans += c[i]*(c[i]-1)/2
  print(int(ans))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,p = [int(i) for i in 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)
    exit()

else:
  chk = [0]*p
  chk[0] = 1
  m = 0
  for i in range(n)[::-1]:
    m = (int(s[i])*pow(10,n-1-i,p)+m)%p
    chk[m] += 1
  for i in chk:
    ans += i*(i-1)/2
  print(int(ans))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,p = [int(i) for i in 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)
    exit()
    
else:
  chk = [0]*p
  chk[0] = 1
  m = 0
  for i in range(n)[::-1]:
    m = (int(s[i])*pow(10,n-1-i,p)+m)%p
    chk[m] += 1
  chk= [i*(i-1)/2 for i in chk]
  print(int(sum(chk)))

Submission status: Accepted

Solution code:
def main():  
  import sys
  input = sys.stdin.readline
  n,p = [int(i) for i in input().split()]
  s = input()
  ans = 0
  import collections
 
  if p == 2 or p == 5:
      for i in range(n):
          if int(s[i]) % p == 0:
              ans += i + 1
      print(ans)
      exit()
 
  else:
    chk = []
    m = 0
    chk = collections.deque(chk)
    for i in range(n)[::-1]:
      m = (int(s[i])*pow(10,n-1-i,p)+m)%p
      chk.append(m)
    chk.append(0)
    chk = list(chk)
    c = collections.Counter(chk)
    for i in range(p):
      ans += c[i]*(c[i]-1)/2
    print(int(ans))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():  
  import sys
  input = sys.stdin.readline
  n,p = [int(i) for i in input().split()]
  s = input()
  ans = 0
  
  import math
  def nCr(n, r):
    if n < r:
      return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

  else:
    chk = [0]*p
    chk[0] = 1
    m = 0
    for i in range(n)[::-1]:
      m = (int(s[i])*pow(10,n-1-i,p)+m)%p
      chk[m] += 1
    for i in chk:
      ans += nCr(i,2)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,p = [int(i) for i in input().split()]
s = input()
ans = 0

import math
def nCr(n, r):
  if n < r:
    return 0
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

else:
  chk = [0]*p
  chk[0] = 1
  m = 0
  for i in range(n)[::-1]:
    m = (int(s[i])*pow(10,n-1-i,p)+m)%p
    chk[m] += 1
  for i in chk:
    ans += nCr(i,2)
  print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import defaultdict

n, p = na()
s = ns()

if 10 % p == 0:
    ans = 0
    for i in range(n - 1, -1, -1):
        if int(s[i]) % p == 0:
            ans += i + 1
    print(ans)
    exit(0)

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

ans = 0
dic = defaultdict(int)
for i in range(n, -1, -1):
    ans += dic[c[i]]
    dic[c[i]] += 1

print(ans)

Submission status: Accepted

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

if p == 2 or p == 5:
    for i, x in enumerate(s):
        if (p == 2 and not x % 2) or (p == 5 and (x == 0 or x == 5)):
            ans += i+1
    print(ans)
    exit()

s.reverse()
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = (cum[i] + s[i] * pow(10, i, p)) % p
t = [0] * p
for x in cum: t[x] += 1

for x in t:
    ans += x * (x-1) // 2
print(ans)

Submission status: Accepted

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 += int(S[i])*pow(10,i,p)
    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: Accepted

Solution code:
def main():
    n,p = map(int,input().split())
    s = input()
    l = [0 for i in range(p)]
    l[0] = 1
    ten = 1
    cnt = 0

    ans = 0
    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):
            cnt = (cnt + int(s[-i-1]) * ten) % p
            l[cnt] += 1
            ten = (ten * 10) % p
        for i in l:
            if i > 1:
                ans += i * (i - 1) // 2

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N, P = (int(i) for i in input().split())
    S = input()
    ans = 0
    if P == 2 or P == 5:
        for i, s in enumerate(S, start=1):
            if int(s) % P == 0:
                ans += i
        return print(ans)
    cnt = [0]*P
    cnt[0] += 1
    d = 1
    cur = 0
    for s in S[::-1]:
        s = int(s)
        cur += (s * d) % P
        cur %= P
        d *= 10
        d %= P
        cnt[cur] += 1
    for c in cnt:
        if c:
            ans += c*(c-1)//2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,p = map(int,input().split())
s = input()
l = [0 for i in range(p)]
l[0] = 1
ten = 1
cnt = 0

ans = 0
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):
        cnt = (cnt + int(s[-i-1]) * ten) % p
        l[cnt] += 1
        ten = (ten * 10) % p
    for i in l:
        if i > 1:
            ans += i * (i - 1) // 2

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict

N, P = map(int, input().split())
S = input()
if P == 2 or P == 5:
    ans = 0
    for i in range(N):
        d = int(S[i])
        if d % P == 0:
            ans += i + 1
    print(ans)
else:
    ans = 0
    count = defaultdict(int)
    count[0] = 1
    num = 0
    factor = 1
    for i in range(N)[::-1]:
        num = (num + int(S[i]) * factor) % P
        factor = factor * 10 % P
        ans += count[num]
        count[num] += 1
    print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

def smallSol():
    dp = [0] * P
    ans = 0
    for s in map(int, S):
        newDp = [0] * P
        newDp[s % P] += 1
        for p in range(P):
            newDp[(p * 10 + s) % P] += dp[p]
        dp = newDp
        ans += dp[0]
    return ans

def largeSol():
    cnt = [0] * P
    cnt[0] += 1
    ret = 0
    now = 0
    for i, s in enumerate(map(int, S[:: -1])):
        now = (pow(10, i, P) * s + now) % P
        ret += cnt[now - P]
        cnt[now] += 1
    return ret

print(smallSol() if N * P <= 10**6 else largeSol())

Submission status: Accepted

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

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

elif p == 5:
    for i, char in enumerate(s):
        if int(char) % 5 == 0:
            ans += i + 1
    print(ans)

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

def solMin():
  dp=[[0]*P for i in range(N+1)]
  
  for i,s in enumerate(map(int,S), start=1):
    dp[i][s%P]+=1
    for p in range(P):
      dp[i][(p*10+s)%P]+=dp[i-1][p]
  
  return sum(dp[i][0] for i in range(N+1))

def solLarge():
  cnt=defaultdict(int)
  ret=0
  now=0
  
  for d,s in enumerate(map(int, S[::-1])):
    now+=pow(10,d,P)*s
    now%=P
    ret+=cnt[(now-P)%P]
    if now==0:
      ret +=1
    cnt[now]+=1
  
  return ret

print(solMin() if P*N<=10**6 else solLarge())

Submission status: Accepted

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

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

else:
    d=defaultdict(int)
    a=0
    for i in range(N):
        a+=int(S[N-i-1])*pow(10,i,P)
        a%=P
        d[a]+=1
    ans=d[0]
    for v in d.values():
        ans+=v*(v-1)//2
    print(ans)

Submission status: Accepted

Solution code:

def hoge():

    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 + pow(10, n-i-1, p) * int(s[i])) % p
    #         tmp = (tmp + 10**(n-i-1) * 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)
hoge()

Submission status: Accepted

Solution code:
from collections import Counter


n, p = map(int, input().split())
S = map(int, reversed(input()))

if p == 2 or p == 5:
    ans = 0
    mods = map(lambda x: x % p, S)
    for idx, mod in enumerate(mods):
        if mod == 0:
            ans += n - idx
    print(ans)
    exit()

mods = [0]
num = 0
digit = 1
for s in S:
    num += s * digit
    num %= p
    mods.append(num)
    digit = digit * 10 % p

counter = Counter(mods)
ans = 0
for count in counter.values():
    ans += count * (count-1) // 2
print(ans)

Submission status: Accepted

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[N-1-i])%5==0:
            ans+=(N-i)
    print(ans)

Submission status: Accepted

Solution code:
def sol(s, p):
	n = len(s)
	cnt = 0
	if p == 2 or p == 5:
		for i in range(n):
			if (s[i] % p == 0):
				cnt += i + 1
	else:
		pre = [0] * (n+2)
		pre[n+1] = 0
		b = 1
		for i in range(n, 0, -1):
			pre[i] = (pre[i+1] + s[i-1] * b) % p
			b = (b * 10) % p
		rec = [0] * p
		rec[0] = 1
		for i in range(n, 0, -1):
			cnt += rec[pre[i]]
			rec[pre[i]] += 1
	return cnt

if __name__ == "__main__":
	n, p = map(int, input().split())
	s = input()
	print (sol([int(i) for i in s], p))

Submission status: Accepted

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 in [2, 5]:
        for i, x in enumerate(s):
            if x % p == 0:
                ans += i + 1
        print(ans)
        exit()

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

def solMin():
    dp = [[0] * P for _ in range(N + 1)]

    for i, s in enumerate(map(int, S), start=1):
        dp[i][s % P] += 1
        for p in range(P):
            dp[i][(p * 10 + s) % P] += dp[i - 1][p]

    return sum(dp[i][0] for i in range(N + 1))

def solLarge():
    cnt = defaultdict(int)
    ret = 0
    now = 0

    for d, s in enumerate(map(int, S[:: -1])):
        now += pow(10, d, P) * s
        now %= P
        ret += cnt[(now - P) % P]
        if now == 0:
            ret += 1
        cnt[now] += 1

    return ret

print(solMin() if P * N <= 10**6 else solLarge())