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 = list(map(int,input().split()))
S = input()
DP1 = [[0]*(P) for i in range(N)]
DP2 = [[0]*(P) for i in range(N)]
DP1[0][int(S[0]) % P] = 1
for i in range(N-1):
    DP1[i+1][int(S[i+1]) % P] += 1
    for j in range(P):
        DP1[i+1][((j*10)+int(S[i+1])) % P] += DP1[i][j]
    for j in range(P):
        DP2[i+1][j] = DP1[i][j] + DP2[i][j]
print(DP1[N-1][0] + DP2[N-1][0])

Submission status: Time Limit Exceeded

Solution code:
NP = input().split(' ')
S =input()
N = int(NP[0])
P = int(NP[1])
Ss = [int(S[x:y+1]) for x in range(N) for y in range(N) if x<=y]
SP = [u for u in Ss if u % P ==0]
print(len(SP))

Submission status: Time Limit Exceeded

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

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

print(count)

Submission status: Time Limit Exceeded

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

# process
def toNum(l):
    n = 0
    for i in range(len(l[::-1])):
        n += l[i]*10**i
    return n

ans = 0
for i in range(N):
    for j in range(i+1, N+1):
#        print("{} {} {}".format(i, j, S[i:j]))
        if toNum(S[i:j])%P == 0:
            ans += 1 

# output
print(ans)

# print("ans: {}".format(ans))

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:
n, p = map(int, input().split())
s = input()

cnt = 0
for i in range(0, 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:
n,p=map(int,input().split())
s=input()
ans=0
for i in range(n):
    for j in range(i,n):
        num=int(s[i:j+1])
        if num%p==0:
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict

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

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

ans = 0
for k, v in dict.items():
    if k%p == 0:
        ans += v
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

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

ans = 0
m = set()
for s in range(N):
    for e in range(s+1, N+1):
        if S[s:e] in m:
            ans += 1
            continue
        if int(S[s:e]) % P == 0:
            ans += 1
            m.add(S[s:e])
print(ans)

Submission status: Time Limit Exceeded

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

# List of ints
def LI(): return list(map(int, sys.stdin.readline().split()))

# Single int
def I(): return int(sys.stdin.readline())

# List, which contains Lists of chars (not strings)
def LS():return list(map(list, sys.stdin.readline().split()))

# Single List of chars (not strings)
def S(): return list(sys.stdin.readline())[:-1]

# List of "n" integers from "n" lines.
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
# List of "n" Lists of integers
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l


# Runtime Complexity: O(?)
# Space Complexity: O(?)
# Solution
N, P = LI()
s = sys.stdin.readline().split()[0]

nums = list(map(int, s))

# print(N, P, S)

res = 0
for i in range(len(nums)):
    num = nums[i]
    if num % P == 0:
        res += 1

    for j in range(i + 1, len(nums)):
        num *= 10
        num += nums[j]

        if num % P == 0:
            res += 1

print(res)

Submission status: Time Limit Exceeded

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

for i in range(n):
  for j in range(n-i):
    l.append(s[j:j+i+1])

l = [int(i)%p for i in l]
res = l.count(0)
print(res)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    n, p = tuple([int(s) for s in input().split()])
    s = input()
    memo = {}

    res = 0
    for i in range(len(s)):
        for j in range(i, len(s)):
            if (i, j) in memo.keys():
                res += memo[(i, j)]
            curr = int(s[i:j + 1])
            if curr % p == 0:
                memo[(i, j)] = 1
                res += 1
            else:
                memo[(i, j)] = 0

    print(res)

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]
temp = 0
cum = [0]*n
for i in range(n):
    temp += s[i]*10**i
    cum[i] = temp
    cum[i] = cum[i]%p
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:
import itertools

N, P = list(map(int, input().strip().split()))
S = input().strip()
ans = 0
#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 % P == 0:
      #print(num)
      ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
