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:
N, P = map(int, input().split())
S = list(map(int,list(input())))
U = []


for i in range(N+1):
    tmp = 0
    for j in range(i,N):
        tmp += S[j] * (10 ** (N-1-j))
    U.append(tmp % P)
    
def check1(i,j,P,S):
    return S[j] % P == 0

def check2(i,j,P,U):
    num = U[i]-U[j+1]
    return num == 0

def check(i,j,P,U,S):
    if P == 2 or P == 5:
        return check1(i,j,P,S)
    else:
        return check2(i,j,P,U)

ans = 0
for i in range(N):
    for j in range(i,N):
        if check(i,j,P,U,S):
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = [0] + list(map(int, input()))
dp = dict()
ans = 0
for i in range(1, n + 1):
    prev_dp = dp
    dp = dict()
    dp[s[i] % p] = 1
    for key, value in prev_dp.items():
        try:
            dp[(key * 10 + s[i]) % p] += value
        except KeyError:
            dp[(key * 10 + s[i]) % p] = value
    try:
        ans += dp[0]
    except KeyError:
        pass
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n,p = map(int,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()

sur = []
for i in range(n-1, -1, -1):
    sur += [int(s[i:]) % p]

d = defaultdict(int)
for x in sur:
    d[x] += 1

for k,v in d.items():
    if k == 0:
        ans += v * (v+1) // 2
    else:
        ans += v * (v-1) // 2
print(ans)

Submission status: Time Limit Exceeded

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

count=0
if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            count+=i+1
elif p==5:
    for i in range(n):
        if int(s[i])%5==0:
            count+=i+1
else:
    unum=[1]
    for i in range(p-1):
        unum.append(0)
    for i in range(n):
        unum[int(s[i:n])%p]+=1
    for i in range(p):
        unumi=unum[i]
        count+=(unumi*(unumi-1))*0.5
print(round(count))

Submission status: Time Limit Exceeded

Solution code:
def solve2(s):
    ans = 0
    for i, c in enumerate(s): #見る数字を右に広げていく
        if c in '02468':
            ans += i + 1 # 見ている数字のの一番右の桁が偶数ならその頭に乗っている数字の数だけ
                        # 答えに追加する
                        # 例 2254とし2→偶数、22→偶数（さらに先頭の2をどけても偶数）
                        # →225（奇数）→2254（偶数、上の3つをそれぞれどけても偶数）
    return ans


def solve5(s): # p==2のときと同じ原理
    ans = 0
    for i, c in enumerate(s):
        if c in '05':
            ans += i + 1
    return ans


def solve_other(s, p):
    ans = 0
    last_mod=0
    mods = [0]*p
    mods[0] = 1 #初期値として何も選んでない状態を1個加えとく
    digit = 1
    for i in range(n-1,-1,-1): # 一番右のけたから見る
        last_mod = (last_mod + int(s[i])*digit)%p # 最新のmodに新しく見ている桁*(10**x)を足してmod計算
        ans += mods[last_mod] # modリストに直前までのの値を答えに追加
        mods[last_mod] += 1 # modリスト更新
        digit *=10 # 桁上げ
    return ans


n, p = list(map(int, input().split()))
s = input()
if p == 2:
    print(solve2(s))
elif p == 5:
    print(solve5(s))
else:
    print(solve_other(s, p))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

def main():
    input=stdin.readline
    n, p = map(int, input().split())
    s = input()
    co = [0]*p
    
    c = 0
    num = 0
    
    if p == 2 or p == 5:
        for i in range(n):
            if int(s[i])%p == 0:
                c += i+1
    else:
        for i in range(n-1, -1, -1):
            num += int(s[i])*10**(n-1-i)
            m = num%p
            if m == 0:
                c += 1
            c += co[m]
            co[m] += 1   
            
    print(c)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

input=stdin.readline
n, p = map(int, input().split())
s = input()
co = [0]*p

c = 0
num = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i])%p == 0:
            c += i+1
else:
    for i in range(n-1, -1, -1):
        num += int(s[i])*10**(n-1-i)
        m = num%p
        if m == 0:
            c += 1
        c += co[m]
        co[m] += 1

        
print(c)

Submission status: Time Limit Exceeded

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

