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:
# -*- coding: utf-8 -*-

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

import math
from functools import lru_cache

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

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

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

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

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

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

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

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

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

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

mods = []
count = 0

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

print(count)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#
import sys
import math
import numpy as np
import itertools

# いくつか入力
n,p = (int(i) for i in input().split())
# 空白区切りの数列をリストに代入
s = [int(i) for i in list(input())] 

answer = 0
#print(s)
for i in range(n):
    q=0
    for j in range(i,n):
        q=q*10+s[j]
        if q%p==0:
            answer += 1
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


len_arr, prime = map(int, input().split())

s = input()
current = set()
counter = defaultdict(int)

for c in s:
    new = set()
    new.add(c)
    for sub in current:
        new.add(sub + c)
    for sub in new:
        counter[int(sub)] += 1
    current = new

ans = 0
for key, count in counter.items():
    if key % prime == 0:
        ans += count

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,P = [int(i) for i in input().split()]
S = input()
DP = [[[0]*P for h in range(2) ] for i in range(N+1)]
amari =[[(a*10+num)%P for a in range(P)]for num in range(10)]#amari[num][a]

if P not in [2,5]:
    for j,s in enumerate(S):
        Num = int(s)
        for a in range(P):
            DP[j+1][0][a] = DP[j][0][a] + DP[j][1][a]
            DP[j+1][1][amari[Num][a]] = DP[j][1][a]
        DP[j+1][1][Num%P] += 1
    print(DP[N][0][0]+DP[N][1][0])
else:
    for j,s in enumerate(S):
        Num = int(s)
        for a in range(P):
            DP[j+1][0][a] = DP[j][0][a] + DP[j][1][a]
            DP[j+1][1][amari[Num][a]] += DP[j][1][a]
        DP[j+1][1][Num%P] += 1
    print(DP[N][0][0]+DP[N][1][0])

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+1,N+1):
        ss = int(S[i:j])
        if ss % P == 0:
            cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = input()
ans = 0
x0 = [0]*p
for t in s:
  x1 = [0]*p
  z = int(t)
  x1[z%p] = 1
  for j in range(p):
    x1[(10*j+z)%p] += x0[j]
  x0 = x1
  ans += x0[0]
print(ans)

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(len(S)):
    for j in range(i, len(S)):
        tmp = int(S[i:j+1])
        if tmp % P == 0:
            cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import defaultdict

    N, P = map(int, input().split())
    S = (int(x) % P for x in input())

    dp = defaultdict(int)
    ndp = defaultdict(int)

    ret = 0
    for x in S:
        ndp[x] += 1
        for rest in dp.keys():
            next_rest = (rest * 10 + x) % P
            ndp[next_rest] += dp[rest]
        ret += ndp[0]
        dp = ndp
        ndp = defaultdict(int)

    print(ret)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

for i in range(N):
    for j in range(i+1, N+1):
        tmp += S[j-1]
        num = int(tmp)
        if num%P == 0:
            count += 1
    tmp = ''
print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

L = [0 for i in range(P)]
ans = 0

for i in range(N):
  s = int(S[i])
  nL = [0 for i in range(P)]
  for j in range(P):## ADD s
    nj = (j * 10 + s) % P
    nL[nj] += L[j]
    if j == 0:
      nL[s%P] += 1
  L = nL
#L = nL.copy()
  ans += L[0]
print(ans)

Submission status: Time Limit Exceeded

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

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

    print(cnt)

resolve()

Submission status: Time Limit Exceeded

