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: Runtime Error

Solution code:
n,p=map(int,input().split())
S=input()
s=int(s)
ans=0
if p==5:
    for i in range(n):
        if int(S[i])==5 or int(S[i])==0:
            ans+=i+1
elif p==2:
    for i in range(n):
        if int(S[i])%2==0:
            ans+=i+1
else:
    kouho=[0]*p
    for i in range(n):
        a=int(S[-i:])
        a%=p
        kouho[a]+=1
    for j in range(p):
        z=kouho[j]
        ans+=z*(z-1)//2
    ans+=kouho[0]
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
n,p=map(int,input().split())
s=input().rstrip()
if p==2:
    for i in range(n):
        ans=0
        if s[i]%2==0:
            ans+=i+1
elif p==5:
    for i in range(n):
        ans=0
        if s[i]==0 or s[i]==5:
            ans+=i+1
else:
    count=[0]*p
    x=0
    y=1
    count[0]=1
    for i in range(n-1,-1,-1):
        x=x+y*int(s[i])
        x=x%p
        count[x]+=1
        y=(y*10)%p
    ans=0
    for i in count:
        ans+=i*(i-1)//2
print(ans)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <fstream>
#include <random>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

#define int int64_t

int binpow(int a, int pw, int mod) {
    if (pw <= 0) {
        return a;
    }
    if (pw % 2 == 0) {
        return binpow(a*a%mod, pw/2, mod);
    } else {
        return (binpow(a, pw-1,mod) * a)%mod;
    }
}


signed main() {

    //freopen("../input.txt", "r", stdin);

    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();

    int n, p;
    string s;
    cin >> n >> p >> s;

    int ans = 0;

    if (p == 2 || p == 5) {
        for (int i = 0; i < n; ++i) {
            if ((s[i] - '0') % p == 0) {
                ans += i + 1;
            }
        }
    } else {
        map<int, int> cnt;
        int tenPower = 1;
        int currRem = 0;

        cnt[0]++;

        for (int i = n - 1; i >= 0; --i) {
            currRem = (currRem + tenPower * (s[i] - '0')) % p;
            tenPower *= 10;
            tenPower %= p;

            ans += cnt[currRem];
            cnt[currRem]++;
        }

    }



    cout << ans;
    return 0;
}

Submission status: Runtime Error

Solution code:
n,p = map(int, input().split())
s = list(map(int, list(ns())))
if p in (2, 5):
  print(sum(i+1 for i in range(n) if s[i]%p == 0))
  exit(0)
   
ans = g = 0
d = [0]*p
d[0] = 1
t = 1
for i in range(n-1,-1,-1):
    g = (g + s[i]*t)%p
    ans += d[g]
    d[g] += 1
    t = (t*10)%p
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
nandp=list(map(int, input().split()))
sstr=input()
s=[]
p=nandp[1]
for i in range(nandp[0]):
    s.append(int(sstr[i]))
print(s)
answer=np.zeros((nandp[0],nandp[0]))
counter=0
for kk in range(nandp[0]):
    answer[0][kk]=s[kk]%p
    if(answer[0][kk]==0):
        counter+=1
for j in range(1,nandp[0]):
    for k in range(0,nandp[0]-j):
        answer[j][k]=(answer[j-1][k]*10+answer[0][j+k])%p
        if(answer[j][k]==0):
            counter+=1
            #print(j)
            #print(k)
print(counter)

Submission status: Runtime Error

Solution code:
import numpy as np
nandp=list(map(int, input().split()))
sstr=input()
s=[]
p=nandp[1]
for i in range(nandp[0]):
    s.append(int(sstr[i]))
print(s)
answer=np.zeros((nandp[0],nandp[0]))
counter=0
for kk in range(nandp[0]):
    answer[0][kk]=s[kk]%p
    if(answer[0][kk]==0):
        counter+=1