if __name__ == '__main__':
    lines = sys.stdin.readlines()
    line = [a.strip('\n').split(' ') for a in lines]
    for i,v in enumerate(line):
        if i == 0:
            n = int(v[0])
            p = int(v[1])
        else:
            numbers = list(v[0])
            # print(numbers)

    count = 0
    for i in range(n):
        for j in range(i+1,n+1):
            strs = ''.join(numbers[i:j])
            num = int(strs)
            if num%p==0:
                count += 1

    print(count)

Submission status: Time Limit Exceeded

Solution code:
def construct_matrix(N):
    matrix = []
    for i in range(N):
        matrix.append([0]*N)
    return matrix

if __name__ == "__main__":
    N, P = [int(x) for x in input().split(" ")]
    S = input()
    mods = construct_matrix(len(S))
    count = 0
    for i in range(len(S)):
        mods[i][i] = int(S[i]) % P
        if (mods[i][i] == 0):
            count += 1
    for i in range(len(S)):
        for j in range(i+1, len(S)):
            mods[i][j] = ((10%P * mods[i][j-1]%P)%P + int(S[j])%P) % P
            if (mods[i][j] == 0):
                count += 1
    print(count)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

res = [P]*N
count=0

for i in range(N):
    #print(N-1-i) 
    q = S[N-1-i] 
    #print(q)
    for j in range(i+1):
        res[j] = (res[j]+q*(10**(i-j)))%P
        #print(res)
        if res[j] ==0:
            count+=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)]
ans = 0
tmp = 0
for i in range(n):
    now = int(s[i])%p
    if not now:
        ans += 1
    for j in range(i+1,n):
        # print(i,j)
        now = int(s[j])%p + mods[now]
        now %= p
        if not now:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
nums=input().split(" ")
n,p=int(nums[0]),int(nums[1])
num=input()
count=0
for i in range(n):
    for j in range(i,n):
        if int(num[i:j+1])%p ==0:
          count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import glob

# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = 'ABC\\158\\E'

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'


class Common:
    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index - 1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class Solver(Common):

    def resolve(self):

        tmp = self.input_data().split()
        N = int(tmp[0])
        P = int(tmp[1])
        S = self.input_data()

        count = 0

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

        print(str(count))


solver = Solver(REL_PATH)
solver.exec_resolve()

Submission status: Time Limit Exceeded

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

def countSubStr(str, l, k): 
    count = 0
  
    for i in range(l): 
        n = 0
  
        # Take all sub-strings starting from i 
        for j in range(i, l, 1): 
            n = n * 10 + (ord(str[j]) - ord('0')) 
  
            # If current sub-string is divisible by k 
            if (n % k == 0): 
                count += 1
      
    # Return the required count 
    return count 


def solve(N: int, P: int, S: int):
    S = str(S)
    ans = countSubStr(S, len(S), P)
    print(ans)


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    solve(N, P, S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
  N,P=map(int, input().split())
  S=input()
  cnt=0
  for i in range(len(S)):
    temp=0
    for j in range(i,len(S)):
      temp=((temp*10)%P+int(S[j])%P)%P
      cnt+=(temp==0)
  print(cnt)
main()

Submission status: Time Limit Exceeded

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

cnt = 0
s = set()
for i in range(len(S)):
    for j in range(i, len(S)):
        tmp = int(S[i:j + 1])
        if tmp in s:
            cnt += 1
            continue
        if tmp % P == 0:
            s.add(tmp)
            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):
    for j in range(1,N+1):
        s=S[i:j]
        if len(s)==0:
            continue
        if int(s)%P==0:
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

m=0
for i in l:
    if int(i)%p==0:
        m+=1
print(m)

Submission status: Time Limit Exceeded

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

def check_num(s):
    count = 0
    if len(s) == 1:
        if int(s) % p == 0:
            return 1
        else:
            return 0
    for i in range(len(s)):
        part = s[:i+1]
        if int(part) % p == 0:
            count += 1
    return count + check_num(s[1:])

print(check_num(s))

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
N,P = map(int,input().split())
S = input()
#s = set()
#for i in range(1,int(S)//P):
#  s.add(P*i)
ret = 0
#print(s)
ret = sum([ 1 for end in range(1,len(S)+1) for start in range(end) if int(S[start:end])%P==0])
#for end in range(1,len(S)+1):
#  for start in range(end):
    #if int(S[start:end]) in s:
    #  ret += 1