count=0
if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            count+=i+1
elif p==5:
    for i in range(n):
        if int(s[i])%5==0:
            count+=i+1
else:
    unum=[]
    for i in range(p):
        unum.append(0)
    num=0
    for i in range(n):
        unum[int(s[i:n])%p]+=1
    unum[0]+=1
    for i in range(p):
        count+=(unum[i]*(unum[i]-1))*0.5
print(round(count))

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = input()
co = [0]*p

c = 0
num = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i])%p == 0:
            c += i+1
else:
    for i in range(n-1, -1, -1):
        num += int(s[i])*10**(n-1-i)
        m = num%p
        if m == 0:
            c += 1
        c += co[m]
        co[m] += 1

        
print(c)

Submission status: Time Limit Exceeded

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

count=0
if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            count+=i+1
elif p==5:
    for i in range(n):
        if int(s[i])%5==0:
            count+=i+1
else:
    unum=[]
    for i in range(p):
        unum.append(0)
    num=0
    for i in range(n):
        unum[int(s[i:n])%p]+=1
    unum[0]+=1
    for i in range(p):
        if unum[i]>=2:
            count+=round((unum[i]*(unum[i]-1))*0.5)
print(count)

Submission status: Time Limit Exceeded

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

c = 0
num = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i])%p == 0:
            c += i+1
else:
    for i in range(n-1, -1, -1):
        num += int(s[i])*10**(n-1-i)
        m = num%p
        if m == 0:
            c += 1
        if m in co:
            c += co[m]
            co[m] += 1
        else:
            co[m] = 1
        
        
print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

c = 0
num = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i])%p == 0:
            c += i+1
else:
    for i in range(n-1, -1, -1):
        num += int(s[i])*10**(n-1-i)
        m = num%p
        if m == 0:
            c += 1
        c += co.get(m, 0)    
        co.update([m])        
        
print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

c = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i])%p == 0:
            c += i+1
else:
    for i in range(n-1, -1, -1):
        num = int(s[i:])
        m = num%p
        if m == 0:
            c += 1
        c += co.get(m, 0)    
        co.update([m])        
        
print(c)

Submission status: Time Limit Exceeded

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

for i in range(N+1):
    tmp = 0
    for j in range(i,N):
        tmp += S[j] * (10 ** (N-1-j))
    U.append(tmp)
    
def check(i,j,P,U):
    num = (U[i]-U[j])//10 ** (N - j)
    return num % P == 0


ans = 0
for i in range(N):
    for j in range(i+1,N+1):
        if check(i,j,P,U):
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

count=0
if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            count+=i+1
elif p==5:
    for i in range(n):
        if int(s[i])%5==0:
            count+=i+1
else:
    u=[]
    num=0
    for i in range(n):
        u.append(int(s[i:n])%p)
    u.append(0)
    for i in range(n):
        for j in range(i,n):
            if (u[i]-u[j+1])%p==0:
                count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:

#E
N,P=map(int,input().split())
S=input()
ans=0
if P in (2,5):
    for i,s in enumerate(S):
        if int(s)%P==0:
            ans+=i+1