for j in range(1,nandp[0]):
    for k in range(0,nandp[0]-j):
        answer[j][k]=(answer[j-1][k]*10+answer[0][j+k])%p
        if(answer[j][k]==0):
            counter+=1
            #print(j)
            #print(k)
print(counter)

Submission status: Runtime Error

Solution code:
n,p=map(int,input().split())
s=input()
if p==2 or p==5:
    a=0
    for i in range(n):
        if int(s[i])%p==0:
            ans+=n
    print(a)
else:
    a=0
    g=[0]*(n+1)
    t=[0]*p
    t[0]=1
    for i in range(n-1,-1,-1):
        g[i]=(g[i+1]*10+int(s[n-i-1]))%p
        a+=t[g[i]]
        t[g[i]]+=1
    print(a)

Submission status: Runtime Error

Solution code:
dp = [[0 for i in range(N-j)] for j in range(N)]
dp
for j in range(N):
    dp[j][0]=(int(S[j])%mod)
    for i in range(1,N-j):
        dp[j][i]=((dp[j][i-1]*10+int(S[j+i]))%mod)
ans = 0
for i in range(N):
    ans += dp[i].count(0)
    
print(ans)

Submission status: Runtime Error

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

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

    for i in range(1,N+1):
        n = int(S[N-i:])
        modlist[n%P] = modlist[n%P]+1
    modlist[0]+=1

    ans=0
    for i in modlist:
        if i>=2:
            ans = ans + i*(i-1)/2
    print(int(ans))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from math import factorial

def comb(n, r):
    return factorial(n) // factorial(r) // factorial(n - r)

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

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

cnt = [0]*10
ans = 0
for i in range(len(s)):
    cnt[list[i]] += 1

ans = cnt[0]
for i in range(10):
    if cnt[i] >= 2:
        ans += comb(cnt[i], 2)
print(int(ans))

Submission status: Runtime Error

Solution code:
count=0
c_zero=1
for i in range(N):
    tmp=0
    flag=0
    for j in range(i,N):
#         print(int(S[i:j+1]),int(S[i:j+1])%P,c_zero)
        if int(S[i])==0:
            count+=c_zero
            c_zero+=1
            flag=1
            break
        else:
            if int(S[i:j+1])%P==0:
                tmp+=1
    count+=tmp*c_zero
#     print(count)
    if flag==0:
        c_zero=1
print(count)

Submission status: Runtime Error

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, P = iim()
    S = list(map(int, input().rstrip()))

    if P == 2:
        cnt = N * (N + 1) // 2
        for i, si in enumerate(S):
            if si & 1:
                cnt -= i + 1
        print(cnt)
        return

    i = j = 1
    while j < P:
        i += 1
        j *=10
    keta = i - 2
    cnt = 0
    for i in range(N):
        ans = 0
        if S[i] == 0:
            cnt += 1
        for j in range(i, i+keta):
            ans = 10*ans + S[j]
        for j in range(i+keta, N):
            sj = S[j]
            ans = 10*ans + sj
            #print(ans, ans % P)
            if ans % P == 0:
                cnt += 1
    print(cnt)

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

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


ans=0
ss=[]
for i in range(n):
    for k in range(n):
        s2=s[i:(n-k)]
        s3=int(s2)
       
        if int(s3)%p==0:
            ans+=1

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

mem = defaultdict(int)
mem[0] += 1
T = [0]
dec = 1
x = 0
for s in S[::-1] :
  s = int(s)
  x = (dec * s + x) % P
  dec = dec * 10 % P
  T.append(x)
  mem[x] += 1

inv = pow(10, P - 2, P)
dec = 1
ret = 0
for i, t in enumerate(T) :
  if dec % P =  0 :
    ret += len(T) - i - 1
  else :
    ret += mem[t] - 1
  mem[t] -= 1
  dec = dec * inv % P
  
print(ret)

Submission status: Runtime Error

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

mod = p
l = 100

M = [1]  # i!のmod
m = 1
for i in range(1, l):
    m = (m * i) % mod
    M.append(m)

