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: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

cum = [0]*(N+1)
for i in range(0, N)[::-1]:
    a = int(S[i]) * 10**(N-1-i) % P
    cum[i] = int((cum[i+1]+a) % P)
ans = 0
cnt = [0]*P
for i in range(0, N+1)[::-1]:
    ans += cnt[cum[i]]
    cnt[cum[i]] += 1
print(ans)

Submission status: Time Limit Exceeded

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

cnt = 0
if P == 2 or P == 5:
    for i in range(N):
        if int(S[i]) % P == 0:
            cnt += (i+1)
            
else:
    dic = dict()
    dic[0] = 1
    for i in range(N):
        s = int(S[i : N])
        if not s%P in dic:
            dic[s%P] = 1
        else:
            dic[s%P] += 1
    for i in dic:
        cnt += dic[i]*(dic[i]-1)/2
        
print(int(cnt))

Submission status: Time Limit Exceeded

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

dp_table = list([0]*P for _ in range(N))

dp_table[0][int(S[0])%P] = 1

for i in range(N-1):
    d = dp_table[i]
    d_nxt = dp_table[i+1]
    s = int(S[i+1])
    d_nxt[s%P] += 1
    for j in range(P):
        if d[j] != 0:
            d_nxt[(j*10+s)%P] += d[j]

cnt = 0            
for i in range(N):
    cnt += dp_table[i][0]
    
