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

def solve():
    input = sys.stdin.readline
    N, P = map(int, input().split())
    S = list(input().strip("\n"))

    if P == 2 or P == 5:
        count = 0
        for i in range(N):
            s = int(S[N - 1 - i])
            if s % P == 0: count += N - i
        print(count)
    else:
        modDict = dict()
        modDict[0] = 1
        sSum = 0
        for i in range(N):
            s = int(S[N - 1 - i])
            sSum += s * pow(10, i, P)
            sSum %= P
            if sSum in modDict: modDict[sSum] += 1
            else: modDict[sSum] = 1
        count = 0
        for key in modDict:
            count += modDict[key] * (modDict[key] - 1) // 2
        print(count)
            

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
s = input()
ans = 0
# p == 2,5
if 10 % p == 0:
    for r in range(n):
        if int(s[r]) % p == 0:
            ans += r + 1
    print(ans)
    exit()

d = [0 for _ in range(n + 1)]
ten = 1

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

cnt = [0 for _ in range(p)]
for i in range(n, -1, -1):
    ans += cnt[d[i]]
    cnt[d[i]] += 1

#print(d)

print(ans)

Submission status: Accepted

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

T = [0] * (N + 1)
T[0] = 0
e = 1
for i in range(N):
  T[i + 1] = T[i] + int(S[N - i - 1]) * e
  T[i + 1] %= P
  e *= 10
  e %= P

a = {}
for i in range(N + 1):
  if T[i] in a:
    a[T[i]] += 1
  else:
    a[T[i]] = 1

num = 0
if P % 2 == 0 or P % 5 == 0:
  for i in range(N):
    if int(S[i]) % P == 0:
      num += 1 + i
else:
  for k in a:
    num += a[k] * (a[k] - 1) // 2

print(num)

Submission status: Accepted

Solution code:
from collections import Counter


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

cnt = 0
if P in [2, 5]:
    for i, s in enumerate(S):
        if int(s) % P == 0:
            cnt += (i + 1)
else:
    num = 0
    mods = Counter()
    for i, s in enumerate(reversed(S)):
        num += int(s) * pow(10, i, P)
        num %= P
        mods[num] += 1
    mods[0] += 1
    for i, s in enumerate(S):
        mods[num] -= 1
        cnt += mods[num]
        num -= int(s) * pow(10, N - 1 - i, P)
        num %= P

print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter


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

cnt = 0
if P in [2, 5]:
    for i, s in enumerate(S):
        if int(s) % P == 0:
            cnt += (i + 1)
else:
    T = [0] * (N + 1)
    mods = Counter({0: 1})
    for i, s in enumerate(reversed(S)):
        T[N - 1 - i] = (T[N - i] + int(s) * pow(10, i, P)) % P
        mods[T[N - 1 - i]] += 1
    for t in T:
        mods[t] -= 1
        cnt += mods[t]

print(cnt)

Submission status: Accepted

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

s = list(input())

ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    d = [0] * (n + 1)
    ten = 1
    for i in range(n - 1, -1, -1):
        a = int(s[i]) * ten % p
        ten *= 10
        ten %= p
        d[i - 1] = (d[i] + a) % p
    cnt = [0] * p
    for i in range(n, -1, -1):
        ans += cnt[d[i]]
        cnt[d[i]] += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

