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 = [int(i) for i in input()]
amarilist = [0 for i in range(P)]
zeroamari = [0 for i in range(P)]
golist = []
for i in range(P):
    x = 10 * i % P
    golist.append(x)
def mknext(amarilist):  
    nextamari = list(zeroamari)  
    for i in range(P):
        nextamari[golist[i]] += amarilist[i]
    return nextamari
ans = 0
for s in S:
    y = s % P
    nextamari = mknext(amarilist)
    if y == 0:
        amarilist = nextamari
    else:
        amarilist = nextamari[-1*y:]+nextamari[:-1*y]
    #print(amarilist,y)
    amarilist[y] += 1
    ans += amarilist[0]
    #print(amarilist[0],ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

reverse = False

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

cnt = 0
for i in range(n):
    for l in range(len(s)-i):
        num = int(s[i:i+l+1])
        q, mod = divmod(num, p)
        # print(num, q, mod)
        if mod == 0:
            cnt += 1

print(cnt)

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_list = [0] * p

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

  print(ans)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
n,p = map(int,input().split())
s = input()[::-1]
res = 0
for start in range(n):
    num = 0
    for i,end in enumerate(range(start,n)):
        num += (int(s[end]) * 10**i)
        num %= p
        if num == 0:
            res += 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
n,p = map(int,input().split())
s = input()
a = []
for i in range(n):
    for j in range(n-i):
        a.append(min(1,int(s[i:i+j+1])%p))