def pow(x, y, mod):  # x**y の mod を返す関数
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = (ans * x) % mod
        x = (x**2) % mod
        y //= 2
    return ans

def inv(x, mod):  # x の mod での逆元を返す関数
    return pow(x, mod-2, mod)


P = [0] * p

T = [1]
for i in range(n-1):
    T.append((T[-1] * 10) % p)

# a = 0
# for i in range(n):
#     a = (a * 10 + int(s[i]))
#     a = a%p
#     P[a] += 1

ans = 0
u = 0
v = 0
s = list(s)
for i in range(n):
    s[i] = int(s[i])
# for i in range(n):
#     print(u,P[(p-u)%p])
#     ans += P[(p-u)%p]
#     u = (u-int(s[n-1-i])) % p
#     u = u * inv(10%p, mod) % p
# print(s)
for i in range(n):
    v = (u * 10 + s[i]) % p
    P[v] += 1
    # qq = s[i-1] if i > 0 else 0
    ans += P[(p-v*s[i])%p]
    # print(ans)
    u = v
s -= 1
if s[-1] == 0:
    s += 1

print(ans)

Submission status: Runtime Error

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

a=[s[i:] for i in range(len(s))] + [s[:i] for i in range(len(s))]
a=[v for v in a if v!='']
print(a)
for ele in a:
    if int(ele)%p==0:t+=1
        
print(t+1)

Submission status: Runtime Error

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

    ans = 0
    if P == 5:
        for i in range(1):
            for j in range(1, N-i+1):
                num = int(S[i:i+j])
                if num % P == 0:
                    # print("!", end=" ")
                    ans += len(S[i:i+j])
                # print(num)
    else #if P == 2:
        for i in range(1):
            for j in range(1, N-i+1):
                num = int(S[i:i+j])
                if num % P == 0:
                    # print("!", end=" ")
                    ans += len(S[i:i+j])
                # print(num)
    """
    A = [int(s) for s in S]
    from itertools import accumulate
    acc = accumulate([0] + A)
    right = N
    for left in range(N):
        while left

    print()
    """
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N, P = MI()
    s = S()
    ans = 0
    dic = [0] * N
    dic2 = [0] * (N - 1)

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

    tmp = 0
    for i in range(N + 1 - len(str(P))):
        if int(s[i:i+len(str(P))]) % P == 0:
            dic[i] = 1
            tmp += 1

    for i in range(N + 1 - len(str(P)) - 1):
        if s[i:i+1+len(str(P))][0] == '0':
            continue

        if int(s[i:i+1+len(str(P))]) % P == 0:
            dic2[i] = 1
            tmp += 1

    D = list(accumulate(dic))
    D2 = list(accumulate(dic2))
    # print(D, D2)
    # print((D[-1] + D2[-1]) * 2)

    # print(ans)
    tmp = 0
    tmp += (D[-1] * (D[-1] + 1)) // 2
    tmp += (D2[-1] * (D2[-1] + 1)) // 2
    print(tmp)
    # print(tmp, dic)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
input = raw_input

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

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

if p != 2:
    inv10 = modinv(10, p)
else:
    inv10 = None

#for i in range(n-1, -1, -1):
if True:
    i = n-1
    cur_num = s[i] % p
    cur_keta = 1
    if cur_num == 0:
        out += 1
    nums[cur_num] += 1

    kiroku = [None] * n
    kiroku[i] = cur_num

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

    #print(nums)
    nums2 = nums
    for del_i in range(n-1, -1, -1):
        #nums[(zure+del_num) % p] -= 1
        if p != 2:
            zure = (zure + inv10 )% p
        nums2[(zure+kiroku[del_i])%p] -= 1

        nums2 = nums2[zure:] + nums2[:zure]
        out_ = nums2[0]
        #print("cur_out", out_)
        out += out_
        #print(nums, nums2)

#print(out)

print(out)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h> 
using namespace std; 
 