#    if int(S[start:end])%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]
    pre = [p - pow(10, i, p) for i in range(len(s))]
    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()

Submission status: Time Limit Exceeded

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

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

    ans = 0
    for i in range(p):
        ans += cnt[i] * (cnt[i] - 1) // 2
    print(ans)

Submission status: Time Limit Exceeded

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

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, P = lr()
S = sr()
# 累積和
remain = [0] * N
cur = 0
for i in range(N):
    num = 10 * cur + int(S[i])
    cur = num % P
    remain[i] = cur

counter = Counter(remain)
answer = 0
v = counter[0]
if v >= 1:
    answer += v * (v+1) // 2

for i in range(N):
    if remain[i] == 0:
            continue
    for j in range(i+1, N):        
        diff = j - i
        if (remain[j] - remain[i] * (10**diff)) % P == 0:
            answer += 1

print(answer)

Submission status: Time Limit Exceeded

Solution code:

def resolve():
    N,P=map(int,input().split())
    S=list(map(int,input()))
    count=0
    amaris=dict()
    for i in S:
        ca=i%P
        count+=amaris[0] if 0 in amaris else 0
        nd=dict()
        for j,v in amaris.items():
            na=(j*10+i)%P
            if  na in nd:
                nd[na]+=v
            else:
                nd[na]=v
        if  i%P in nd:
            nd[i%P]+=1
        else:
            nd[i%P]=1
        
        amaris=nd
    
    if 0 in amaris:
        print(count+amaris[0])
    else:
        print(count)


                


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N, P = read_int()
S = read_str()

def solve():
    ans = 0
    for i, s in enumerate(S):
        for j, si in enumerate(S[i:]):
            n = int(s + S[i + 1 : i + 1 + j])
            if n % P == 0:
                ans += 1
    return ans

if __name__ == "__main__":
    print(solve())

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
N,P = [int(i) for i in input().split()]
S = list(input())
DP = [[0]*P for i in range(N+1)]
amari =[[(a*10+num)%P for a in range(P)]for num in range(10)]#amari[num][a]
tasi = 0
if P not in[2,5]:
    for j,s in enumerate(S):
        Num = int(s)
        for a,dd in enumerate(DP[j]):
            if a==0:tasi += dd
            DP[j+1][amari[Num][a]] = dd
        DP[j+1][Num%P] += 1
    print(DP[N][0] + tasi)
else:
    for j,s in enumerate(S):
        Num = int(s)
        for a,dd in enumerate(DP[j]):
            if a==0:tasi += dd
            DP[j+1][amari[Num][a]] += dd
        DP[j+1][Num%P] += 1
    print(DP[N][0] + tasi)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
NP = input().split(' ')
S =input()
N = int(NP[0])
P = int(NP[1])
Ss = [int(S[x:y+1]) for x in range(N) for y in range(N) if x<=y]
SP = [u for u in Ss if u % P ==0]
print(len(SP))

Submission status: Time Limit Exceeded

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

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

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):
        s.append(int(S[i:i+j+1]))

#print(s)

co = np.mod(s,P)

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

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = [int(i) % p for i in input()]
mod = [[0] * p for _ in range(n)]
for i in range(n):
  mod[i][s[i]] = 1
count = mod[0][0]
for i in range(1, n):
  for j in range(p):
    mod[i][(j * 10 + s[i]) % p] += mod[i-1][j]
  count += mod[i][0]
print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,p = map(int,input().split())
s = input()
num = 0
ans = 0
for i in range(n):
	num = int(s[i])
	if num % p == 0:ans+=1
	for j in range(i+1,n):
		num = 10 * num + int(s[j])
		if num % 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):
    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:
def main():
    n, p = map(int, input().split())
    s = input()
    r = 0
    for i in range(1, n + 1):
        for j in range(0, n - i + 1):
            r += int(s[j:j+i]) % p == 0
    print(r)
main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = input()
ans = 0
x0 = [0]*p
y = [0]*(10*p)
for i in range(10*p):
  y[i] = i%p