Solution code:
# E - Divisible Substring

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def power(a, b, P):
	if b == 0:
		return 1
	elif b == 1:
		return a % P
	elif b % 2 == 0:
		return (power(a, b//2, P) ** 2) % P
	else:
		return (power(a, b//2, P) ** 2 * a) % P
 

N, P = (int(i) for i in input().split())
S = input()
l = [0]*N
ls = [0]*(N+1)
if P != 2 and P != 5:
    for i in range(N):
        a = int(S[N-1-i]) * power(10, i, P)
        l[i] = a%P
        ls[i+1] = (ls[i]+ l[i])%P
    d = {}
    for i in range(N+1):
        if ls[i] not in d:
            d[ls[i]] = 0
        d[ls[i]] += 1
    ans = 0
    for k in d:
        a = d[k]
        ans += (a-1)*a//2
    print(ans)
else:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += (i+1)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,P=map(int, input().split())
    S=input()
    l = 0
    r = 0
    ans = 0

    while l < N:
        t = S[l:r+1]
        if int(t) % P == 0:
            ans += 1
        r += 1
        if r + 1 > N:
            l += 1
            r = l
    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(n):
    for y in range(i,n):
        if int(s[i:y+1]) % p == 0:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

ketas = [None]
for i in range(0, n):
    #keta = i + 1
    ketas.append((10 ** i) % p)

out = 0
for i in range(n-1, -1, -1):
    cur_num = s[i] % p
    cur_keta = 1
    if cur_num == 0:
        out += 1
    for j in range(i-1, -1, -1):
        cur_keta += 1 
        cur_num = (ketas[cur_keta] * s[j] + cur_num) % p
        if cur_num == 0:
            out += 1

print(out)

Submission status: Time Limit Exceeded

Solution code:
#At coder 2020/3/8 E
import math
N,P=list(map(int,input().split())) 
S=str(input())

ans=0
for ii in range(N):
    for jj in range (N-ii):
        T=S[ii:ii+jj+1]
        T=int(T)
        if T%P==0:
            ans=ans+1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,P = [int(s) for s in 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:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd


mod=10**9+7
N,P=map(int,input().split())
S=input()
dp=[[0 for i in range(P)] for n in range(N)]
visited=set()
nset=set()
for n,s in enumerate(S):
    s=int(s)%P
    if nset:
        nset.clear()
    for i in visited:#range(P):
        A=(i*10+s)%P
        if dp[n-1][i]:
            nset.add(A)
            dp[n][A]+=dp[n-1][i]

    dp[n][s]+=1
    visited.add(s)
    visited=visited|nset
print(sum([i[0] for i in dp]))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8


def main():
    N, p = map(int, input().split())
    S = list(map(int, input()))

    ans = 0
    for h in range(N):
        x = S[h]
        for t in range(h+1, N):
            if x % p == 0:
                ans += 1
                x = S[t]
            else:
                x = 10 * (x % p) + S[t]
        if x % p == 0:
            ans += 1

    return ans


print(main())

Submission status: Time Limit Exceeded

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

sur1 = [int(s[0]) % p]
sur2 = [int(s[-1]) % p]
sur10 = [1 % p]
for i in range(n-1):
    sur1 += [(sur1[i] * 10 + int(s[i+1])) % p]
    sur10 += [(sur10[i] * 10) % p]
    sur2 += [(sur2[i] + sur10[i+1] * int(s[-i-2])) % p]

ans = 0
for i in range(n):
    for j in range(i,n):
        if i == 0:
            if sur1[j] == 0:
                ans += 1
        elif j == n-1:
            if sur2[n-i-1] == 0:
                ans += 1
        elif (sur1[j] - sur10[j-i+1] * sur1[i-1]) % p == 0:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

dp = [defaultdict(int) for i in range(N)]


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

for i in range(N-1):
    n = int(S[i+1])
    #print(n)
    for k,v in dp[i].items():
        dp[i+1][(10*k+n) % P] += v
    dp[i+1][n % P] += 1
    #print(dp[i+1])

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

Submission status: Time Limit Exceeded

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

for i in range(n):
    for j in range(n - i):
        num=''.join(s[j:j+i + 1])
        if int(num) % p == 0:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

S=str(input())

s=np.ones(N+1)

s[0]=0

for i in range(1,N+1):
    plu=0
    for j in range(i):
        num = int(S[i-1-j:i])
        if num%P==0:
            plu+=1
            
    s[i]=s[i-1]+plu
    
print(int(s[-1]))

Submission status: Time Limit Exceeded

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

ps = {}
count = 0

for i in s:
    next_ps = {}
    
    for j in range(p):
        next_ps[j] = 0
    
    this_i = int(i)
    for j in ps:
        mod = (j*10+this_i)%p
        if mod == 0:
            count += ps[j]
            #print(i,j)
        #if mod in next_ps:
        next_ps[mod] += ps[j]
        #else:
        #    next_ps[mod] = ps[j]
    
    mod = this_i%p
    if mod == 0:
        count += 1
        #print(i)
    #if mod in next_ps:
    next_ps[mod] += 1
    #else:
    #    next_ps[mod] = 1

    ps = next_ps
    #print(ps)
        
print(count)

Submission status: Time Limit Exceeded

Solution code:

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def main(inputs):
	n,p=getIntList(inputs[0])
	s=inputs[1][0]
		
	ans=0
	for i0 in range(len(s)):
		num=int(s[i0:i0+1])
		r=num%p
		if r==0: ans+=1
		for i1 in range(i0+1, len(s)):
			num=int(s[i1:i1+1])
			r1=r*10+num
			r=r1%p
			if r==0: ans+=1
	print(ans)
	

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(N):
  keta = N - i

  if keta < len(str(P)):
    ans += len([i for i in S if i == '0'])
    break
  num = int(S[0:keta])
  #print(num)
  if num % P == 0:
    ans += 1
  for j in range(i):
    num -= int(S[j]) * (10 ** (keta-1))
    num *= 10
    num += int(S[j + keta])
    #print(num)
    if num % P == 0:
      ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

N, P = map(int, input().split())
amari_S = np.array(list(map(int, input())))%P
count = (amari_S==0).sum()
amari_now = amari_S
for i in range(1, N): # i: start
  amari_now = (10*amari_now[:-1]+amari_S[i:])%P
  count += (amari_now==0).sum()

print(count)

Submission status: Time Limit Exceeded

Solution code:
N,P = map(int,input().split())
S = input()
ret = 0
for end in range(1,len(S)+1):
  for start in range(end):
    if int(S[start:end])%P==0:
      ret += 1
print(ret)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
n,p = map(int,stdin.readline().rstrip().split())
s = stdin.readline().rstrip()
point = 0
for i in range(1,n+1):
    for j in range(n-i+1):
        num = int(s[j:j+i])
        if num%p == 0:
            point += 1
print(point)

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = input()
ans = 0
x0 = [0]*p
for i in range(n):
  x1 = [0]*p
  z = int(s[i])
  x1[z%p] = 1
  for j in range(p):
    x1[(10*j+z)%p] += x0[j]
  x0 = x1
  ans += x0[0]
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(1, N+1):
    for j in range(N-i+1):
        s = int(S[j:j+i])
        if s % P == 0:
            ans += 1
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+1, N+1):
        num = int(S[i:j])
        if num%P == 0:
            count += 1
print(count)

Submission status: Time Limit Exceeded

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

c = 0
for st in range(N):
    for en in range(st, N):
        sub = S[st:en+1]
        sub_i = int(sub)
        if sub_i % P == 0:
            c += 1
        
print(c)

Submission status: Time Limit Exceeded

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

memo_ls = [{0:0} for j in range(n)]
memo_ls[0][int(s[0]) % p] = 1
for i, _s in enumerate(s[1:], 1):
    _s = int(_s)
    if memo_ls[i].get(_s % p) is None:
        memo_ls[i][_s % p] = 0
    memo_ls[i][_s % p] += 1
    for k, v in memo_ls[i-1].items():
        if memo_ls[i].get((k * 10 + _s) % p) is None:
            memo_ls[i][(k * 10 + _s) % p] = 0
        memo_ls[i][(k * 10 + _s) % p] += v

print(sum([memo_ls[i][0] for i in range(n)]))

Submission status: Time Limit Exceeded

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

count = 0

for left in range(N//2):
    for right in range(left+1, N-left):
        # print(left, right, S[left:right], S[right:N-left])
        if int(S[left:right]) % P == 0:
            count += 1
        if int(S[right:N-left]) % P == 0:
            count += 1
    if int(S[left:N-left]) % P == 0:
        count += 1
    # print(S[left:N-left])

if N % 2 == 1 and int(S[N//2]) % P == 0:
    count += 1
print(count)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
S = input()
count = [0] * P
ans = 0
for d in S:
    d = int(d)
    count[0] += 1
    ncount = [0] * P
    for i in range(P):
        ni = (i * 10 + d) % P
        ncount[ni] += count[i]
    count = ncount
    ans += count[0]
print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

    for i, x in enumerate(S):
        dp[i + 1][x % P] += 1
        for rest in range(P - 1, -1, -1):
            # dp[i + 1][rest] += dp[i][rest]

            next_rest = (rest * 10 + x) % P
            dp[i + 1][next_rest] += dp[i][rest]

    ret = sum(dp[i][0] for i in range(1, N + 1))
    print(ret)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd

mod=10**9+7
N,P=map(int,input().split())
S=input()
dp=[[0 for i in range(P)] for n in range(N)]
#visited=set()
for n,s in enumerate(S):
    s=int(s)
    for i in range(P):
        A=(i*10+s)%P
        dp[n][A]+=dp[n-1][i]
    dp[n][s%P]+=1

print(sum([i[0] for i in dp]))

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(1, n + 1):
    for j in range(n - i + 1):
        number = int(s[j:j + i])
        if number % p == 0:
            cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

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

res = 0
for l in range(n):
    for r in range(l+1, n+1):
#         print(s[l: r])
        if(int(s[l: r])%p==0): res += 1

print(res)

Submission status: Time Limit Exceeded

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

for i in range(n):
  for j in range(i,n):
    if int(''.join(s[i:j+1]))%p == 0:
      ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

ps = {}
count = 0

for i in s:
    next_ps = {}
    this_i = int(i)
    for j in ps:
        mod = (j*10+this_i)%p
        if mod == 0:
            count += ps[j]
            #print(i,j)
        if mod in next_ps:
            next_ps[mod] += ps[j]
        else:
            next_ps[mod] = ps[j]
    
    mod = this_i%p
    if mod == 0:
        count += 1
        #print(i)
    if mod in next_ps:
        next_ps[mod] += 1
    else:
        next_ps[mod] = 1

    ps = next_ps
    #print(ps)
        
print(count)

Submission status: Time Limit Exceeded

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

divider = pow(10, n-1)
minus = s // divider * divider
r = n*(n+1)//2
count = 0
for i in range(r):
    if (s // divider) % p == 0:
        count += 1
    divider //= 10
    if divider == 0:
        n -= 1
        divider = pow(10, n-1)
        s -= minus
        minus = s // divider * divider

print(count)

Submission status: Time Limit Exceeded

Solution code:
N,P = [int(i) for i in input().split()]
S = input()
DP = [[[0]*P for h in range(2) ] for i in range(N+1)]

for j,s in enumerate(S):
    i = j + 1
    Num = int(s)
    for a in range(P):
        DP[i][0][a] = DP[i-1][0][a] + DP[i-1][1][a]
        NewAmari = (a*10+Num)%P
        DP[i][1][NewAmari] += DP[i-1][1][a]
    DP[i][1][Num%P] += 1
print(DP[N][0][0]+DP[N][1][0])

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+1,n+1):
        if int(s[i:j]) % p == 0:
            cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(N):
  keta = N - i

  '''if keta < len(str(P)):
    break'''
  num = int(S[0:keta])
  #print(num)
  if num % P == 0:
    ans += 1
  for j in range(i):
    num -= int(S[j]) * (10 ** (keta-1))
    num *= 10
    num += int(S[j + keta])
    #print(num)
    if num % P == 0:
      ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

def main():
    N, P = [int(n) for n in input().split()]
    S = input()
    count = 0
    for start in range(N):
        for end in range(start + 1, N + 1):
            if int(S[start:end]) % P == 0:
                count += 1
    print(count)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
N,P = map(int,input().split())
S = input()
def num(s):
    flag = False
    for i in range(len(s)):
        if s[i] != '0':
            break
    return int(s[i:])
lens = len(S)
if P == 2:
    ans = 0
    for i in range(N):
        if int(S[i])%2 == 0:
            ans += i+1
    print(ans)
else:
    ans = 0
    for i in range(N):
        for j in range(i+1):
            snow = S[j:i+1]
            numi = num(snow)
            if numi%P == 0:
                ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, P = map(int, readline().split())
S = list(readline().decode().rstrip())

cnt = 0
for l in range(N):
    for r in range(l + 1, N + 1):
        if int("".join(S[l:r])) % P == 0:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

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

@lru_cache(maxsize=None)
def waru(i, j):
    return int(s[i:j+1]) % p == 0 

ans = 0
for i in range(len(s)):
    for j in range(i, len(s)):
        if waru(i, j):
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

dp = [0 for i in range(p)]
pp = 0
ans = 0
for i in range(n):
    c = int(s[i])
    tmp = [0 for pp in range(p)]
    for r in range(p):
        tmp[(r * 10 + c) % p] += dp[r]
    tmp[c % p] += 1
    dp = tmp
    ans += dp[0]
print(ans)
# print(dp)

Submission status: Time Limit Exceeded

Solution code:
# 大きい数用
def modPow(a, n, p):
    if n == 0:
        return 1
    if n == 1:
        return a
    if n % 2 == 1:
        return (a * (modPow(a, n//2, p) ** 2)) % p
    else:
        return (modPow(a, n//2, p) ** 2) % p


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

if P != 2 and P != 5:
    p_array = [0] * P
    mod = 0
    for i, s in enumerate(S[::-1]):
        s = int(s)
        mod = (mod + s * modPow(10, i, P)) % P
        p_array[mod] += 1

    ans = 0
    for i, p in enumerate(p_array):
        if i == 0:
            ans += p
        ans += (p * (p-1) // 2)

    print(int(ans))

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

Submission status: Time Limit Exceeded

Solution code:
import sys
n, p = [int(i) for i in sys.stdin.readline().split()]
s = input()
memo_ls = [{i : 0 for i in range(p)} for j in range(n)]
memo_ls[0][int(s[0]) % p] = 1
for i, _s in enumerate(s[1:], 1):
    _s = int(_s)
    memo_ls[i][_s % p] += 1
    for k, v in memo_ls[i-1].items():
        if v == 0:
            continue
        memo_ls[i][(k * 10 + _s) % p] += v
print(sum([memo_ls[i][0] for i in range(n)]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N, P = map(int, input().split())
S = input()

import numpy as np

amari_S = np.array([int(i)%P for i in S])

count = (amari_S==0).sum()
amari_now = amari_S

for i in range(1, N): # i: start
  amari_now = (10*amari_now[:-1]+amari_S[i:])%P
  count += (amari_now==0).sum()

print(count)

Submission status: Time Limit Exceeded

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

L = [0 for i in range(P)]
ans = 0

for i in range(N):
  s = int(S[i])
  nL = [0 for i in range(P)]
  for j in range(P):## ADD s
    nj = (j * 10 + s) % P
    nL[nj] += L[j]
    if j == 0:
      nL[s%P] += 1
  L = nL.copy()
  ans += L[0]
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0

for i in range(p):
    tmp = ss.count(i)
    ans += tmp*(tmp-1)//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

# input = sys.stdin.readline

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

s = input()

num = 0
for i in range(n):
    for j in range(i+1, n+1):
        x = int(s[i:j])
        if int(s[i:j]) % p == 0:
            num += 1
print(num)

Submission status: Time Limit Exceeded

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

  ans = 0

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

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

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

  for i in range(n):
    rem = int(s[i:]) % p
    ans += rem_dict[rem]
    if rem == 0:
      ans += 1      
    rem_dict[rem] += 1

  print(ans)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

S = input()


# left = 0
# right = N
ans = 0

for left in range(N):
    for right in range(left+1, N+1):
        if int(S[left:right]) % P == 0:
            ans += 1

print(ans)

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+1):
    #print(i, j, s[j:i+1])
    if int(s[j:i+1])%p==0:
      cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

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

ans =sum([int(s[i:j])%p==0  for i in range(0, ls) for j in range(i+1, ls+1)])
print(ans)

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+1, N+1):
        val = int(S[i:j])
        #print(i, j, val)

        if val % P == 0:
            cnt += 1

print(cnt)

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):
        num = int(s[i:j+1])
        if num %p == 0 :
            count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:

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

ans = 0
for i in range(N+1):
  for j in range(N+1):
    if i >= j:
      continue
    else:
      #i keta-me
      target = int(S[i:j])
      if target % P == 0:
        #print(S[i:j])
        ans +=1
        
        
print(ans)