int countSubStr(string str, int len, int k) 
{ 
	int count = 0; 

	for (int i = 0; i < len; i++) { 
		int n = 0; 

		for (int j = i; j < len; j++) { 
			n = n * 10 + (str[j] - '0'); 

			if (n % k == 0) 
				count++; 
		} 
	} 

	return count; 
} 

int main() 
{   
    int n, p;
    cin >> n >> p;
	string str;
    cin >> str; 
	cout << countSubStr(str, n, p); 

	return 0; 
}

Submission status: Runtime Error

Solution code:
N,P=map(int,input(),split())
S=input()
count==0
for i in range(N):
	kazu=N-i
    for j in range(0,kazu):
		score=int(S(i,i+j)):
        	if score%P==0:
            	count=count+1
print(count)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

S=raw_input()
Q=input()
Query=[ sys.stdin.readline().split() for _ in range(Q) ]

s1=deque()
s2=deque()
judge={}
judge["front"]="s1"
judge["end"]="s2"

cnt=0
for x in Query:
    if x[0]=="1":
        n=x[0]
        cnt+=1
    elif x[0]=="2":
        n,f,c=x[0],x[1],x[2]
    if n=="1":
        judge["front"],judge["end"]=judge["end"],judge["front"]
    elif n=="2":
        if f=="1":
            if judge["front"]=="s1":
                s1.appendleft(c)
            elif judge["front"]=="s2":
                s2.appendleft(c)
        elif f=="2":
            if judge["end"]=="s1":
                s1.append(c)
            if judge["end"]=="s2":
                s2.append(c)

str1=""
for x in s1:
    str1+=x
str2=""
for x in s2:
    str2+=x

if cnt%2==0:
    print str1[::-1]+S+str2
elif cnt%2==1:
    print str2+S[::-1]+str1[::-1]

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
def main():
    import sys
    from collections import Counter
    input = sys.stdin.readline

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

    for i in range(n):
        s_1 = int(s[i:n])
        lis.append(s_1 % p)
    c = Counter(lis)
    c_1 = c.values()
    ans = 0
    for i in range(c_1):
        ans += (c_1[i])**2
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Runtime Error

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)
for end in range(1,len(S)+1):
  for start in range(end):
    #if int(S[start:end]) in s:
    #  ret += 1
    if len(end-start) > P and int(S[start:end])%P==0:
      ret += 1
print(ret)

Submission status: Runtime Error

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

ans = 0
p0 = 0
dp = [0] * p
for i in s[::-1]:
    i = int(i)
    p0 = p0*10 % p
    dp[p0 + i] += 1
    ans += dp[p0]

print(ans)

Submission status: Runtime Error

Solution code:
N,P=map(int,input().split())
S=input()
ans=0
for i in range(1,N+1):
    ans+=sum(map(lambda x: int(x)%P==0, getCharNGram(i,S)))
print(ans)

Submission status: Runtime Error

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

ans = 0
p0 = 0
dp = [0] * p
for i n range(s[::-1]):
    i = int(i)
    p0 = p0*10 % p
    dp[p0 + i] += 1
    ans += dp[p0]

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

n, p = map(int, input().split())
s = np.array([int(i) % p for i in input()])
mod = np.zeros((n, p), dtype=np.int)
for i in range(n):
  mod[i, s[i]] = 1
count = mod[0, 0]
for i in range(1, n):
  idx = s[i]
  for j in range(p):
    mod[i, idx] += mod[i-1, j]
    idx = (idx + 10) % p
print(mod[:, 0].sum())

Submission status: Runtime Error

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


ans=0
ss=[]
for i in range(n):
    for k in range(n):
        s2=s[i:(n-k)]
        ss.append(s2)
       