print(n*(n+1)//2-sum(a))

Submission status: Time Limit Exceeded

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

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

    add_len = n - (i - 1)
    for z in range(i+1, n):
        check_str = check_str * 10 + int(s[z])
        if int(check_str) % p == 0:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
from copy import copy
from collections import defaultdict
N,P = map(int, input().split())
S = input()
d = [0] * 10000
prev = [0] * 10000
key_prev = set([0])

for i,s in enumerate(S):
    tmp = [0] * 10000
    key_tmp = set([0])
    amari = int(s)%P
    tmp[amari] += 1
    key_tmp.add(amari)
    
    for k in key_prev:
        tmp[(k*10+amari)%P] += prev[k]
        key_tmp.add((k*10+amari)%P)
    
    for k in key_tmp:
        d[k] += tmp[k]

    prev = copy(tmp)
    key_prev = copy(key_tmp)
print(d[0])

Submission status: Time Limit Exceeded

Solution code:
# E

n,p = map(int, input().split())
s = str(input())
count=0
for i in range(n):
    for j in range(i,n+1):
        if i != j:
            if int(s[i:j]) % p == 0:
                count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import groupby

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

lis = []
for i in range(n):
    for j in range(i+1, n+1):
        lis.append(int(s[i:j]))
lis = sorted(lis)

ans = 0
for key, value in groupby(lis):
    if key%p == 0:
        ans += len(list(value))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import combinations

def input():
    return sys.stdin.readline()[:-1]


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

for i in range(len(S)):
    for j in range(i+1, len(S)+1):
        list_.append(int(''.join(S[i:j])))


count = 0
for i in list_:
    if i % P == 0:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
n,div= map(int,input().split(' '))
s=input()
a=0
for i in range(n):
	rem= 0
	for j in range(i,n):
		rem=(rem*10+int(s[j]))%div
		if rem%div==0:
			a+=1
print(a)

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:
n, p = map(int, 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:
def main():
  N, P = map(int, input().split(' '))
  S = input()

  def gen(n):
    for l in range(0, n):
      for r in range(l+1, n+1):
        yield slice(l, r)

  t = 0
  for i in gen(N):
    if int(S[i]) % P == 0:
      t += 1
  print(t)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

S = input()

dp = [-1 for i in range(N)]
def dpf(n):
    if n==N:
        return 0
    if dp[n]>=0:
        return dp[n]
    else:
        for i in range(n+1, N+1):
            num = int(S[n:i])
            ##print(num, n, i)
            if num%P == 0 :
                dp[n] = 1 + dpf(i) 
                return dp[n]
        dp[n]=0
        return dp[n]
    

# ans = [0 for i in range(N)]

# def solve(n):
#     if n==N:
#         return 0
#     else:
#         for i in range(n+1, N+1):
#             num = int(S[n:i])
#             ##print(num, n, i)
#             if num%P == 0 :
#                 ans[n] = 1 + solve(i) 
#                 return ans[n]
#         return 0
for i in range(N,-1,-1):
    dpf(i)

print(sum(dp))

Submission status: Time Limit Exceeded

Solution code:
# li = [[0] * 4 for i in range(3)]

# A = list.map(int, input().split())

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

S = input()


memo = {}


def dfs(n):
    if n in memo:
        return memo[n]

    i = n + 1
    while i <= N:
        temp_int = int(S[n:i])
        if temp_int % P == 0:
            if temp_int == 0:
                continue

            memo[n] = 1 + dfs(i)
            return memo[n]

        i += 1
    return 0


ans = 0
for i in range(N):
    temp = dfs(i)
    ans += temp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

count = 0

for i in range(n):
  for j in range(i,n):
    target.append(int(s[i:j+1]))

targetarray = np.array(target)
print(np.count_nonzero(targetarray % p == 0))

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import ceil, floor
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def digit_len(n):
    # 各桁の和を求める
    # 計算量: O(logN)
    ans = 0
    while n > 0:
        ans += 1
        n //= 10
    return ans

def main():
    n,p = map(int, input().split())
    s = input()
    k = digit_len(p)
    # 割り切れる整数の桁数は，明らかにpの桁数より大きくなくてはならない
    # つまり，部分文字列の長さは絶対にpの桁数以上である
    cnt = 0
    zero_counter = Counter(s)['0']
    for i in range(n):
        for j in range(i+k, n+1):
            m = int(s[i:j])
            if m % p == 0:
                #print(i,j,m)
                cnt += 1
    if k != 1:
        print(cnt+zero_counter)
    else:
        print(cnt)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# E
import numpy as np
N, P = list(map(int, input().split()))
S = str(input())

a = []
for i in range(1, len(S)+1):
    for j in range(0, len(S)-i+1):
        num = int(S[j:j+i])
        a.append(num)

print(np.sum(np.array(a) % P ==0))

Submission status: Time Limit Exceeded

Solution code:
s=input().split(' ')
P=int(s[1])
count=0
num=input()
for j in range(len(num)):
    x1=0
    for i in range(len(num)-j):
        if int(num[j:x1+j+1])%P==0:
            count+=1
        x1+=1
print(count)

Submission status: Time Limit Exceeded

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

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

    print(count)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,P = (int(i) for i in input().split(' '))
S = input()
S_size = len(S)
S = int(S)
count = 0
for s in range(1,S_size+1):
    s_ = 10**s
    for i in range(0, S_size-s+1):
        i_=10**i
        sub = (S//i_)%s_
        if sub%P==0:
            count+=1
print(count)

Submission status: Time Limit Exceeded

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

rlist = []
v = 1
while True:
    r = v % P
    if r in rlist:
        break
    rlist.append(r)
    v *= 10

MAX_N = 2*(10**5)+10
rmap = [[None] * MAX_N for i in range(MAX_N)]

ans = 0
for i in range(len(S)-1, -1, -1):
    for j in range(i, -1, -1):
        r = 0
        dr = rlist[j-i]
        nr = rmap[i+1][j]
        if nr:
            r = dr + nr
        else:
            r = dr
        if r == 0:
            ans += 1
        rmap[i][j] = r
    
print(ans)

Submission status: Time Limit Exceeded

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

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

    r = 0
    for el in l2:
        r += el.count(0)
    print(r)
main()

Submission status: Time Limit Exceeded

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

l = [[0] * p for _ in range(n+1)]
ans = 0

for i in range(n):
    m = int(s[i])
    l[i+1][m%p] = 1
    for j in range(p):
        if l[i][j] !=0:
            k = (j * 10 + m) % p
            l[i+1][k] += l[i][j]
    ans += l[i+1][0]




print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = [0] + list(map(int, input()))
dp = s.copy()
for j in range(len(dp)):
    dp[j] %= p
ans = dp[1:].count(0)
for i in range(2, n + 1):
    for j in range(n, i - 1, -1):
        a = (dp[j - 1] * 10 + s[j]) % p
        dp[j] = a
    ans += dp[i:].count(0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = input()
cnt = 0
li = []
for i in range(n):
    for j in range(n-i):
        li.append(int(s[i:i+j+1]))

for i in li:
    if i % p == 0:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

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

def warikireru(x):
    return x%p==0
cnt=0
for i in range(n):
    for j in range(i+1,n+1):
        tmp=s[i:j]
        k=int(tmp)
        if warikireru(k):
            cnt+=1
            
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
readline = sys.stdin.readline


def main():
    n,m = map(int, readline().split())
    val = str(readline().strip())
    ans = 0
    for i in range(n):
        for j in range(i,n):
            if int(val[i:j+1]) % m == 0:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
a, b = [int(x) for x in input().split()]
s = input()
count = 0
for i in range(a):
    for j in range(i+1, a+1):
        subnum = int(s[i:j])
        if subnum % b == 0:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
NN = 2020202
MOD = 10**9+7
INF = float("inf")


n, p = map(int, input().split())
S = input()
pl = len(str(p))
ans = 0
d = [0]*p

for i in range(len(S)):
    d[0] += 1
    nd = [0]*p
    a = int(S[i])
    for k, v in enumerate(d):
        ne = (k*10+a)%p
        nd[ne] += v
    ans += nd[0]
    d = nd
    # print(d)

print(ans)

Submission status: Time Limit Exceeded

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

m=[[0 for i in range(p)] for j in range(n)]

m[0][int(s[0])%p]=1

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

ans=0
for i in range(n):
  ans+=m[i][0]
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def sol():
    n,p=map(int,input().split())
    s=input()+"0"
    d=tuple([int(i) for i in s])
    ans=0
    for i in range(n):
        x=0
        for j in range(i,n):
            x=x*10+d[j]
            if x%p==0:
                ans+=1
            x%=p
    print(ans)

if __name__=="__main__":
    sol()

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):
  for j in range(N-i):
    L[j]=(L[j+1]+(S[j]*10**i))%P
  ans+=L[:-i].count(0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, P = list(map(int, input().strip().split()))
S = input().strip()
ans = 0
ss = set()
#print(S)
for i in range(1, N+1):
  for j in range(N-i+1):
    s = S[j:j+i]
    #print(s)
    num = int(s)
  #for v in itertools.combinations(S, i):
  #  num = int(''.join(v))    
    if num in ss or num % P == 0:
      #print(num)
      ans += 1
      ss.add(num)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, P=(int(i) for i in 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()
print(sum(int(int(S[i:j+1])%P==0) for i in range(N) for j in range(i, N)))

Submission status: Time Limit Exceeded

Solution code:
n,p=map(int,input().split())
s=input()
ans=0
sint=[]
for i in range(n):
  sint.append(int(s[i]))

for i in range(n):
  m=0
  for j in range(i,n):
    m=(m*10+sint[j])%p
    if m==0:
      ans+=1
     
print(ans)

Submission status: Time Limit Exceeded

Solution code:
info = [int(i) for i in input().split()]
string = input()
count = 0
for i in range(len(str(info[1])), info[0]+1):
    for j in range(0, info[0]-i+1):
        if int(string[j:j+i]) % info[1] == 0:
            count+=1
for i in range(1, len(str(info[1]))):
    count += string.count('0'*i)
print(count)

Submission status: Time Limit Exceeded

Solution code:

n,p = map(int,input().split())
s = list(input())
num = 0
while True:
    for i in range(1,len(s)+1):
        res = "".join(s[:i])
        if int(res) % p == 0:
            num +=1
    if len(s) == 1:
        break
    s.pop(0)
print(num)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, P = map(int, input().split(' '))
    P = int(P)
    S = input()
    count = 0
    for i in range(N):
        for n in range(i, N):
            try:
                k = int(''.join(S[i:n+1]))
            except ValueError:
                continue
            if k % P == 0:
                count += 1
    print(count)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,P = map(int,input().split())
S = [int(i) for i in input()]
amarilist = [0 for i in range(P)]
zeroamari = [0 for i in range(P)]
golist = []
for i in range(P):
    x = 10 * i % P
    golist.append(x)
def mknext(amarilist):  
    nextamari = list(zeroamari)  
    for i in range(P):
        x = 10 * i % P
        nextamari[golist[i]] += amarilist[i]
    return nextamari
ans = 0
for s in S:
    y = s % P
    nextamari = mknext(amarilist)
    if y == 0:
        amarilist = nextamari
    else:
        amarilist = nextamari[-1*y:]+nextamari[:-1*y]
    #print(amarilist,y)
    amarilist[y] += 1
    ans += amarilist[0]
    #print(amarilist[0],ans)
print(ans)

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

Submission status: Time Limit Exceeded

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

(n * (n - 1)) / 2

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

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int,input().split(" "))
x = input()
ans = 0
bag = 0
for i in range(n):
    nok = n - i
    bag = 0
    for j in range(nok):
        bag = bag*10 + int(x[i+j])
        bag %= p
        if bag == 0:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, P = lr()
    S = sr()
    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)
resolve()

Submission status: Time Limit Exceeded

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

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


    print(l.count(0))
main()

Submission status: Time Limit Exceeded

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

tmp=10%P

#print(dp)
for i in range(N-1):
    c=int(S[i+1])
    #print(c)
    for j in range(P):
        #dp[i+1][0][j]=dp[i][0][j]+dp[i][1][j]
        #dp[i+1][1][(tmp*j+c)%P]+=dp[i][1][j]
        dp[i+1][(tmp*j+c)%P]+=dp[i][j]
    #dp[i+1][1][c%P]+=1
    dp[i+1][c%P]+=1
    #print(dp)
#print(dp[N-1][0][0]+dp[N-1][1][0])
ans=0
for i in range(N):
    ans+=dp[i][0]
print(ans)

Submission status: Time Limit Exceeded

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

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

print(cnt)

Submission status: Time Limit Exceeded

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

cnt = 0
temp = ""

for i in range(0,N):
  for j in range(i+1,N+1):
    if int(temp.join(S[i:j]))%P == 0:
      cnt += 1
      
print(cnt)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

  def gen(n):
    for l in range(0, n):
      for r in range(l+1, n+1):
        yield slice(l, r)

  t = 0
  for i in gen(N):
    if int(S[i]) % P == 0:
      t += 1
  print(t)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def iin(): return int(input())
def iln(): return list(map(int, input().split()))

# N, P = [5, 5]
# S = "000055"

# N, P = [4,3]
# S = "3543"
#
# N, P = [5,2]
# S = "02020"
#
# N, P = [20,11]
# S = "33883322005544116655"

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

digits = []
for c in S:
    digits.append(int(c))

multipiler_values = [10 ** i for i in range(N)]
def to_int(digits, start, end):
    result = 0
    multiplier_idx = 0
    for j in range(end, start - 1, -1):
        if digits[j] > 0:
            result += multipiler_values[multiplier_idx] * digits[j]
        multiplier_idx += 1
    return result

start_pos = 0
while start_pos < N:
    if digits[start_pos] == 0:
        start_pos += 1
    else:
        break

count = 0
for i in range(start_pos, start_pos+1):
    for j in range(i, N):
        # substring [i..j]
        num = to_int(digits, i, j)
        if num % P == 0:
            count += 1

count *= (start_pos + 1)

for i in range(start_pos + 1, N):
    for j in range(i, N):
        # substring [i..j]
        num = to_int(digits, i, j)
        if num % P == 0:
            count += 1

print(count)

Submission status: Time Limit Exceeded

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

mod_10=10%p

#余りがkとなる組み合わせの数の配列

answer=0

dp=[0 for i in range(p)]
dp2=[0 for i in range(p)]
st=int(s[0])%p
dp[st]+=1
use_set={st}
answer+=dp[0]
zure_list=[mod_10*num%p for num in range(p)]
#ずれ量
for i in range(1,n):
    tmp_set=set()
    mod_i = int(s[i])%p
    tmp_set.add(mod_i)
    dp2[mod_i]+=1
    
    for num in use_set:
        tmp_num=(mod_i+zure_list[num])%p
        tmp_set.add(tmp_num)
        dp2[tmp_num]+=dp[num]
        dp[num]=0
    
    dp,dp2 = dp2,dp
    tmp_set, use_set = use_set,tmp_set
    answer+=dp[0]  

print(answer)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

count = 0
res = {}

for i in range(n):
    for j in range(i + 1, n + 1):
        key = s[i:j]

        if not key in res.keys():
            res[key] = (int(key) % p == 0)

        if res[key]:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
N,P = (int(i) for i in input().split(' '))
S = input()
S_size = len(S)
count = 0
for s in range(1,S_size+1):
    for i in range(0, S_size-s+1):
        sub = S[i:i+s]
        if int(sub)%P==0:
            count+=1
print(count)

Submission status: Time Limit Exceeded

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

mod_matrix = [ [0]*n for i in range(n) ]
ans = 0

for i in range(n):
    v = int(s[i])
    mod_matrix[i][i] = v % p
    for j in range(i+1):
        mod = (mod_matrix[j][i-1]*10 + v) % p
        mod_matrix[j][i] = mod
        if mod == 0:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
mod=998244353
inf=float("inf")
from math import sqrt
from collections import deque
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
@lru_cache(maxsize=10**10)
def karukosuu(x):
    if x==1:
        return 1 if int(s[0])%p==0 else 0
    res=1 if int(s[x-1])%p==0 else 0
    for i in range(x-1):
        if int(s[i:x])%p==0:res+=1
    return res+karukosuu(x-1)
n,p=map(int,input().split())
s=input()
print(karukosuu(n))
#TLEコードを投げてしまい申し訳ありません！！！！！！！！！！

Submission status: Time Limit Exceeded

Solution code:
n,p=map(int,input().split())
s=input()+"0"
d=tuple([int(i) for i in s])
ans=0
for i in range(n):
    x=0
    for j in range(i,n):
        x=x*10+d[j]
        if x%p==0:
            ans+=1
        x%=p
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, p = (int(i) for i in 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 = cnt + 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N,P = map(int,input().split())
S = input()
amarilist = [0 for i in range(P)]
zeroamari = [0 for i in range(P)]
golist = []
for i in range(P):
    x = 10 * i % P
    golist.append(x)
def mknext(amarilist):  
    nextamari = list(zeroamari)  
    for i in range(P):
        x = 10 * i % P
        nextamari[golist[i]] += amarilist[i]
    return nextamari
ans = 0
for s in S:
    s = int(s)
    y = s % P
    nextamari = mknext(amarilist)
    if y == 0:
        amarilist = nextamari
    else:
        amarilist = nextamari[-1*y:]+nextamari[:-1*y]
    #print(amarilist,y)
    amarilist[y] += 1
    ans += amarilist[0]
    #print(amarilist[0],ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = input()
zeros = [i for i, _ in enumerate(s) if _ == '0']
sum = len(zeros)
pn = p

while True:
  tn = s.count(str(pn))
  index = 0
  sum += tn
  for i in range(tn):
    index = s.index(str(pn), index)
    for i in range(len(zeros)):
      if zeros.count(index-i-1) == 1:
        sum += 1
      else:
        break
    index += 1
  if pn+p > int(s):
    break
  pn += p
print(sum)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations as c
l,p=map(int,input().split())
s=input()
print(sum(1 for i in (s[x:y] for x,y in c(range(l+1),r=2)) if int(i)%p==0))

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(len(S),-1,-1):
  r = 0
  for j in range(i):
    x = int(S[i-1-j])*(10**j)
    #print(x)
    if x not in d:
      d[x] = x%P
    r += d[x]
    r %= P
    if r == 0:
      ans += 1
print(ans)

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:
[n,p] = [int(x) for x in input().split()]
s = input()

count = 0
for start_pos in range(n):
    for end_pos in range(start_pos+1,n+1):
        if int(s[start_pos:end_pos])%p == 0:
            count += 1

print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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


#print(s)

#s = [0] + s
#from itertools import accumulate
#cum =list(accumulate(s))
#cum = [c%p for c in cum]

def power(a, n, mod):
  bi=str(format(n,"b")) #2進数
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res

temp = 0
cum = [0]*n
for i in range(n):
    temp += s[i]*10**i
    temp += s[i]*power(10, i, p)
    temp = temp%p
    cum[i] = temp
cum = [0]+cum

#print(cum)

d = {}
ans = 0
for i in range(n+1):
  if cum[i] not in d:
    d[cum[i]] = 1
  else:
    ans += d[cum[i]]
    d[cum[i]] += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:


def calc(j, this_i, p, ps, next_ps):
    count = 0
    mod = (j*10+this_i)%p
    if mod == 0:
        count = ps[j]
        #print(this_i,j)
    if mod in next_ps:
        next_ps[mod] += ps[j]
    else:
        next_ps[mod] = ps[j]
        
    return next_ps, count

def main():

    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)
        #this_i = map(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]
            """
            next_ps, count2 = calc(j, this_i, p, ps, next_ps)
            count += count2

        """
        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
        """
        next_ps, count2 = calc(0, this_i, p, {0:1}, next_ps)
        count += count2

        ps = next_ps
        #print(ps)

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

Submission status: Time Limit Exceeded

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

S = input()
d = defaultdict(int) #全余り
prev = defaultdict(int) #以前の余り
for i,s in enumerate(S):
    tmp = defaultdict(int) #追加するときの余り
    amari = int(s)%P

    tmp[amari] += 1
    for k in prev.keys():
        tmp[(k*10+amari)%P] += prev[k]

    for k in tmp.keys():
        d[k] += tmp[k]

    prev = copy(tmp)
print(d[0])

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(N-i):
        if int(str(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()
l = [int(x) for x in list(str(s))]
cnt = 0
for ind0 in range(len(l)):
    for length in range(1,n-ind0+1):
        sub_l = l[ind0:ind0+length]
        x = 0
        for ind1 in range(length):
            x += sub_l[ind1] * 10 ** (length-ind1-1)
        if x % p == 0:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

ret = 0

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

Submission status: Time Limit Exceeded

Solution code:
def answer():
    n, p = map(int, input().split())
    s = input()
    m = [0] * p
    dp = [0]
    for i, a in enumerate(s):
        m = amari(m, int(a), p)
        dp.append(dp[i] + m[0])
    print(dp[-1])

def amari(m, a, p):
    mm = [0] * p
    for i, b in enumerate(m):
        if b == 0:
            continue
        mm[(i * 10 + a) % p] += b
    mm[a%p] += 1
    return mm

answer()