def a():
  n, p = list(map(int, input().split()))
  num = [int(s) for s in input()]
  
  if(p==2 or p==5):
    count=0
    for i in range(1,n+1):
      if(num[-i]%p == 0):
        count += n-i+1
    print(count)
    return
  
  counts = np.zeros(p)
  tmp = 0
  tens = 1
  for i in range(1,n+1):
    tmp = (tens*num[-i] + tmp) % p
    counts[tmp] += 1
    tens = (tens*10)%p
  ret = int(counts[0] + sum(counts*(counts-1)//2))
  print(ret)
  return
a()

Submission status: Accepted

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

S = input()


cnt = 0
if P in [2,5]:
    for i in range(N):
        cnt += i+1 if int(S[i]) % P == 0 else 0
else:
    table = [0] * P # ?1
    Ui = 0
    ten = 1
    
    S = S[::-1]
    table[0] = 1 # ?2
    
    for i in range(N):
        Ui = (Ui + int(S[i]) * ten) % P # ?3
        
        cnt += table[Ui] # ?4
        
        table[Ui] += 1 # ?5
        ten = (ten * 10) % P # ?6
print(cnt)

Submission status: Accepted

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

if P == 2 or P == 5:
    print(sum(i for i, s in enumerate(S, 1) if s % P == 0))
    quit()

C = [0] * P
tens = 1
cur = 0
for s in reversed(S):
    cur = (cur + s * tens) % P
    C[cur] += 1
    tens = (tens * 10) % P

print(C[0] + sum(c * (c - 1) // 2 for c in C))

Submission status: Accepted

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

n,p = mi()
s = input()
srev = s[::-1]

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

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

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,P = map(int, input().split())
    S = input().rstrip()
    D = list(map(int, S))
    
    ans = 0
    if P == 2:
        for i, d in enumerate(D):
            if d&1 == 0: ans += i + 1
        return ans

    if P == 5:
        for i, d in enumerate(D):
            if d == 0 or d == 5: ans += i + 1
        return ans

    A = [0] * P
    num = Mint(0, P)
    for i in range(N):
        num += Mint(D[-1-i], P) * pow(10, i, P)
        A[num.value] += 1
    for a in A:
        ans += a * (a-1) // 2
    ans += A[0]
    return ans

class Mint:
    def __init__(self, value=0, mod=10**9+7):
        self.value = ((value % mod) + mod) % mod
        self.mod = mod

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, self.mod
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        return (u + self.mod) % self.mod

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value, self.mod)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % self.mod
        return self
    def __add__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other) + self.mod) % self.mod
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other), self.mod)
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % self.mod
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other, self.mod)
        self *= other.inverse
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other), self.mod)
        new_obj //= self
        return new_obj

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

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

# process
ans = 0
if P == 2 or P == 5:
    # 1桁目がPで割り切れる数をカウント
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i+1

else:
    cnt = [0]*P # S[i:N]%Pの結果をカウント
    num = 0
    tenPow = 1
    for i in reversed(range(N)):
        num = (num + int(S[i])*tenPow)%P
        tenPow = tenPow*10%P
        cnt[num] += 1

    ans += cnt[0]
    for c in cnt:
        ans += c*(c-1)//2 # c=0,1のときは0加算

# output
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N,P = map(int, input().split())
S = list(input()[::-1])
ans = 0
if P == 2:
    for i,s in enumerate(S):    
        if int(s) in [2,4,6,8,0]:
            ans += N - i
elif P == 5:
    for i,s in enumerate(S):    
        if int(s) in [0,5]:
            ans += N - i
else:
    d = defaultdict(int)
    cnt = 0
    d[0] = 1
    for i,s in enumerate(S):
        cnt = (cnt + pow(10,i,P)*int(s))%P
        d[cnt] += 1
    for k in d.keys():
        if d[k] > 1:
            ans += d[k]*(d[k]-1)//2 
print(ans)

Submission status: Accepted

Solution code:
def main():
	N, P = map(int, input().split())
	S = [int(c) for c in input()]

	if 10 % P == 0:
		ans = 0
		for i in range(N):
			if S[i] % P == 0:
				ans += (i + 1)

		print(ans)
		return


	M = [0] * (N + 1) #左からi番目から最後までの数字のmod p

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

	C = [0] * 10000

	for v in M:
		C[v] += 1

	ans = 0
	for v in C:
		if v > 0:
			ans += v * (v - 1) // 2

	print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,p = map(int,input().split())
s = list(map(int, list(input()))) # 数値のリストにしておく