ss2=[int(x) for x in ss if x!=""]
for y in ss2:
    if y%p==0:
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
import sys; sys.setrecursionlimit(2147483647); input = sys.stdin.readline
from math import floor, ceil, sqrt, factorial, log
from collections import Counter, defaultdict
from operator import itemgetter
INF = float('inf'); MOD = 10**9+7
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(MI())
def LIR(n): return [LI() for i in range(n)]
def S(): return input().rstrip()
def LIR(n): return [S().split() for i in range(n)]

def main():
    s = S()
    Q = I()
    Qu = LIR(Q)
    for que in Qu:
        if que[0] == '1':
            s = s[::-1]
        else:
            if que[1] == '1':
                s = ''.join([que[2], s])
            else:
                s = ''.join([s, que[2]])
    print(s)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N,P=map(int,input(),split())
S=input()
count==0
for i in range(N):
	kazu=N-i
    for j in range(1,kazu):
	    score=int(S(i,i+j)):
        	if score%P==0:
            	count=count+1
print(count)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def is_prime(num):
  i = 5
  while (i * i <= num):
      if num % i == 0 or num % (i+2) ==0:
          return False
      i+=6
  return True if num > 1 and num <=3 else False if num % 2 == 0 or num % 3 == 0 or num <=1 else True

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

count = 0
for n in l:
    count+=1 if int(n)%p==0 else 0
print(count)

Submission status: Runtime Error

Solution code:
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: Runtime Error

Solution code:
import numpy as np

n, p = map(int, input().split())
s = np.array([int(i) % p for i in input()])
mod = np.zeros((n, p), dtype=np.int)
for i in range(n):
  mod[i, s[i]] = 1
count = mod[0, 0]
for i in range(1, n):
  idx = s[i]
  for j in range(p):
    mod[i, idx] += mod[i-1, j]
    idx = (idx + 10) % mod
print(mod[:, 0].sum())

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

StringP = str (P)
kosu = 0
if N < len(StringP):
    print(0)
else:
    for lng in range(len(StringP)-1, N+1):
        for i in range(0, N-lng+1):
            if int(S[i:i+lng]) % P ==0:
                kosu = kosu+1

print(kosu)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

N, P = map(int, input().split())
S = input()
acc = [0] * (N+1)
for i in range(N):
  acc[i+1] = (acc[i]*10 + int(S[i])) % P

res = [[] for i in range(P)]
for i in range(N+1):
  res[acc[i]].append(i)

class factorial:
  def __init__(self, n, p=10**9 + 7):
    self.__p  = p
    self.__fac  = [0] * (n+1)
    self.__inv  = [0] * (n+1)
    self.__finv = [0] * (n+1)

    self.__fac[0] = self.__fac[1] = 1
    self.__inv[1] = 1
    self.__finv[0] = self.__finv[1] = 1

    for i in range(2, n+1):
      self.__fac[i] = self.__fac[i-1] * i % p
      self.__inv[i] = p - self.__inv[p%i] * (p // i) % p
      self.__finv[i] = self.__finv[i-1] * self.__inv[i] % p
  
  def fact(self, n):
    return self.__fac[n]
  
  def perm(self, n, k):
    return self.__fac[n] * self.__finv[n-k] % self.__p
  
  def comb(self, n, k):
    return self.perm(n, k) * self.__finv[k] % self.__p
f = factorial(2*10**5)
ans = 0
for p in range(P):
  ans += f.comb(len(res[p]), 2) if len(res[p]) > 1 else 0
print(ans)

Submission status: Runtime Error

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


def solve(N: int, P: int, S: int):
    if N == 1:
        print(1 if S[0]%P == 0 else 0)
    arr = [[int(S[i])%P for i in range(N)]]
    for i in range(2,N):
        prevArr = arr[-1]
        arr.append([0]*(N-i+1))
        for j in range(N-i+1):
            sum = 0
            for k in range(j):
                arr[-1][j] =(arr[-1][j]+prevArr[k])%P
    print(arr)


    # sum = 0
    # for i in range(N):
    #     sDiv = 0
    #     coeff = 1
    #     for j in range(i,N):
    #         sDiv= (sDiv*coeff + arr[j])%P
    #         coeff*=10
    #         if sDiv == 0:
    #             sum+=1
    # print(sum)
    return


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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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):
    dpf(i)