else:
    cnt=[0 for _ in range(P)]
    CS=0
    for i,s in enumerate(S[::-1]):
        tmp2=(10**i)%P
        tmp=(int(s)*tmp2)%P
        CS=(CS+tmp)%P
        cnt[CS]+=1
        # print(CS)
        # print(cnt)
    for c in cnt:
        ans+=c*(c-1)//2
    ans+=cnt[0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#E
N,P=map(int,input().split())
S=input()
ans=0
if P in (2,5):
    for i,s in enumerate(S):
        if int(s)%P==0:
            ans+=i+1
else:
    cnt=[0 for _ in range(P)]
    CS=0
    for i,s in enumerate(S[::-1]):
        tmp=(int(s)*(10**i))%P
        CS=(CS+tmp)%P
        cnt[CS]+=1
        # print(CS)
        # print(cnt)
    for c in cnt:
        ans+=c*(c-1)//2
    ans+=cnt[0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,P=map(int,input().split())
S=input()
ans=0
if P in (2,5):
    for i,s in enumerate(S):
        if int(s)%P==0:
            ans+=i+1
else:
    cnt=[0 for _ in range(P)]
    CS=0
    for i,s in enumerate(S[::-1]):
        CS=(CS+int(s)*(10**i))%P
        cnt[CS]+=1
        # print(CS)
        # print(cnt)
    for c in cnt:
        ans+=c*(c-1)//2
    ans+=cnt[0]
print(ans)

Submission status: Time Limit Exceeded

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

count=0
if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            count+=i+1
elif p==5:
    for i in range(n):
        if int(s[i])%5==0:
            count+=i+1
else:
    u=[]
    num=0
    for i in range(n):
        u.append(int(s[i:n])%p)
    u.append(0)
    for i in range(n):
        for j in range(i,n):
            if (u[i]-u[j+1])%p==0:
                count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
def main():
  N,P = map(int,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
  else:
    # r = [0] * (N+1)
    # for i in range(N):
    #   r[N-1-i] = int(S[N-1-i:])%P
    # for i in range(N):
    #   for j in range(i,N):
    #     if (r[i]-r[j+1])%P == 0:
    #       ans += 1
    d = {}
    for i in range(N):
      r = int(S[N-1-i:])%P
      if r in d:
        d[r] += 1
      else:
        d[r] = 1
    if 0 in d:
      d[0] += 1
    for k,v in d.items():
      ans += v*(v-1)//2
  
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  N,P = map(int,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
  else:
    r = [0] * (N+1)
    for i in range(N):
      r[N-1-i] = int(S[N-1-i:])%P
    # for i in range(N):
    #   for j in range(i,N):
    #     if (r[i]-r[j+1])%P == 0:
    #       ans += 1
    d = {}
    for x in r:
      if x in d:
        d[x] += 1
      else:
        d[x] = 1
    for k,v in d.items():
      ans += v*(v-1)//2
  
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,P = map(int,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
else:
  r = [0] * (N+1)
  for i in range(N):
    r[N-1-i] = int(S[N-1-i:])%P
  # for i in range(N):
  #   for j in range(i,N):
  #     if (r[i]-r[j+1])%P == 0:
  #       ans += 1
  d = {}
  for x in r:
    if x in d:
      d[x] += 1
    else:
      d[x] = 1
  for k,v in d.items():
    ans += v*(v-1)//2
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,P = map(int,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
else:
  r = [0] * (N+1)
  for i in range(N):
    r[N-1-i] = int(S[N-1-i:])%P
  # for i in range(N):
  #   for j in range(i,N):
  #     if (r[i]-r[j+1])%P == 0:
  #       ans += 1
  d = {}
  for x in r:
    if x in d:
      d[x] += 1
    else:
      d[x] = 1
  for k,v in d.items():
    ans += v*(v-1)//2
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,P=map(int,input().split())
S=list(map(int,list(input())))
L=[s%P for s in S]
ans=L.count(0)
for i in range(1,N):
  L=[(L[j+1]+(S[j]*10**i))%P for j in range(N-i)]
  ans+=L.count(0)
print(ans)

Submission status: Time Limit Exceeded

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

a = []

count=0
for i in range(N):
    for j in range(i+1,N+1):
        count += (int(S[i:j]) % int(P) == 0)

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

s = input()

if 10 % p == 0:
    ans = sum(i + 1 for i, x in enumerate(s) if int(x) % p == 0)
    print(ans)
else:
    li = [0] * (n + 1)
    for i, x in enumerate(s[::-1]):
        li[i+1] = (li[i] + (int(x) * (10**(i+1)) % p)) % p

    ans = 0
    c = Counter(li[1:])
    ans = sum(v * (v - 1) for v in c.values()) // 2
    ans += c[0]
    print(ans)

Submission status: Time Limit Exceeded

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

if P == 2 or P == 5:
#if False:
  count = 0
  for n in range(N):
    if int(S[n]) % P==0:
      count += (n + 1)
  print(count)
else:    
  Pa = [0 for _ in range(P)]
  number = 0
  for i in range(N, 0, -1):
#    ui = int(S[i-1:])
    number = number + int(S[i-1])*10**(N-i)
    mp = number % P
    Pa[mp] += 1
  count = 0
  if Pa[0] > 0:
    count += Pa[0]
  for p in range( P):
    pmod = Pa[p]
    if pmod > 0:
      count += (pmod * (pmod - 1))//2
  print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

s = input()

if 10 % p == 0:
    ans = 0
    for i, x in enumerate(s):
        if int(x) % p == 0:
            ans += i + 1
    print(ans)
else:
    li = [0] * (n + 1)
    for i, x in enumerate(s[::-1]):
        li[i+1] = (li[i] + (int(x) * (10**(i+1)) % p)) % p

    ans = 0
    c = Counter(li[1:])
    for v in c.values():
        ans += v * (v-1)
    ans = ans // 2
    ans += c[0]
    print(ans)

Submission status: Time Limit Exceeded

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

if P == 2 or P == 5:
#if False:
  count = 0
  for n in range(N):
    if int(S[n]) % P==0:
      count += (n + 1)
  print(count)
else:    
  Pa = [0 for _ in range(P)]
  for i in range(N, 0, -1):
    ui = int(S[i-1:])
    mp = ui % P
    Pa[mp] += 1
  count = 0
  if Pa[0] > 0:
    count += Pa[0]
  for p in range( P):
    pmod = Pa[p]
    if pmod > 0:
      count += (pmod * (pmod - 1))//2
  print(count)

Submission status: Time Limit Exceeded

Solution code:
N,P=map(int,input().split())
S=[c for c in input()]
L=[]
cnt=0
for i in range(N):
    L.append(S)
    S=S[:]
    S.pop(-1)
for i in L:
    while len(i)!=0:
        if int("".join(i))%P==0:
            cnt+=1
        i=i[:]
        i.pop(0)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

s = input()

if 10 % p == 0:
    ans = 0
    for i, x in enumerate(s):
        if int(x) % p == 0:
            ans += i + 1
    print(ans)
else:
    li = [0]
    for i, x in enumerate(s[::-1]):
        li.append((li[-1] + int(x) * (10**i)) % p)

    ans = 0
    c = Counter(li[1:])
    for v in c.values():
        ans += v * (v-1)
    ans = ans // 2
    ans += c[0]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

s = input()

if 10 % p == 0:
    ans = 0
    for i, x in enumerate(s):
        if int(x) % p == 0:
            ans += i + 1
    print(ans)
else:
    li = [0]
    for i, x in enumerate(s[::-1]):
        li.append((li[-1] + int(x) * (10**i) % p) % p)

    ans = 0
    c = Counter(li[1:])
    for v in c.values():
        ans += v * (v-1)
    ans = ans // 2
    ans += c[0]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

s = input()

if 10 % p == 0:
    ans = 0
    for i, x in enumerate(s):
        if int(x) % p == 0:
            ans += i + 1
    print(ans)
else:
    li = [0]
    for i, x in enumerate(s[::-1]):
        li.append((li[-1] + int(x) * (10**i) % p) % p)

    ans = 0
    c = Counter(li[1:])
    for v in c.values():
        ans += (v * (v-1) // 2)
    ans += c[0]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

s = input()

if 10 % p == 0:
    ans = 0
    for i, x in enumerate(s):
        if int(x) % p == 0:
            ans += i + 1
    print(ans)
else:
    li = [0]
    for i, x in enumerate(reversed(s)):
        li.append((li[-1] + int(x) * (10**i) % p) % p)

    ans = 0
    c = Counter(li[1:])
    for v in c.values():
        ans += (v * (v-1) // 2)
    ans += c[0]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

from bisect import bisect_left

N,P = LI()
S = list(map(int,list(str(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:
    M = [0]*(N+1)
    now = 0
    for i in range(N):
        now += 10**i*S[N-1-i]
        now %= P
        M[N-1-i] = now
    d = defaultdict(list)
    for i in range(N+1):
        d[M[i]].append(i)
    for i in range(N):
        p = bisect_left(d[M[i+1]],i+1)
        ans += p

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

from bisect import bisect_left

N,P = LI()
S = str(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:
    M = [0]*(N+1)
    now = 0
    for i in range(N):
        now += 10**i*int(S[N-1-i])
        now %= P
        M[N-1-i] = now
    d = defaultdict(list)
    for i in range(N+1):
        d[M[i]].append(i)
    for i in range(N):
        p = bisect_left(d[M[i+1]],i+1)
        ans += p

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def solve(N: int, P: int, S: str):
    ans = 0
    DP = [0]*P
    for i in range(N):
        c = int(S[i]) % P
        nDP = [0]*P
        nDP[c % P] += 1
        for p in range(P):
            nDP[(10*p + c) % P] += DP[p]
        DP = nDP
        ans += DP[0]
    print(ans)
    return


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 = str(next(tokens))  # type: int
    solve(N, P, S)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import collections

def slowsolve(N, P, S):
    ans = 0
    for i in range(N):
        for j in range(i, N):
            if int(S[i:j+1]) % P == 0:
                # print(S[i:j+1])
                ans += 1
    return ans
def solve(N, P, S):
    mods = {}
    k = 0
    ans = 0

    for i, c in enumerate(S):
        k = int(c) % P

        # if (P - k) in mods:
        #     ans += mods[P - k]

        newmods = {k: 1}
        for m in mods:
            d = (m * 10 + k) % P
            if d not in newmods:
                newmods[d] = 0
            newmods[d] += mods[m]

        if 0 in newmods:
            ans += newmods[0]
        mods = newmods

    return ans

# print(slowsolve(5, 11, "33883"))
# print(solve(5, 11, "33883"))

if __name__ == "__main__":
    N, P = tuple(map(int, input().split(" ")))
    S = input()
    print(solve(N, P, S))

Submission status: Time Limit Exceeded

Solution code:
N,P=map(int,input().split(' '))
S =list(map(int,list(input()[::-1])))
ans = 0
cnt = [0]*P
cnt[0]=1
tmp = 0
for i in range(N):
    tmp += S[i]*10**i
    cnt[tmp%P] += 1
if P==2 or P==5:
    if P==2:
        check=[0,2,4,6,8]
    else:
        check=[0,5]
    for n,i in enumerate(S):
        if int(i) in check:
            ans += N-n
else:
    for i in cnt:
        ans += i*(i-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,P=map(int,input().split(' '))
S =input()
ans = 0
cnt = [0]*P
cnt[0]=1
for i in range(N):
    cnt[int(S[i:])%P] += 1
if P==2 or P==5:
    if P==2:
        check=[0,2,4,6,8]
    else:
        check=[0,5]
    for n,i in enumerate(S[::-1]):
        if int(i) in check:
            ans += N-n
else:
    for i in cnt:
        ans += i*(i-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def go(s, b, e, p):
	aux = ""
	qnt = 0
	while(b < e):
		aux += s[b]
		if(int(aux) % p == 0):
			qnt += 1
		b += 1
	return qnt

def main():
	n, p = input('').split(' ')
	n = int(n)
	p = int(p)
	s = input()
	qnt = 0
	for i in range(n):
		qnt += go(s, i, n, p)
	print(qnt)

main()

Submission status: Time Limit Exceeded

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

if P!=2 and P!=5:
    for i in range(0,N):
        chec=S[i]
        j=0
        while i+j<N:
            chec%=P
            if chec==0:
                count+=1
            j+=1
            if i+j<N:
                chec=chec*10+S[i+j]
if P==2:
    for i in range(N):
        if S[i]%2==0:
            count+=i+1
if P==5:
    for i in range(N):
        if S[i]==0 or S[i]==5:
            count+=i+1
print(count)

Submission status: Time Limit Exceeded

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

if P!=2 and P!=5:
    for i in range(0,N):
        chec=int(S[i])
        j=0
        while i+j<N:
                if chec%P==0:
                    count+=1
                j+=1
                try:
                    chec=(chec%P)*10+int(S[i+j])
                except:
                    pass
if P==2:
    for i in range(N):
        if int(S[i])%2==0:
            count+=i+1
if P==5:
    for i in range(N):
        if int(S[i])==0 or int(S[i])==5:
            count+=i+1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int,input().split())
s = str(input())
mods = [(i*10)%p for i in range(p)]
sums = [0] * p

tmp = 0
dp = [[0]*p for i in range(n+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()

for i in range(1,n+1):
    now = int(s[i-1])%p
    dp[i][now] += 1
    for j in range(p):
        dp[i][(mods[j]+now)%p] += dp[i-1][j]
#         tmp[(mods[j]+now)%p] += sums[j]
print(sum([dp[i][0] for i in range(n+1)]))
# print(*dp,sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=998244353
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,p=LI()
  s=S()

  ans=0
  if p==2 or p==5:
    for i,x in enumerate(s):
      if int(x)%p==0:
        ans+=i+1
    return ans

  _s=list(s)
  _s.reverse()

  a=[]
  i=1
  for x in _s:
    b=(i*int(x))%p
    a.append(b)
    i*=10%p

  b=[0]*p
  b[a[0]%p]=1
  for i in range(n-1):
    a[i+1]+=a[i]
    a[i+1]%=p
    b[a[i+1]]+=1

  for i,x in enumerate(b):
    if i==0:
      ans+=x
    if x>1:
      ans+=x*(x-1)//2

  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=998244353
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,p=LI()
  s=S()

  ans=0
  if p==2 or p==5:
    for i,x in enumerate(s):
      if int(x)%p==0:
        ans+=i+1
    return ans

  _s=list(s)
  _s.reverse()

  a=[]
  i=1
  for x in _s:
    b=(i*int(x))%p
    a.append(b)
    i*=10

  b=[0]*p
  b[a[0]%p]=1
  for i in range(n-1):
    a[i+1]+=a[i]
    a[i+1]%=p
    b[a[i+1]]+=1

  for i,x in enumerate(b):
    if i==0:
      ans+=x
    if x>1:
      ans+=x*(x-1)//2

  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, P = [int(x) for x in input().split()]
    S = input().strip()

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

    M = [0] * N
    for i, s in enumerate(S[::-1]):
        M[i] = (int(s) * (10 ** i)) % P

    MA = []
    MA.append(M[0])
    c = collections.Counter()
    ans = 0
    c[0] += 1
    ans += c[MA[0]]
    c[M[0]] += 1
    for i in range(1, N):
        MA.append((MA[i - 1] + M[i]) % P)
        ans += c[MA[i]]
        c[MA[i]] += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=998244353
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Summarize count of factor within list -- START --
def summarize_list(l):
  sl=sorted(l)

  a=sl[0]
  c=1
  res=[]

  for x in sl[1:]:
    if x==a:
      c+=1
    else:
      res.append([a,c])
      a=x
      c=1
  res.append([a,c])

  return res
# Summarize count of factor within list --- END ---

def main():
  n,p=LI()
  s=S()

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

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

  else:
    a=[]
    for i in range(n)[::-1]:
      _i=n-1-i
      b=(10**_i*int(s[i]))%p
      a.append(b)

    # print(a)
    for i in range(1,n)[::-1]:
      a[i-1]+=a[i]
      a[i-1]%=p
    # print(a)

    a=summarize_list(a)
    # print(a)

    for x,y in a:
      if x%p==0:
        ans+=y
      if y>1:
        ans+=(y*(y-1))//2

  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=998244353
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Summarize count of factor within list -- START --
def summarize_list(l):
  sl=sorted(l)

  a=sl[0]
  c=1
  res=[]

  for x in sl[1:]:
    if x==a:
      c+=1
    else:
      res.append([a,c])
      a=x
      c=1
  res.append([a,c])

  return res
# Summarize count of factor within list --- END ---

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

def main():
  n,p=LI()
  s=S()

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

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

  else:
    a=[]
    for i in range(n)[::-1]:
      _i=n-1-i
      b=(10**_i*int(s[i]))%p
      a.append(b)

    # print(a)
    for i in range(1,n)[::-1]:
      a[i-1]+=a[i]
      a[i-1]%=p
    # print(a)
    
    a=summarize_list(a)
    # print(a)

    for x,y in a:
      if x%p==0:
        ans+=y
      ans+=nCr(y,2)

  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

s1 = ""
s2 = ""
state = 0

s= []

for i in range(N):
    for j in range(N-i):
        if(j>4):
            tmp = s[-5]
            s.append((int(S[i+j-4:i+j+1])+ (tmp * 100000))%P)
            #print(S[i+j-4:i+j+1])
            continue
        s.append(int(S[i:i+j+1])%P)
        #print(S[i:i+j+1])

#print(s)

#co = np.mod(s,P)
answer=s.count(0)

#answer=np.count_nonzero(co == 0 )
print(answer)