for t in s:
  x1 = [0]*p
  z = int(t)
  x1[z%p] = 1
  for j in range(p):
    x1[y[10*j+z]] += x0[j]
  x0 = x1
  ans += x0[0]
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):
    for j in range(i, n):
        if int(s[i:j+1]) % p == 0:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

if __name__ == "__main__":
    main()

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()
s = list(map(int, list(s)))
#print(s)
res = 0
for i in range(n):
    mod = 0
    for j in range(i, n):
        mod *= 10
        mod += s[j]
        mod %= p
        if mod == 0:
            res += 1
print(res)

Submission status: Time Limit Exceeded

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

num = 0
count = 0
for i in range(N):
    x = S[i] % P
    if x == 0:
        count += 1
    for j in range(i + 1, N):
        x = (10 * x + S[j]) % P
        if x == 0:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

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

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

    print(count)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split(' '))
S = input()
count = 0
for n in range(1, N+1):
    for i in range(N-n+1):
        num = int(S[i:i+n])
        if num % 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_ss = int(s[i:j])
        if n_ss % p == 0:
            ans += 1

print(ans)

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][1][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][1][c%P]+=1
    #print(dp)
print(dp[N-1][0][0]+dp[N-1][1][0])

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, p = 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)
main()

Submission status: Time Limit Exceeded

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

prev_key = {}
count = 0
for c in s:
    i = int(c) % p
    key = {i:1}
    if i == 0:
        count += 1
    for check in prev_key.keys():
        test = (check * 10 + i) % p
        if(test in key):
            key[test] += prev_key[check]
        else:
            key[test] = prev_key[check]
        if(test == 0):
            count += prev_key[check]
    prev_key = key
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, Counter, namedtuple, deque
from bisect import bisect_left
from functools import reduce
import math

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


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

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

print(ans)

Submission status: Time Limit Exceeded

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

ps = {}
count = 0

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

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)

Submission status: Time Limit Exceeded

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

p_d = {}
count = 0
for i in range(N):
    for j in range(1, N-i+1):
        q = int(S[i:i+j])
        if q in p_d:
            ans = p_d[q]
            if ans:
                count += 1
        elif q % P == 0:
            p_d[q] = True
            count += 1
        else:
            p_d[q] = False
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys

n, p = [int(s) for s in sys.stdin.readline().strip().split()]
s = sys.stdin.readline().strip()

dic = [0] * p
ans = 0

for i in range(n):
    num = int(s[i])
    next_dic = [0] * p
    next_dic[num % p] = 1
    for key, val in enumerate(dic):
        if val > 0:
            rem = (key * 10 + num) % p
            next_dic[rem] += val
    ans += next_dic[0]
    dic = next_dic

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = input()
res = 0
for i in range(n):
    #ss = ""
    mod = 0
    for j in range(i, n):
        #ss = ss + s[j]
        mod *= 10
        mod += int(s[j]) % p
        mod %= p
        if mod == 0:
            res += 1
print(res)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

print(ans)

Submission status: Time Limit Exceeded

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

memo = {}
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 in memo:
            cnt += 1
        elif val % P == 0:
            memo[val] = 1
            cnt += 1

# print(memo)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N,P = [int(i) for i in input().split()]
S = list(input())
DP = [[0]*(N+1) for i in range(P)]
amari =[[(a*10+num)%P for a in range(P)]for num in range(10)]#amari[num][a]
tasi = 0
if P not in[2,5]:
    for j,s in enumerate(S):
        Num = int(s)
        tasi += DP[0][j]
        for a in range(P):
            DP[amari[Num][a]][j+1] = DP[a][j]
        DP[Num%P][j+1] += 1
    print(DP[0][N] + tasi)
else:
    for j,s in enumerate(S):
        Num = int(s)
        tasi += DP[0][j]
        for a in range(P):
            DP[amari[Num][a]][j+1] += DP[a][j]
        DP[Num%P][j+1] += 1
    print(DP[0][N] + tasi)

Submission status: Time Limit Exceeded

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