print(sum(dp))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def inverse_mod(a, m):  # mod mでのaの逆元
    b=m
    u=1
    v=0
    while b:
        t=a // b
        a -= t * b
        a, b=b, a
        u -= t * v
        u, v=v, u
    u %= m
    return u
def main():
    N,P=MI()
    if P==2:
        raise Exception
    S=ST()
    before = 0
    ans = 0
    d = defaultdict(int)
    d[0] += 1
    for i in range(N):
        x = int(S[i])
        before += x
        before %= P
        ans += d[(before*(inverse_mod(10,P)**i))%P]
        d[before] += 1
        before *= 10

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

Submission status: Runtime Error

Solution code:
N,P=map(int,input().split())
S=list(map(int,input().split()))
count=0
a=0
for i in range(N):
    for j in range(N): #i<J
        if i<=j:
            for t in range(i,j):
                a=a+S[i]*10**(j-t)
            if a%P==0:
                count+=1
print(count)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()

int main() {
    int N, P;
    cin >> N >> P;
    string S;
    cin >> S;
    ll count[P];
    memset(count, 0, sizeof(count));
    ll ncount[P];
    ll ans = 0;
    rep(i, N) {
        int d = S.at(i) - '0';
        count[0]++;
        memset(ncount, 0, sizeof(ncount));
        rep(j, P) {
            int nj = (j * 10 + d) % P;
            ncount[nj] += count[j];
        }
        rep(j, P) count[j] = ncount[j];
        ans += count[0];
    }
    cout << ans << endl;
}

Submission status: Runtime Error

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

print(counter)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
n,p=map(int,input().split())
l=list(input())
for i in range(n):
    l[i]=int(l[i])
w=0
wl=[]
po=pow(10,p-2,p)
for i in range(n):
    wl.append(w)
    #if w==0:
        #ans+=rr[n-1-i]
    w-=l[n-1-i]
    w*=po
    w%=p
wl.reverse()
r=[]
rt=0
for i in range(n):
    rt+=l[n-1-i]*(10**i)
    r.append(rt%p)
r.reverse()
d=tuple(0 for i in range(p))
ans=0
for i in range(n):
    d[r[i]]+=1
    ans+=d[wl[i]]  
print(ans)

Submission status: Runtime Error

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

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

for ss in res:
  if(int(ss) % p == 0):
      count += 1
print(count)

Submission status: Runtime Error

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

S = input()

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
solve(0)
print(sum(ans))

Submission status: Runtime Error

Solution code:
m_l=[0 for i in range(p)]

dp=[0 for i in range(p)]
dp2=[0 for i in range(p)]
st=int(s[0])%p
dp[st]+=1
m_l[st]+=1
use_set={st}

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+mod_10*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
    for num in use_set:
        m_l[num]+=dp[num]

print(m_l[0])

Submission status: Runtime Error

Solution code:
from collections import Counter
N, P = map(int, input().split())
S = input()
L = len(str(P))
M = []
for i in range(10 ** (L+1)):
    M.append(i % P)

q = Counter([int(S[i:L-1]) for i in range(L-1)])
q[0] += 1
ans = 0
for i in range(L-1, N):
    nq = Counter()
    n = int(S[i])
    for a, c in q.items():
        s = M[a * 10 + n]
        if s == 0:
            ans += c
        nq[s] += c
    nq[0] += 1
    q = nq
print(ans)

Submission status: Runtime Error

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

mod_10=10%p

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

m_l=[0 for i in range(n)]

dp=[0 for i in range(n)]
dp2=[0 for i in range(n)]
st=int(s[0])%p
dp[st]+=1
m_l[st]+=1
use_set={st}

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+mod_10*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
    for num in use_set:
        m_l[num]+=dp[num]

print(m_l[0])

Submission status: Runtime Error

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