def solve():
    if p in [2,5]: # 例外的な処理
        ret = 0
        for i in range(n): # 文字位置: i: 左から, n-1-i:右から (0 基準)
            lsd = s[n-1-i] # 最下位桁
            if lsd % p == 0: ret += n - i # LSD が割り切れたら LSD から右の桁数分加算
        return ret

    ten = 1 # S[l,r) のときの 10^r, init r=0 -> 10^0 = 1
    cnt = [0]*p # 余りで仕分けして個数を集計
    r = 0 # 左からの文字数 0 のときの余り
    cnt[r] += 1 # 余りが同じものをカウント
    for i in range(n): # 文字位置: i: 左から, n-1-i:右から (0 基準)
        msd = s[n-1-i] # 最上位桁
        r = (msd * ten + r) % p # r: 今回の余り
        ten = ten * 10 % p # N≦2*10^5 桁 なので剰余計算忘れずに！
        cnt[r] += 1 # 余りが同じものをカウント

    ret = 0
    for r in range(p): # 余り r の個数から組み合わせを計算
        ret += cnt[r] * (cnt[r] - 1) // 2 # nCr(n=i,r=2)= n(n-1)/2
    return ret

print(solve())

Submission status: Accepted

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

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

    l = [0]*p
    l[0] += 1
    s1 = s[::-1]
    ten = 1
    mod = 0
    for i in range(n):
        mod += int(s1[i])*ten%p
        mod %= p
        ten = ten*10%p
        l[mod] += 1
    ans = 0

    for i in l:
        ans += (i-1)*i//2
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

def solve():
    if p in [2,5]:
        ret = 0
        for i in range(n):
            if int(s[n-1-i]) % p == 0: ret += n-i
        return ret
    val = [0]*p
    ten = 1
    cur = 0
    val[cur] += 1
    for i in range(n):
        cur = (cur + int(s[n-1-i]) * ten) % p
        ten = ten * 10 % p
        val[cur] += 1
    ret = 0
    for i in range(p):
        ret += val[i] * (val[i] - 1) // 2
    return ret

print(solve())

Submission status: Accepted

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

def solve():
    if p in [2,5]:
        ret = 0
        for i in range(n):
            d = ord(s[n-1-i])-ord('0')
            if d % p == 0: ret += n-i
        return ret
    val = [0]*p
    ten = 1
    cur = 0
    val[cur] += 1
    for i in range(n):
        d = ord(s[n-1-i])-ord('0')
        cur = (cur + d * ten) % p
        ten = ten * 10 % p
        val[cur] += 1
    ret = 0
    for i in range(p): ret += val[i] * (val[i]-1)//2
    return ret

print(solve())

Submission status: Accepted

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

a = [0] * (N + 1)

if P != 2 and P != 5:
    tenfactor=1
    for i in range(1,N+1):
        a[i] = ((int(S[N-i])*tenfactor+a[i-1])%P)
        tenfactor*=10
        tenfactor%=P

    ans = 0
    from collections import Counter
    C=Counter(a)
    for v,i in C.items():
        ans += (i * (i - 1) // 2)
elif P == 2:
    ans = 0
    for i in range(N):
        if int(S[i]) % 2 == 0:
            ans += i + 1
elif P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) == 0 or int(S[i]) == 5:
            ans += i + 1

print(ans)

Submission status: Accepted

Solution code:
def main():

    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)
        exit()

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

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


if __name__ == '__main__':
    main()

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):
        c = int(c)
        if c%P==0:
            ans += (i+1)
    print(ans)
else:
    ans = 0
    a = [0]
    j = 1
    for c in S[::-1]:
        c = int(c)
        a.append((a[-1] + j*c) % P)
        j *= 10
        j %= P
    from collections import Counter
    ctr = Counter(a)
    for k,v in ctr.items():
        ans += v*(v-1)//2
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

    for i in range(n-1, -1, -1):
        d = int(s[i]) * pow(10, n-i, p)
        prev = (prev + d) % p
        dd[prev] += 1

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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


def solve1(s, p):
    v = 0
    pow10 = 1
    ans = 0
    cnt = [0] * p
    cnt[0] = 1

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


def solve25(s, p):
    cnt = 0
    ans = 0
    for i in range(len(s) - 1, -1, -1):
        if int(s[i]) % p == 0:
            cnt += 1
        ans += cnt
    return ans