print(cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import collections

n,p = map(int,raw_input().split(' '))
s = map(int,list(raw_input()))
prev = [0] * p
count = 0
for i in range(len(s)):
	cur = [0] * p
	
	for k in range(p):
		if prev[k]:
			nk = (10 * k + s[i]) % p
			cur[nk] += prev[k]
	cur[s[i] % p] += 1
	count += cur[0]
	prev = cur
print count

Submission status: Time Limit Exceeded

Solution code:
import collections

n,p = map(int,raw_input().split(' '))
s = map(int,list(raw_input()))
prev = [0] * p
count = 0
for i in range(len(s)):
	cur = [0] * p
	
	for k in range(p):
		nk = (10 * k + s[i]) % p
		cur[nk] += prev[k]
	cur[s[i] % p] += 1
	count += cur[0]
	prev = cur
print count

Submission status: Time Limit Exceeded

Solution code:
import collections

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

count = 0
for i in range(len(s)):
	cd = collections.Counter()
	for k in cc:
		nk = (10 * k + s[i]) % p
		cd[nk] += cc[k]
	cd[s[i] % p] += 1
	count += cd[0]
	
	cc = cd
print count

Submission status: Time Limit Exceeded

Solution code:
N,P=map(int,input().split())
S=input()
if P==2 or P==5:
    x=0
    for j in range(N):
        if int(S[j])%P==0:
            x+=j+1
    print(x)
else:
    A=[0]*P
    a=0
    b=1
    for i in range(N):
        a=(a+int(S[(N-1-i)])*(b%P))%P
        A[a]+=1
        b=b*10
    x=A[0]
    for k in range(P):
        x+=int(A[k]*(A[k]-1)/2)
    print(x)

Submission status: Time Limit Exceeded

Solution code:
N,P=map(int,input().split())
S=input()
if P==2 or P==5:
    x=0
    for j in range(len(S)):
        if int(S[j])%P==0:
            x+=j+1
    print(x)
else:
    A=[0]*P
    a=0
    b=1
    for i in range(len(S)):
        a=(a+int(S[(len(S)-1-i)])*(b%P))%P
        A[a]+=1
        b=b*10
    x=A[0]
    for k in range(P):
        x+=int(A[k]*(A[k]-1)/2)
    print(x)

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
S = input()
from collections import Counter
ans = 0
if P == 2 or P == 5:
    for i in range(N-1, -1, -1):
        t = S[i]
        if not int(t) % P:
            ans += i + 1
else:
    c = Counter()
    c[0] += 1
    p = 1
    t = int(S[N-1])
    c[t%P] += 1
    for i in range(N-2, -1, -1):
        p *= 10
        t = int(S[i]) * p + t
        c[t % P] += 1
    for a in c.values():
        ans += (a * (a-1)) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
S = input()
from collections import Counter
ans = 0
if P == 2 or P == 5:
    for i in range(N-1, -1, -1):
        t = S[i]
        if not int(t) % P:
            ans += i + 1
else:
    c = Counter()
    c[0] += 1
    t = ""
    for i in range(N-1, -1, -1):
        t = S[i] + t
        r = int(t) % P
        c[r] += 1

    for a in c.values():
        ans += (a * (a-1)) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
S = input()
from collections import Counter
ans = 0
if P == 2 or P == 5:
    for i in range(N-1, -1, -1):
        t = S[i]
        if not int(t) % P:
            ans += i + 1
else:
    c = Counter()
    c[0] += 1
    t = ""
    for i in range(N-1, -1, -1):
        t = S[i] + t
        r = int(t) % P
        c[r] += 1

    for k in c.keys():
        a = c[k]
        ans += (a * (a-1)) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
S = input()
from collections import Counter
ans = 0
if P == 2 or P == 5:
    for i in range(N-1, -1, -1):
        t = S[i]
        if not int(t) % P:
            ans += i + 1
else:
    c = Counter()
    c[0] += 1
    t = ""
    for i in range(N-1, -1, -1):
        t = S[i] + t
        r = int(t) % P
        c[r] += 1    

    for k in c.keys():
        a = c[k]
        ans += (a * (a-1)) // 2
print(ans)

Submission status: Time Limit Exceeded

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


if 10 % p == 0:
    for i in range(n):
        if int(D[i]) % p == 0:
            out += i + 1
else:
    mod = 0
    count = [0] * p
    ten = 1
    count[mod] += 1
    for i in range(n):
        mod = (mod + int(D[n-i-1]) * 10**i) % p
        ten = ten * 10 % p
        count[mod] += 1
    for c in count:
        out += (c * (c - 1)) // 2
print(out)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

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

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

    c = collections.Counter(A)
    ans = 0
    for k, v in c.items():
        ans += v * (v-1) // 2
    
    print(ans)

Submission status: Time Limit Exceeded

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

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
def main():
    N, P = map(int, input().split())
    S = list(map(int, input().rstrip("\r\n")))
    S.reverse()
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            if S[i] % P == 0:ans += N-i
    else:
        D = [0] * (N+1)
        tenpow = 1
        for i in range(N):
            S[i] = S[i] * tenpow % P
            tenpow *= 10 % P
            D[i+1] = (S[i] + D[i]) % P
        c = Counter(D)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
def main():
    N, P = map(int, input().split())
    S = list(map(int, input().rstrip("\r\n")))[::-1]
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            if int(S[i]) % P == 0:ans += N-i
    else:
        D = [0] * (N+1)
        tenpow = 1
        for i in range(N):
            S[i] = tenpow * S[i] % P
            tenpow *= 10 % P
            D[i+1] = (S[i] + D[i]) % P
        c = Counter(D)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
def main():
    N, P = map(int, input().split())
    S = list(map(int, input().rstrip("\r\n")[::-1]))
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            if int(S[i]) % P == 0:ans += N-i
    else:
        D = [0] * (N+1)
        D[0] = int(S[0]) % P
        tenpow = 1
        for i in range(N):
            S[i] = tenpow * S[i] % P
            tenpow *= 10 % P
        for i in range(N):
            D[i+1] = (S[i] + D[i]) % P
        c = Counter(D)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
def main():
    N, P = map(int, input().split())
    S = input().rstrip("\r\n")[::-1]
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            if int(S[i]) % P == 0:ans += N-i
    else:
        D = [0] * (N+1)
        D[0] = int(S[0]) % P
        tenpow = 1
        for i in range(N):
            a = 10*tenpow % P * int(S[i]) % P
            D[i+1] = (a + D[i]) % P
            tenpow *= 10 % P
        c = Counter(D)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
def main():
    N, P = map(int, input().split())
    S = input().rstrip("\r\n")[::-1]
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            if int(S[i]) % P == 0:ans += N-i
    else:
        D = [0] * (N+1)
        D[0] = int(S[0]) % P
        for i in range(1, N):
            a = 10**i % P * int(S[i]) % P
            D[i] = (a + D[i-1]) % P
        c = Counter(D)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
import math
def main():
    N, P = map(int, input().split())
    S = input().rstrip("\r\n")[::-1]
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            if int(S[i]) % P == 0:ans += N-i
    else:
        D = [0] * (N+1)
        for i in range(N):
            D[i] = int(S[:i+1][::-1]) % P
        c = Counter(D)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
S = input()
if 10 % P == 0:
    ans = 0
    for r in range(N):
        if int(S[r]) % P == 0:
            ans += r + 1
    print(ans)
    exit()

d = [0] * (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] * P
ans = 0
for i in range(N, -1, -1):
    ans += cnt[d[i]]
    cnt[d[i]] += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = input()
r = set()
last = 0
d = {0: 0}
total = 0
rem = 0
if p == 2:
    for i in range(0, len(s)):
        if int(s[i]) % 2 == 0:
            total += i + 1
    print(total)
elif p == 5:
    for i in range(0, len(s)):
        if int(s[i]) % 5 == 0:
            total += i + 1
    print(total)



else:
    power = 1
    for i in range(len(s) - 1, -1, -1):  # handling of 0's as n and rem
        n = int(s[i]) * power + rem
        power *= 10
        power = power % p
        rem = n % p
        if rem in d.keys():
            d[rem] += 1
        else:
            d[rem] = 1
        total += d[rem] - 1
    print(total + d[0])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

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

if p == 2 or p == 5:
  ans = 0
  for i, x in enumerate(S[::-1]):
    if x % p == 0:
      ans += n - i
else:
  mods = [0 for _ in range(p)]
  mods[0] = 1

  num = 0
  digit = 1
  for s in S[::-1]:
    num = (s * digit + num) % p
    mods[num] += 1
    digit = digit * 10
  
  ans = 0
  for m in mods:
    ans += m * (m - 1) // 2

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def main():
    N,P = map(int,input().split())
    S = input()
    ans = 0
    if P == 2 or P == 5:
        for i,s in enumerate(S):
            if int(s) % P == 0:
                ans += i + 1
    else:
        D = [0] * (N+1)
        for i in range(N):
            D[i] = int(S[N-1-i:N+1]) % P
        C = Counter(D)
        ans = sum([c*(c-1)//2 for c in C.values()])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def main():
    N,P = map(int,input().split())
    S = input()[::-1]
    ans = 0
    if P == 2 or P == 5:
        for i,s in enumerate(S):
            if int(s) % P == 0:
                ans += N-i
    else:
        D = [0] * (N+1)
        for i in range(N):
            D[i] =  int(S[:i+1][::-1]) % P
        C = Counter(D)
        for i in C.values():
            ans += i*(i-1)//2
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def main():
    N,P = map(int,input().split())
    S = input()[::-1]
    ans = 0
    if P == 2 or P == 5:
        for i,s in enumerate(S):
            if int(s) % P == 0:
                ans += N-i
    else:
        D = [0] * (N+1)
        for i in range(N):
            D[i] =  int(S[:i+1][::-1]) % P
        C = Counter(D)
        ans = sum([c*(c-1)//2 for c in C.values()])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# Problem E - Divisible Substring

from collections import Counter

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

# count
if P==2 or P==5:
    ans = 0
    for i in range(N-1, -1, -1):
        s = int(S[i])
        if s%P==0:
            ans += i + 1
    # output
    print(ans)
else:
    p_nums = [0]*(N+1)
    s = ""
    for i in range(N-1, -1, -1):
        s = S[i] + s
        p_nums[N - i] = int(s)%P
    p_counter = [0]*P
    for i in range(N+1):
        p_counter[p_nums[i]] += 1
    ans = 0
    for i in range(P):
        ans += p_counter[i] * (p_counter[i] - 1) // 2
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# Problem E - Divisible Substring

from collections import Counter

# 組み合わせ
def combinations_count(n, r):
    return n * (n - 1) // r

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

# count
if P==2 or P==5:
    ans = 0
    for i in range(N-1, -1, -1):
        s = int(S[i])
        if s%P==0:
            ans += i + 1
    # output
    print(ans)
else:
    p_nums = [0]*(N+1)
    s = ""
    for i in range(N-1, -1, -1):
        s = S[i] + s
        p_nums[N - i] = int(s)%P
    p_counter = [0]*P
    for i in range(N+1):
        p_counter[p_nums[i]] += 1
    ans = 0
    for i in range(P):
        ans += combinations_count(p_counter[i], 2)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# Problem E - Divisible Substring

from collections import Counter

# 組み合わせ
def combinations_count(n, r):
    return n * (n - 1) // r

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

# count
if P==2 or P==5:
    ans = 0
    for i in range(N-1, -1, -1):
        s = int(S[i])
        if s%P==0:
            ans += i + 1
    # output
    print(ans)
else:
    p_nums = [0]*(N+1)
    s = ""
    for i in range(N-1, -1, -1):
        s = S[i] + s
        p_nums[N - i] = int(s)%P
    p_counter = Counter(p_nums)
    ans = 0
    for key in p_counter.keys():
        p_c = p_counter[key]
        if p_c>=2:
            ans += combinations_count(p_c, 2)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# Problem E - Divisible Substring

from collections import Counter

# 組み合わせ
def combinations_count(n, r):
    return n * (n - 1) // r

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

# count
if P==2 or P==5:
    ans = 0
    for i in range(N-1, -1, -1):
        s = int(S[i])
        if s%P==0:
            ans += i + 1
    # output
    print(ans)
else:
    p_nums = [0]*(N+1)
    for i in range(N-1, -1, -1):
        s = int("".join(S[i:]))
        p_nums[N - i] = s%P
    p_counter = Counter(p_nums)
    ans = 0
    for key in p_counter.keys():
        p_c = p_counter[key]
        if p_c>=2:
            ans += combinations_count(p_c, 2)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def nCr(n,r):
  ret = 1
  for i in range(r):
    ret *= (n-i)
    ret //= i+1
  return ret    

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)
      
elif p == 5:
  for i in range(n):
    if int(s[i])%5 == 0:
      ans += (i+1)
      
else:      
  mods = [0]*(n+1)
  t = ''
  for i in range(n):
    t = s[-i-1] + t
    mods[i] = int(t)%p    
  c = Counter(mods)
  for k,v in c.items():
    if v > 1:
      ans += nCr(v,2)

print(ans)

Submission status: Time Limit Exceeded

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

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

    cnt_a = 0
    for s in S[::-1]:
        if int(s) % P == 0:
            cnt_a += 1

        cnt += cnt_a
else:
    r_lst = [0] * P
    r_lst[0] = 1

    cnt = 0
    num = 0

    for i, s in enumerate(S[::-1]):
        num  = (num + int(s) * pow(10, i)) % P
        cnt += r_lst[num]

        r_lst[num] += 1


print(cnt)

Submission status: Time Limit Exceeded

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

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

    cnt_a = 0
    for s in S[::-1]:
        if int(s) % P == 0:
            cnt_a += 1

        cnt += cnt_a
else:
    r_lst = [0] * P
    r_lst[0] = 1

    cnt = 0
    num = ''
    for s in S[::-1]:
        num = s + num
        r = int(num) % P

        cnt += r_lst[r]

        r_lst[r] += 1


print(cnt)

Submission status: Time Limit Exceeded

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

if P == 2:
    cnt = 0

    cnt_2 = 0
    for s in S[::-1]:
        if int(s) % 2 == 0:
            cnt_2 += 1

        cnt += cnt_2
elif P == 5:
    cnt = 0

    cnt_0 = 0
    cnt_5 = 0
    for s in S[::-1]:
        if s == '0':
            cnt_0 += 1
        elif s == '5':
            cnt_5 += 1

        cnt += cnt_0
        cnt += cnt_5
else:
    dic = {}
    dic[0] = 1
    cnt = 0
    num = ''
    for s in S[::-1]:
        num = s + num
        r = int(num) % P

        cnt += dic.get(r, 0)

        if r not in dic:
            dic[r] = 1
        else:
            dic[r] += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
## io
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
MIIZ = lambda: list(map(lambda x: x-1, MII()))
## dp
INIT_VAL = 0
MD2 = lambda d1,d2: [[INIT_VAL]*d2 for _ in range(d1)]
MD3 = lambda d1,d2,d3: [MD2(d2,d3) for _ in range(d1)]
## math
DIVC = lambda x,y: -(-x//y)
DIVF = lambda x,y: x//y

def main():
    n, p = MII()
    s = list(map(int, IS()))
    if 10%p == 0: # pが2または5の場合
        cnt = 0
        for i, si in enumerate(s):
            if si%p == 0:
                cnt += i+1
        print(cnt)
        return None

    d = {i: 0 for i in range(p)}
    d[0] = 1
    ss = 0
    x = 1
    for si in s[::-1]:
        ss += x*si
        ss %= p
        d[ss] += 1
        x = 10*x
    cnt = 0
    for dv in d.values():
        cnt += dv*(dv-1)//2
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
## io
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
MIIZ = lambda: list(map(lambda x: x-1, MII()))
## dp
INIT_VAL = 0
MD2 = lambda d1,d2: [[INIT_VAL]*d2 for _ in range(d1)]
MD3 = lambda d1,d2,d3: [MD2(d2,d3) for _ in range(d1)]
## math
DIVC = lambda x,y: -(-x//y)
DIVF = lambda x,y: x//y
from collections import defaultdict

def main():
    n, p = MII()
    s = list(map(int, IS()))
    if 10%p == 0: # pが2または5の場合
        cnt = 0
        for i, si in enumerate(s):
            if si%p == 0:
                cnt += i+1
        print(cnt)
        return None

    d = defaultdict(lambda: 0)
    d[0] = 1
    ss = 0
    x = 1
    for si in s[::-1]:
        ss += x*si
        ss %= p
        d[ss] += 1
        x = 10*x
    cnt = 0
    for dv in d.values():
        cnt += dv*(dv-1)//2
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
## io
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
MIIZ = lambda: list(map(lambda x: x-1, MII()))
## dp
INIT_VAL = 0
MD2 = lambda d1,d2: [[INIT_VAL]*d2 for _ in range(d1)]
MD3 = lambda d1,d2,d3: [MD2(d2,d3) for _ in range(d1)]
## math
DIVC = lambda x,y: -(-x//y)
DIVF = lambda x,y: x//y
from collections import defaultdict

def main():
    n, p = MII()
    s = IS()
    if 10%p == 0: # pが2または5の場合
        cnt = 0
        for i, si in enumerate(s):
            if int(si)%p == 0:
                cnt += i+1
        print(cnt)
        return None

    d = defaultdict(lambda: 0)
    d[0] = 1
    ss = 0
    x = 1
    for si in s[::-1]:
        ss += x*int(si)
        ss %= p
        d[ss] += 1
        x = 10*x
    cnt = 0
    for dv in d.values():
        cnt += dv*(dv-1)//2
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
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:
    mod_cnt = [0]*P
    mod_cnt[0] = 1
    k = 0
    for i in range(1, N+1):
        k += 10**(i-1) * int(S[-i])
        mod_cnt[k % P] += 1
    ans = 0
    for cnt in mod_cnt:
        ans += (cnt * (cnt-1)) // 2
    print(ans)