if p in (2,5):
    print(solve25(s, p))
else:
    print(solve1(s, p))

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

            cnt += cum

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

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

    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

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

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

	else:
		tmp = 0

		mod_cnt = [0]*P

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


if __name__ == '__main__':
	main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
	N,P = map(int,input().split())
	S = [int(s) for s in list(input().strip())][::-1]
	num = 0
	ans = 0
	if P == 2 or P == 5:
		for i in range(N):
			if S[i]%P == 0:
				ans += N-i
		print(ans)
		return
	L = [0]*P
	L[0]=1
	t = 0
	s = 1
	for z in S:
		t = (z*s+t)%P	
		L[t]+=1
		s=s*10%P
	for l in L:
		ans += l * (l - 1) // 2
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from collections import Counter

N, P = map(int, input().split())
S = [int(s) for s in input()]
S.reverse()

ans = 0

if P != 2 and P != 5:
    prime10 = [1] * N
    for n in range(1, N):
        prime10[n] = (prime10[n-1] * 10) % P
    S = [(s * prime10[n]) % P for n, s in enumerate(S)]
    for n in range(1, N):
        S[n] = (S[n-1] + S[n]) % P

    S = Counter(S)
    for p in range(P):
        if p == 0:
            ans += S[p]
        ans += (S[p] * (S[p]-1)) // 2

else:
    for n in range(N):
        if S[n] % P == 0:
            ans += N - n

print(ans)

Submission status: Accepted

Solution code:
def main():
    N, P = map(int, input().split())
    S = input()
    if P == 2 or P == 5:
        r = 0
        for i, v in enumerate(S):
            if int(v) % P == 0:
                r += i + 1
        return r
    l = [0] * P
    l[0] = 1
    p = 0
    r = 0
    for i, v in enumerate(reversed(S)):
        p = (p + int(v) * pow(10, i, P)) % P
        r += l[p]
        l[p] += 1
    return r
print(main())

Submission status: Accepted

Solution code:
import sys
from itertools import combinations, permutations, product, combinations_with_replacement, accumulate
from heapq import heapify, heappop, heappush, heappushpop
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from math import sqrt, log, floor, ceil, factorial, cos, sin, pi#, gcd
from fractions import gcd
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
INF = float('inf')
LINF = 2**63-1
NIL = -LINF
MOD = 10**9+7
MGN = 4
def II(): return int(input())
def IF(): return float(input())
def IS(): return input().replace('\n', '')
def ILCI(n: int): return [II() for _ in range(n)]
def ILCF(n: int): return [IF() for _ in range(n)]
def ILI(): return list(map(int, input().split()))
def ILLI(n: int): return [[int(j) for j in input().split()] for i in range(n)]
def ILF(): return list(map(float, input().split()))
def ILLF(n: int): return [[float(j) for j in input().split()] for i in range(n)]
def LTOS(lst: list, sep: str = ' '): return sep.join(map(str, lst))
def DEC(lst: list): return list(map(lambda x: x-1, lst))
def INC(lst: list): return list(map(lambda x: x+1, lst))


def stoli(s, sep = ''):
    """ 文字列と区切り文字(列)を受け取り、
    整数のリストにして返す """
    if sep == None or sep == '':
        return list(map(int, list(s)))

    ls = []
    for e in s.split(sep):
        if e is None or e == '':
            continue
        else:
            ls.append(e)

    return list(map(int, ls))


def seg_count_all(A: list) -> dict:
    """ 整数リスト A を受け取り、
    リスト中の任意の整数 A[i] で挟まれた区間の数を辞書として返す """
    assert A is not None, "S は None でない"
    N = len(A)
    cnt = {}  # これまでに出現した A[i] の数
    res = {}  # A[i] で囲まれた区間の数
    for i in range(N):
        if A[i] in cnt:
            res[A[i]] += cnt[A[i]]  # 今回出現した A[i] を右端として、左端の候補が cnt 個ある
            cnt[A[i]] += 1
        else:
            res[A[i]] = 0
            cnt[A[i]] = 1

    return res


def main():
    N, P = ILI()
    S = IS()

    d = stoli(S)
    
    # 下 1 桁目の数字を d[0] に変更
    d.reverse()

    if 10%P == 0:
        assert P == 2 or P == 5
        ans = 0
        for l in range(N):
            # 部分文字列の末尾の数字で判定
            if d[l] % P == 0:
                ans += N-l  # l を固定して r を [l,N) の N-1 箇所から選ぶ
        print(ans)
        return 0

    # 各桁の数を P で割った余り md を求める
    # md[i] := (d[i] * 10^i) % P
    md = [0] * N
    ten = 1
    for i in range(N):
        md[i] = (d[i] * ten) % P
        ten *= 10
        ten %= P  # 10 と P は互いに素
    
    # md の mod P の塁積和を求める
    sum = [0] * N
    sum[0] = md[0]
    for i in range(1,N):
        sum[i] = (sum[i-1] + md[i]) % P

    # mod P の塁積和の数字が同じ区間は、差が 0 なので P の倍数となる
    ans = 0    
    cnt = seg_count_all(sum)  # sum[i] ごとにグメントを数え上げる
    for k in cnt:
        ans += cnt[k]
    ans += sum.count(0) # sum[i] == 0 のときは 1 文字で成り立つ

    print(ans)
    return 0


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
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 += i + 1
else:
    ct = Counter()
    ct[0] = 1
    prevmod = 0
    mods = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    for i in range(N-1, -1, -1):
        n = int(S[i])
        mod = (mods[n] + prevmod) % P
        ans += ct[mod]
        ct[mod] += 1
        prevmod = mod
        mods = [10 * a % P for a in mods]
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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


po10 = [1]
for i in range(n-1):
    po10.append((po10[-1]*10) % p)

for i in range(n):
    s[i] *= po10[n-1-i]
    s[i] %= p

ss = [0]

for i in range(n):
    ss.append(ss[-1]+s[i])
    ss[-1] %= p


ss = sorted(ss)

ll = len(ss)

ans = 0
tmp = [0,0]
for i in range(ll):
    if ss[i] != tmp[0]:
        ans += (i-tmp[1])*(i-tmp[1]-1) //2
        tmp[0] = ss[i]
        tmp[1] = i

ans += (ll-tmp[1])*(ll-tmp[1]-1)//2

print(ans)

Submission status: Accepted

Solution code:
import collections
import math

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

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

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

s+='0'

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

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

print(count)

Submission status: Accepted

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

def solve(N: int, P: int, S: str):
    if 10%P == 0:
        sum = 0
        for i in range(1,N+1):
            if int(S[-i]) % P == 0:
                sum += (N-i)+1
        print(sum)
        return
    else:
        current = 0
        C = 1
        counts = defaultdict(int)
        for i in range(1,N+1):
            if i == 1:
                current = int(S[-1])%P
            else:
                current = (int(S[-i])*C + current)%P
            counts[current]+=1
            C=C*10%P
        sum = 0
        for k in counts:
            c = counts[k]
            sum += int((c*(c-1)/2))
        sum += counts[0]
        print(sum)

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

Solution code:
import collections
import math

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

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

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

s+='0'

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

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

print(count)

Submission status: Accepted

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

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

Submission status: Accepted

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

tot = 0

if P in [2,5]:
  for i in range(1,N+1):
    if int(S[-i]) % P == 0:
      tot += N-i+1
else:
  S_mod = [0] * P
  S_mod[0] = 1 # 0 = 0 mod P
  mod = 0
  mod10 = 10 % P
  mod_power10 = 1
  for i in range(N-1, -1, -1):
    mod = (int(S[i]) % P * mod_power10 + mod % P) % P
    #print(S[i:], mod)
    tot += S_mod[mod]
    S_mod[mod] += 1
    mod_power10 = (mod_power10 * mod10) % P
print(tot)

Submission status: Accepted

Solution code:
import collections
import math

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

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

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

s+='0'

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

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

print(count)